Operational transformation

"Operation Transformation" redirects here. For the cross-media event, see Operation Transformation (TV series).

Operational transformation (OT) is a technology for supporting a range of collaboration functionalities in advanced groupware systems. OT was originally invented for consistency maintenance and concurrency control in collaborative editing of plain text documents. Two decades of research has significantly extended its capabilities and expanded its applications 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, collaborative computer-aided media design tools, mobile, p2p, and distributed computing. Recently, OT has been adopted as a core technique behind its collaboration features in Google Wave, which took OT to a new range of web-based applications.

History

Operational Transformation was pioneered by C. Ellis and S. Gibbs in the GROVE (GRoup Outtie Viewing Edit) 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 of Collaborative Editing (SIGCE) 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.

System Architecture

Collaborative systems using OT typically adopts a replicated architecture for the storage of shared documents to ensure good responsiveness in high latency environments, such as the Internet. The shared documents are replicated at the local storage of each collaborating site, so editing operations can be performed at local sites immediately and then propagated to remote sites. Remote editing operations arriving at a local site are typically transformed and then executed. The transformation ensures that an application-dependent consistency criteria is achieve across all sites. The lock-free, nonblocking property of OT makes the local response time not sensitive to networking latencies. As a result, OT is particularly good for implementing collaboration features such as group editing in the Web/Internet context.

Basics

Basics of 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: O1 = Insert[0, “x”] (to insert character “x” at position “0”), and 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” shall delete the correct character “c” and the document becomes “xab”. However, if O2 is executed without transformation, then it shall incorrectly delete 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.

Consistency Models

One functionality of OT is to support consistency maintenance in collaborative editing systems, so consistency criteria required by collaborative editing systems is a major issue. 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, two consistency properties have been required for collaborative editing systems:

• Precedence property: 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 (i.e., all generated operations have been executed at all sites).

Since concurrent operations may be executed in different orders and editing operations are not commutative in general, copies of the document at difference sites may diverge (inconsistent). The first OT algorithm was proposed in to achieve convergence in a group text editor; the state-vector (or vector clock in classic distributed computing) was used to preserve the precedence property.

The CCI Model

The CCI model was proposed as a general framework for consistency management in collaborative editing systems. Under the CCI model, three consistency properties are grouped together:

• Causality Preservation : the same as the precedence property in the CC Model.
• Convergence: the same as the convergence property 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 operatin 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 criteria 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 (OT, multi-versioning, serialization, undo/redo). It was not intended for correctness verification for techniques (e.g. OT) 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

Operation intention was not formally defined in CCI model. The SDT and LBT approaches tried to formalise the notion of intention by means of the effects relation concept. The effects relation between two operations relies on the fact that there exists a total order relation between the target characters of the operations. The consistency model proposed by these approaches consist of the following properties:

• 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

Recently, a well-formalized correctness model CA is proposed, which 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 (object ordering) 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 by Li and Li.

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 (or Integration) Algorithms from the low-level Transformation Functions.

Division of functionality in an OT system

Division of functionality in an OT system

The transformation control algorithm is concerned with determining 1) which operation should be transformed against a causally-ready new operation and 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 systems 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.

How to Design OT Algorithms

In general, there are two approaches to developing OT algorithms. In the more widely understood approach , they reuse a generic control procedure and focus on design of application-specific transformation functions. Most works along this line require that the (inclusion) transformation functions satisfy two properties, TP1 and TP2, which essentially say that the functions work in all possible cases (or arbitrary transformation paths). This has turned out extremely difficult to achieve over the past 10+ years' of design practices in the research community. In the most recent work of Sun et al , they have chosen to take a different design approach.

The other relatively new approach was proposed by Li et al. In their approach, an OT algorithm is correct if it satisfies two well-formalized correctness criteria: (1) causality preservation, and (2) admissibility preservation. As long as these two criteria are satisfied, the data replicas converge (with additional constraint) 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 simple 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 causality and admissibility preservation.

Li et al's work considers that satisfying TP1/TP2 conditions is a hard path to success. The two transformation properties, TP1 and TP2, were important in the early days of OT because they were debatably considered as sufficient conditions to convergence. Therefore proving TP2 at most shows that an OT algorithm achieves convergence. It is well known due to Sun et al that convergence is not enough in collaborative applications such as group editors. The converged data must be further constrained by conditions such as intention preservation and admissibility . In the new frameworks , they do not discuss TP1/TP2 at all because they no longer require the transformation functions work in all possible cases (i.e., arbitrary transformation paths). This requirement would make the design of transformation functions (and hence OT algorithms) unnecessarily complicated.

OT Data and Operation Models

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 is a single linear address space; and its operation model consists of two primitive operations: character-wise insert and delete. The basic data mode has been extended to include a third primitive operation update to support collaborative Word document processing in and 3D model editing. The basic OT data model has been extended into a hierarchy of multiple linear addressing domains, which is capable of modeling a broad range of documents. A data adaption process is often required to map application-specific data models to an OT-compliant data model.

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. 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. For an application with m different operations, mxm transformation functions are needed for supporting this application. In this approach, transformation functions are application-specific and cannot be reused in different applications.

Every OT system is based on two underlying models: 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 is a single linear address space from which all data objects (i.e., a string of characters) can be accessed. Addresses in this linear address space range from 0 to N − 1, where N is total number of characters in the document. The operation model of the first OT system consists of two primitive operations (PO): character-wise insert and delete. OT functions for these two POs can be found in .

OT Functions

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:

1. one is Inclusion Transformation (or Forward Transformation): IT(Oa, Ob) or $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; and
2. the other is Exclusion Transformation (or Backward Transformation): ET (Oa, Ob) or $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 the character to insert and sid the identifier of the site that has generated the operation. We can write the following transformation function:

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

$T^{-1}$(ins($p_{1},c_{1},sid_{1}$),ins($p_{2},c_{2},sid_{2}$)) :-
  if ($p_{1}<p_{2}$) return ins($p_{1},c_{1},sid_{1}$)
  else if ($p_{1}=p_{2}$ and $sid_{1}<sid_{2}$) return ins($p_{1},c_{1},sid_{1}$)
  else return ins($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:

1. the functionality of the OT system: whether the OT system supports do (consistency maintenance), undo, locking, awareness, application sharing , etc.;
2. the correctness responsibility in the OT system: what transformation properties (CP1/TP1, CP2/TP2, IP2, IP3, RP) to meet; whether ET is used;
3. the operation model of the OT system: whether the OT operation model is generic and small (insert, delete, update), or application-specific (all operations of the target application); and
4. 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 structure.

Transformation Properties

Various transformation properties for ensuring OT system correctness have been identified. These properties can be maintained by either the transformation control algorithm or by the transformation function. Different OT system designs have different division of responsibilities among these components. The specifications of these properties and pre-conditions of requiring them are given below.

Convergence Properties

File:OTtp1.jpg

Illustration of the TP1 property

File:OTtp2.jpg

Illustration of the TP2 property

The following two properties are related to achieving convergence.

1. CP1/TP1: For every pair of concurrent operations $op_{1}$ and $op_{2}$ defined on the same state, the transformation function T satisfies CP1/TP1 property if and only if: $op_{1}\circ T(op_{2},op_{1})\equiv op_{2}\circ T(op_{1},op_{2})$ where where $op_{i}\circ op_{j}$ denotes the sequence of operations containing $op_{i}$ followed by $op_{j}$;and where $\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.
2. CP2/TP2: For every three concurrent operations $op_{1},op_{2}$ and $op_{3}$ defined on the same document state, the transformation function T satisfies CP2/TP2 property if and only if: $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 $op_{3}$ against the sequence of operation $op_{2}$ followed by $T(op_{1},op_{2})$ must give the same operation as the transformation of $op_{3}$ against the sequence formed by $op_{1}$ and $T(op_{2},op_{1})$. CP2/TP2 Precondition: CP2/TP2 is required only if the OT systems allows two operations $op_{1}$ and $op_{2}$ be IT-transformed in two different document states (or contexts).

Inverse Properties

The following three properties are relate to achieving the desired group undo effect. They are:

• IP1: Given any document state S and the sequence $op\circ {\overline {op}}$, we have $S\circ op\circ {\overline {op}}=S$, which means the sequence $op\circ {\overline {op}}$ is equivalent to a single identity operation I with respect to the effect on the document state. This property is required in an OT system for achieving the correct undo effect, but is not related to IT functions.
• IP2: The property IP2 expresses that the sequence $op\circ {\overline {op}}$ has no effect on the transformation of other operations. The transformation functions satisfy IP2 if and only if: $T(op_{x},op\circ {\overline {op}})=op_{x}$, which means that the outcome of transforming $op_{x}$ against the sequence $op\circ {\overline {op}}$ is equivalent to the outcome of transforming $op_{x}$ against the identity operation I. IP2-Precondition: IP2 is required only if the OT systems allows an operation $op_{x}$ to be transformed against a pair of do and undo operations $op\circ {\overline {op}}$, one-by-one.
• IP3: Given two concurrent operations $op_{1}$ and $op_{2}$ defined on the same document state (or context), if ${\overline {op_{1}}}'=T({\overline {op_{1}}},T(op_{2},op1))$ and ${\overline {op_{1}'}}={\overline {T(op_{1},op_{2})}}$. The transformation functions satisfy the property IP3 if and only if ${\overline {op_{1}}}'={\overline {op_{1}'}}$, which means that the transformed inverse operation ${\overline {op_{1}}}'$ is equal to the inverse of the transformed operation ${\overline {op_{1}'}}$. IP3-Precondition: IP3 is required only if the OT system allows an inverse operation ${\overline {op_{1}}}$ to be transformed against an operation $op_{2}$ that is concurrent and defined on the same document state as (or context-independent of) $op_{1}$.

OT Control (Integration) Algorithms

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 . In addition, different OT control algorithm designs make different tradeoffs in:

1. assigning correctness responsibilities among the control algorithm and transformation functions: transformation properties can often be satisfied either at the control algorithm level or at the transformation function level with different complexity tradeoffs; and
2. time-space complexity of the OT system.

Most existing OT control algorithms for concurrency control adopts 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 essential OT transformation conditions. In a recent work, the theory of operation context has been established to explicitly represent the notion of a document state, which can be used to formally express essential OT transformation conditions for supporting the design and verification of correct and efficient OT control algorithms.

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

OT Control/Integration Algorithms(Systems)	Required Transformation Function Types	Support OT-based Do?	Support OT-based Undo?	Transformation Properties Supported By Control Algorithm	Transformation Properties Supported By Transformation Functions	Transformation Ordering and Propagation Constraints	Timestamp
dOPT(GROVE)	T (IT)	Yes	No	None	CP1/TP1, CP2/TP2	Causal order	State vector
selective-undo(DistEdit)	Transpose (IT and ET)	No	Selective Undo	NA	CP1/TP1, CP2/TP2, RP, IP1, IP2, IP3	Causal order	??
adOPTed(multiedit)	LTransformation (IT)	Yes	Chronological Undo	IP2, IP3	CP1/TP1, CP2/TP2, IP1	Causal order	State vector
Jupiter	xform (IT)	Yes	No	CP2/TP2	CP1/TP1	Causal order + Central transformation server	Scalar
Google Wave OT	transform and composition(IT)	Yes	??	CP2/TP2	CP1/TP1	Causal order + Central transformation server + stop'n'wait propagation protocol	Scalar
GOT(REDUCE)	IT and ET	Yes	No	CP1/TP1, CP2/TP2	None	Causal order + Discontinuous total order	State vector
GOTO(REDUCE, CoWord, CoPPT, CoMaya)	IT and ET	Yes	No	None	CP1/TP1, CP2/TP2	Causal order	State vector
AnyUndo(REDUCE, CoWord, CoPPT, CoMaya)	IT and ET	Yes	undo any operation	IP2, IP3, RP	IP1, CP1/CP2, TP1/TP2	Causal order	State vector
SLOT(NICE)	IT	Yes	No	CP2/TP2	CP1/TP1	Causal order + Central transformation server	Scalar
COT	IT	Yes	Undo any operation	CP2/TP2, IP2, IP3	CP1/TP1, IP1	Causal order + Discontinuous total order	Context vector
TIBOT	IT	Yes	No	CP2/TP2	CP1/TP1	Causal order	Scalar
SOCT4	Forward transformation (IT)	Yes	No	CP2/TP2	CP1/TP1	Causal order + Continuous Total Order	Scalar
SOCT2	Forward Transformation(IT) and Backward Transformation(ET)	Yes	No	CP1/TP1, CP2/TP2, RP	Causal order	State vector
MOT2	Forward transformation (IT)	Yes	No	??	CP1/TP1	??	??

A continuous total order is a strict total order where it 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. A continuous total order is costly to maintain in a distributed system.

Criticisms to OT

• Transformation functions are difficult to write and prove.

This criticism can be mitigated along with the development of the OT framework. They just need to use the original simple transformation functions proposed in Ellis and Gibbs 1989. In their approach, transformation functions do not need to satisfy the above-explained TP2 condition at all. That's why they can be as simple as they should be.

• What is the formal definition for OT "intentions"?

In the alternative correctness criteria proposed in the CA model, "intention" is no longer a concern. What is important here is really that an OT algorithm can be proved against well-formalized correctness criteria, whether it is called "admissibility" or "intention preservation". Some researchers believe that the notion of admissibility is a reasonable definition of intention preservation. However, this is to be agreed upon by the research community.

• There are many other ways to merge data and OT is too complex.

OT is not complex in terms of efficiency. OT looks complicated to people who are not familiar with the topic. It is generally true that it takes much time and effort for a person to learn an unfamiliar subject. Being complex and looking complicated are two different concepts in computer science.

• Is the theoretical framework completely sound?

Yes! The theoretical frameworks proposed by Li et al include both well-formalized correctness criteria and sound approaches to design OT algorithms and prove their correctness. Their recent work also did quite some optimizations to improve the efficiency of OT algorithms so that they can work well on resource-constrained devices and platforms such as cell phones and browsers.

OT Software

• Collaborative plain text editors (One dimensional documents)
  • Subethaedit (commercial)
  • Ace (free, open-source)
  • Gobby (free, open-source)
  • MoonEdit(free for non-commerical use, open source)
• Collaborative productivity applications (Two dimensional documents)
  • CoWord is a Collaborative real-time word processor based on MicroSoft word
  • CoPowerPoint is a Collaborative real-time presentition editorr= based on MicroSoft Powerpoint
• Collaborative computer-aided media design tools (Three-dimensional documents)
  • CoMaya is a real-time collaborative 3D design tool based on Autodesk Maya.
• Web-based applications*
  • Google Wave uses OT as part of the Google Wave Federation Protocol. The Google wave OT algorithm is based on Jupiter
• Version control systems
  • So6 is a free open-source version control system integrated in the LibreSource platform.

Relevant Online Talks

• Google Tech Talk: Issues and Experiences in Designing Real-time Collaborative Editing Systems
• Presentation of CoWord technology to Microsoft Research (Video)

See also

• Optimistic Replication
• Data synchronization
• Collaborative Editing
• Consistency models

External links

• International Workshop on Collaborative Editing Systems
• Distributed System Online - Collaborative editing