Operational transformation


Operational transformation is a technology for supporting a range of collaboration functionalities in advanced collaborative software systems. OT was originally invented for consistency maintenance and concurrency control in collaborative editing of plain text documents. Its capabilities have been extended and its applications expanded to include group undo, locking, conflict resolution, operation notification and compression, group-awareness, HTML/XML and tree-structured document editing, collaborative office productivity tools, application-sharing, and collaborative computer-aided media design tools. In 2009 OT was adopted as a core technique behind the collaboration features in then-Google Wave and Google Docs.

History

Operational Transformation was pioneered by C. Ellis and S. Gibbs in the GROVE system in 1989. Several years later, some correctness issues were identified and several approaches were independently proposed to solve these issues, which was followed by another decade of continuous efforts of extending and improving OT by a community of dedicated researchers. In 1998, a Special Interest Group on Collaborative Editing was set up to promote communication and collaboration among CE and OT researchers. Since then, SIGCE holds annual CE workshops in conjunction with major CSCW conferences, such as ACM, CSCW, GROUP and ECSCW.

System architecture

Collaboration systems utilizing Operational Transformations typically use replicated document storage, where each client has their own copy of the document; clients operate on their local copies in a lock-free, non-blocking manner, and the changes are then propagated to the rest of the clients; this ensures the client high responsiveness in an otherwise high-latency environment such as the Internet. When a client receives the changes propagated from another client, it typically transforms the changes before executing them; the transformation ensures that application-dependent consistency criteria are maintained by all sites. This mode of operation results in a system particularly suited for implementing collaboration features, like simultaneous document editing, in a high-latency environment such as the web.

Basics

The basic idea of OT can be illustrated by using a simple text editing scenario as follows. Given a text document with a string "abc" replicated at two collaborating sites; and two concurrent operations:
  1. O = Insert
  2. O = Delete
generated by two users at collaborating sites 1 and 2, respectively. Suppose the two operations are executed in the order of O and O. After executing O, the document becomes "xabc". To execute O after O, O must be transformed against O to become: O = Delete, whose positional parameter is incremented by one due to the insertion of one character "x" by O''. Executing O on "xabc" deletes the correct character "c" and the document becomes "xab". However, if O'' is executed without transformation, it incorrectly deletes character "b" rather than "c". The basic idea of OT is to transform the parameters of an editing operation according to the effects of previously executed concurrent operations so that the transformed operation can achieve the correct effect and maintain document consistency.

Consistency models

One functionality of OT is to support consistency maintenance in collaborative editing systems. A number of consistency models have been proposed in the research community, some generally for collaborative editing systems, and some specifically for OT algorithms.

The CC model

In Ellis and Gibbs's 1989 paper "Concurrency control in groupware systems", two consistency properties are required for collaborative editing systems:
  • Causality preservation: ensures the execution order of causally dependent operations be the same as their natural cause-effect order during the process of collaboration. The causal relationship between two operations is defined formally by Lamport's "happened-before" relation. When two operations are not causally dependent, they are concurrent. Two concurrent operations can be executed in different order on two different document copies.
  • Convergence: ensures the replicated copies of the shared document be identical at all sites at quiescence.
Since concurrent operations may be executed in different orders and editing operations are not commutative in general, copies of the document at different sites may diverge. The first OT algorithm was proposed in Ellis and Gibbs's paper to achieve convergence in a group text editor; the state-vector was used to preserve the precedence property.

The CCI model

The CCI model was proposed as a consistency management in collaborative editing systems. Under the CCI model, three consistency properties are grouped together:
  • Causality preservation : the same as in the CC model.
  • Convergence: the same as in the CC model.
  • Intention preservation: ensures that the effect of executing an operation on any document state be the same as the intention of the operation. The intention of an operation O is defined as the execution effect which can be achieved by applying O on the document state from which O was generated.
The CCI model extends the CC model with a new criterion: intention preservation. The essential difference between convergence and intention preservation is that the former can always be achieved by a serialization protocol, but the latter may not be achieved by any serialization protocol if operations were always executed in their original forms. Achieving the nonserialisable intention preservation property has been a major technical challenge. OT has been found particularly suitable for achieving convergence and intention preservation in collaborative editing systems.
The CCI model is independent of document types or data models, operation types, or supporting techniques. It was not intended for correctness verification for techniques that are designed for specific data and operation models and for specific applications. In, the notion of intention preservation was defined and refined at three levels: First, it was defined as a generic consistency requirement for collaborative editing systems; Second, it was defined as operation context-based pre- and post- transformation conditions for generic OT functions; Third, it was defined as specific operation verification criteria to guide the design of OT functions for two primitive operations: string-wise insert and delete, in collaborative plain text editors.

The CSM model

The condition of intention preservation was not formally specified in the CCI model for purposes of formal proofs. The SDT and LBT approaches try to formalize an alternative conditions that can be proved. The consistency model proposed in these two approaches consist of the following formal conditions:
  • Causality: the same definition as in CC model
  • Single-operation effects: the effect of executing any operation in any execution state achieves the same effect as in its generation state
  • Multi-operation effects: the effects relation of any two operations is maintained after they are both executed in any states

    The CA model

The above CSM model requires that a total order of all objects in the system be specified. Effectively, the specification is reduced to new objects introduced by insert operations. However, specification of the total order entails application-specific policies such as those to break insertion ties. Consequently, the total order becomes application specific. Moreover, in the algorithm, the total order must be maintained in the transformation functions and control procedure, which increases time/space complexities of the algorithm.
Alternatively, the CA model is based on the admissibility theory. The CA model includes two aspects:
  • Causality: the same definition as in CC model
  • Admissibility: The invocation of every operation is admissible in its execution state, i.e., every invocation must not violate any effects relation that has been established by earlier invocations.
These two conditions imply convergence. All cooperating sites converge in a state in which there is a same set of objects that are in the same order. Moreover, the ordering is effectively determined by the effects of the operations when they are generated. Since the two conditions also impose additional constraints on object ordering, they are actually stronger than convergence. The CA model and the design/prove approach are elaborated in the 2005 paper. It no longer requires that a total order of objects be specified in the consistency model and maintained in the algorithm, which hence results in reduced time/space complexities in the algorithm.

OT system structure

OT is a system of multiple components. One established strategy of designing OT systems is to separate the high-level transformation control algorithms from the low-level transformation functions.
OT Control Algorithms
OT properties and conditions
OT Transformation Functions

The transformation control algorithm is concerned with determining:
  1. Which operation should be transformed against a causally ready new operation
  2. The order of the transformations
The control algorithm invokes a corresponding set of transformation functions, which determine how to transform one operation against another according to the operation types, positions, and other parameters. The correctness responsibilities of these two layers are formally specified by a set of transformation properties and conditions. Different OT systems with different control algorithms, functions, and communication topologies require maintaining different sets of transformation properties. The separation of an OT system into these two layers allows for the design of generic control algorithms that are applicable to different kinds of application with different data and operation models.
The other alternative approach was proposed in. In their approach, an OT algorithm is correct if it satisfies two formalized correctness criteria:
  1. Causality preservation
  2. Admissibility preservation
As long as these two criteria are satisfied, the data replicas converge after all operations are executed at all sites. There is no need to enforce a total order of execution for the sake of achieving convergence. Their approach is generally to first identify and prove sufficient conditions for a few transformation functions, and then design a control procedure to ensure those sufficient conditions. This way the control procedure and transformation functions work synergistically to achieve correctness, i.e., causality and admissibility preservation. In their approach, there is no need to satisfy transformation properties such as TP2 because it does not require that the transformation functions work in all possible cases.