Operational transformation

Operational Transformation was pioneered by C. Ellis and S. Gibbs[2] in the GROVE (GRoup Outline Viewing Edit) system in 1989. Several years later, some correctness issues were identified and several approaches[3][4][5][6] 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[7] 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 (Computer Supported Cooperative Work) conferences, such as ACM, CSCW, GROUP and ECSCW.

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 (invariants) 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.

Basic idea behind OT

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. O1 = Insert[0, "x"] (to insert character "x" at position "0")
2. O2 = Delete[2, "c"] (to delete the character "c" at position "2")

generated by two users at collaborating sites 1 and 2, respectively. Suppose the two operations are executed in the order of O1 and O2 (at site 1). After executing O1, the document becomes "xabc". To execute O2 after O1, O2 must be transformed against O1 to become: O2' = Delete[3, "c"], whose positional parameter is incremented by one due to the insertion of one character "x" by O1. Executing O2' on "xabc" deletes the correct character "c" and the document becomes "xab". However, if O2 is executed without transformation, it incorrectly deletes character "b" rather than "c". The basic idea of OT is to transform (or adjust) 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.

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.

OT is a system of multiple components. One established strategy of designing OT systems[2][3][4][5][12][13] is to separate the high-level transformation control (or integration) algorithms from the low-level 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.[11] 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 (with additional constraints) 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 (inclusive) transformation functions work in all possible cases.

There exist two underlying models in each OT system: the data model that defines the way data objects in a document are addressed by operations, and the operation model that defines the set of operations that can be directly transformed by OT functions. Different OT systems may have different data and operation models. For example, the data model of the first OT system[2] is a single linear address space; and its operation model consists of two primitive operations: character-wise insert and delete. The basic operation model has been extended to include a third primitive operation update to support collaborative Word document processing[14] and 3D model editing.[15] The basic OT data model has been extended into a hierarchy of multiple linear addressing domains,[16][17][18] which is capable of modeling a broad range of documents. A data adaptation process is often required to map application-specific data models to an OT-compliant data model.[19][20]

There exist two approaches to supporting application level operations in an OT system:

1. Generic operation model approach: which is to devise transformation functions for three primitive operations: insert, delete, and update.[19] This approach needs an operation adaptation process to map application operations to these primitive operations. In this approach, the OT operation model is generic, so transformation functions can be reused for different applications.
2. Application-specific operation model approach: which is to devise transformation functions for each pair of application operations.[20][21] For an application with m different operations, m x m transformation functions are needed for supporting this application. In this approach, transformation functions are application-specific and cannot be reused in different applications.

Various OT functions have been designed for OT systems with different capabilities and used for different applications. OT functions used in different OT systems may be named differently, but they can be classified into two categories:

• Inclusion transformation (or forward transformation): IT(Oa, Ob) or ${\displaystyle T(op_{1},op_{2})}$, which transforms operation Oa against another operation Ob in such a way that the impact of Ob is effectively included.
• Exclusion transformation (or backward transformation): ET (Oa, Ob) or ${\displaystyle T^{-1}(op_{1},op_{2})}$, which transforms operation Oa against another operation Ob in such a way that the impact of Ob is effectively excluded.

For example, suppose a type String with an operation ins(p, c, sid) where p is the position of insertion, c is the character to insert and sid is the identifier of the site that has generated the operation. We can write the following transformation function:

T(ins(${\displaystyle p_{1},c_{1},sid_{1}}$),ins(${\displaystyle p_{2},c_{2},sid_{2}}$)) :-
 if (${\displaystyle p_{1}<p_{2}}$) return ins(${\displaystyle p_{1},c_{1},sid_{1}}$)
 else if (${\displaystyle p_{1}=p_{2}}$ and ${\displaystyle sid_{1}<sid_{2}}$) return ins(${\displaystyle p_{1},c_{1},sid_{1}}$)
 else return ins(${\displaystyle p_{1}+1,c_{1},sid_{1}}$)

${\displaystyle T^{-1}}$(ins(${\displaystyle p_{1},c_{1},sid_{1}}$),ins(${\displaystyle p_{2},c_{2},sid_{2}}$)) :-
 if (${\displaystyle p_{1}<p_{2}}$) return ins(${\displaystyle p_{1},c_{1},sid_{1}}$)
 else if (${\displaystyle p_{1}=p_{2}}$ and ${\displaystyle sid_{1}<sid_{2}}$) return ins(${\displaystyle p_{1},c_{1},sid_{1}}$)
 else return ins(${\displaystyle p_{1}-1,c_{1},sid_{1}}$)

Some OT systems use both IT and ET functions, and some use only IT functions. The complexity of OT function design is determined by various factors:

• the functionality of the OT system: whether the OT system supports do (consistency maintenance), undo, locking,[22] awareness, application sharing,[19][23][24][25] etc.;
• the correctness responsibility in the OT system: what transformation properties (CP1/TP1, CP2/TP2, IP2, IP3, RP) to meet; whether ET is used;
• the operation model of the OT system: whether the OT operation model is generic (e.g. primitive insert, delete, update), or application-specific (all operations of the target application); and
• the data model of the OT system: whether the data in each operation is character-wise (an individual object), string-wise (a sequence of objects), hierarchical, or other structures.

Various transformation properties for ensuring OT system correctness have been identified. These properties can be maintained by either the transformation control algorithm[4][5][13][20][26][27] or by the transformation functions.[28] Different OT system designs have different division of responsibilities among these components. The specifications of these properties and preconditions of requiring them are given below.

Convergence properties

Illustration of the TP1 property

Illustration of the TP2 property

The following two properties are related to achieving convergence.

• CP1/TP1: For every pair of concurrent operations ${\displaystyle op_{1}}$ and ${\displaystyle op_{2}}$ defined on the same state, the transformation function T satisfies CP1/TP1 property if and only if: ${\displaystyle op_{1}\circ T(op_{2},op_{1})\equiv op_{2}\circ T(op_{1},op_{2})}$ where ${\displaystyle op_{i}\circ op_{j}}$ denotes the sequence of operations containing ${\displaystyle op_{i}}$ followed by ${\displaystyle op_{j}}$;and where ${\displaystyle \equiv }$ denotes equivalence of the two sequences of operations. CP1/TP1 precondition: CP1/TP1 is required only if the OT system allows any two operations to be executed in different orders.
• CP2/TP2: For every three concurrent operations ${\displaystyle op_{1},op_{2}}$ and ${\displaystyle op_{3}}$ defined on the same document state, the transformation function T satisfies CP2/TP2 property if and only if: ${\displaystyle T(op_{3},op_{1}\circ T(op_{2},op_{1}))=T(op_{3},op_{2}\circ T(op_{1},op_{2}))}$. CP2/TP2 stipulates equality between two operations transformed with regard to two equivalent sequences of operations: the transformation of ${\displaystyle op_{3}}$ against the sequence of operation ${\displaystyle op_{2}}$ followed by ${\displaystyle T(op_{1},op_{2})}$ must give the same operation as the transformation of ${\displaystyle op_{3}}$ against the sequence formed by ${\displaystyle op_{1}}$ and ${\displaystyle T(op_{2},op_{1})}$. CP2/TP2 precondition: CP2/TP2 is required only if the OT systems allows two operations ${\displaystyle op_{1}}$ and ${\displaystyle op_{2}}$ be IT-transformed in two different document states (or contexts).

Various OT control algorithms have been designed for OT systems with different capabilities and for different applications. The complexity of OT control algorithm design is determined by multiple factors. A key differentiating factor is whether an algorithm is capable of supporting concurrency control (do) and/or group undo.[3][8][12][27][29] In addition, different OT control algorithm designs make different tradeoffs in:

• assigning correctness responsibilities among the control algorithm and transformation functions, and
• time-space complexity of the OT system.

Most existing OT control algorithms for concurrency control adopt the theory of causality/concurrency as the theoretical basis: causally related operations must be executed in their causal order; concurrent operations must be transformed before their execution. However, it was well known that concurrency condition alone cannot capture all OT transformation conditions.[3][4][5][8][30] In a recent work, the theory of operation context has been proposed to explicitly represent the notion of a document state, which can be used to formally express OT transformation conditions for supporting the design and verification of OT control algorithms.[27]

The following table gives an overview of some existing OT control/integration algorithms

A continuous total order is a strict total order where it is possible to detect a missing element i.e. 1,2,3,4,... is a continuous total order, 1,2,3,5,... is not a continuous total order.

The transformation-based algorithms proposed in [10][11] are based on the alternative consistency models "CSM" and "CA" as described above. Their approaches differ from those listed in the table. They use vector timestamps for causality preservation. The other correctness conditions are "single-"/"multi-" operation effects relation preservation or "admissibility" preservation. Those conditions are ensured by the control procedure and transformation functions synergistically. There is no need to discuss TP1/TP2 in their work. Hence they are not listed in the above table.

There exist some other optimistic consistency control algorithms that seek alternative ways to design transformation algorithms, but do not fit well with the above taxonomy and characterization. For example, Mark and Retrace[33]

The correctness problems of OT led to introduction of transformationless post-OT schemes, such as WOOT,[34] Logoot[35] and Causal Trees (CT).[36] "Post-OT" schemes decompose the document into atomic operations, but they workaround the need to transform operations by employing a combination of unique symbol identifiers, vector timestamps and/or tombstones.

While the classic OT approach of defining operations through their offsets in the text seems to be simple and natural, real-world distributed systems raise serious issues. Namely, that operations propagate with finite speed, states of participants are often different, thus the resulting combinations of states and operations are extremely hard to foresee and understand. As Li and Li put it, "Due to the need to consider complicated case coverage, formal proofs are very complicated and error-prone, even for OT algorithms that only treat two characterwise primitives (insert and delete)".[37]

Similarly, Joseph Gentle who is a former Google Wave engineer and an author of the Share.JS library wrote, "Unfortunately, implementing OT sucks. There's a million algorithms with different tradeoffs, mostly trapped in academic papers. […] Wave took 2 years to write and if we rewrote it today, it would take almost as long to write a second time."[38] But later he amends his comment with "I no longer believe that wave would take 2 years to implement now - mostly because of advances in web frameworks and web browsers." [39]

For OT to work, every single change to the data needs to be captured: "Obtaining a snapshot of the state is usually trivial, but capturing edits is a different matter altogether. […] The richness of modern user interfaces can make this problematic, especially within a browser-based environment." An alternative to OT is differential synchronization.[40]

Another alternative to OT is using sequence types of conflict-free replicated data type.

• Data synchronization
• Collaborative real-time editors
• Conflict-free replicated data types
• Consistency models
• Optimistic replication

• OTFAQ: Operational Transformation Frequently Asked Questions and Answers
• SIGCE: Special Interest Group of Collaborative Editing
• International Workshop on Collaborative Editing Systems
• Distributed System Online - Collaborative editing
• Simple explanation of OT in Google Docs
• Basics of OT in the Open Coweb Framework