View source for Operational transformation

{{Short description|Concurrency control method for collaborative software}}
{{Redirect|Operation Transformation|the cross-media event|Operation Transformation (TV series)}}
'''Operational transformation''' ('''OT''') 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.<ref>{{Cite web|url=https://www3.ntu.edu.sg/home/czsun/projects/otfaq/|title=OT FAQ|last=Sun|first=Chengzheng|archive-url=https://web.archive.org/web/20200623064915/https://www3.ntu.edu.sg/home/czsun/projects/otfaq/|archive-date=2020-06-23}}</ref> In 2009 OT was adopted as a core technique behind the collaboration features in [[Apache Wave]] and [[Google Docs]].

==History==
Operational Transformation was pioneered by [[Clarence Ellis (computer scientist)|C. Ellis]] and S. Gibbs<ref name="Ellis1989">{{cite journal|author=Ellis, C.A.|author2=Gibbs, S.J.|year=1989|title=Concurrency control in groupware systems|journal=ACM SIGMOD Record|volume=18|issue=2|pages=399–407|doi=10.1145/67544.66963|citeseerx=10.1.1.465.2026|s2cid=6488575}}</ref> in the GROVE (GRoup Outline Viewing Edit) system in 1989. Several years later, some correctness issues were identified and several approaches<ref name=Ressel1996>
{{cite conference
|author = Ressel, Matthias and Nitsche-Ruhland, Doris and Gunzenhäuser, Rul
| title = An integrating, transformation-oriented approach to concurrency control and undo in group editors
| conference = CSCW '96: Proceedings of the 1996 ACM conference on Computer supported cooperative work
| year = 1996
| pages = 288–297
|doi = 10.1145/240080.240305
}}
</ref><ref name=suntochi1998>{{cite journal
 | author = Chengzheng Sun |author2=Xiaohua Jia |author3=Yanchun Zhang |author4=Yun Yang |author5=David Chen 
 | year = 1998
 | title = Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems
 | journal = ACM Trans. Comput.-Hum. Interact.
 | volume = 5
 | issue = 1
 | pages = 63–108
 | doi = 10.1145/274444.274447
 |citeseerx=10.1.1.56.1251 |s2cid=14447070 }}</ref><ref name=nichols1995>{{Cite journal
 |title        = High-latency, low-bandwidth windowing in the Jupiter collaboration system
 |url          = http://ftp.lambda.moo.mud.org/pub/MOO/papers/JupiterWin.ps
 |year         = 1995
 |journal      = Proceedings of the 8th Annual ACM Symposium on User Interface and Software Technology
 |pages        = 111–120
 |last1        = Nichols
 |first1       = D.A.
 |last2        = Curtis
 |first2       = P.
 |last3        = Dixon
 |first3       = M.
 |last4        = Lamping
 |first4       = J.
 |access-date  = 2009-09-27
 |archive-url  = https://web.archive.org/web/20151130183552/http://ftp.lambda.moo.mud.org/pub/MOO/papers/JupiterWin.ps
 |archive-date = 2015-11-30
 |url-status     = live
}}</ref><ref name=suncscw1998>
{{cite conference
 | author = Sun, C.
 |author2=Ellis, C.
 | year = 1998
 | title = Operational transformation in real-time group editors: issues, algorithms, and achievements
 | conference = Proceedings of the 1998 ACM conference on Computer supported cooperative work
 | pages = 59–68
 | publisher = ACM Press New York, NY, USA
 | url = http://portal.acm.org/citation.cfm?id=289444.289469
 }}</ref> 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<ref>{{Cite web|url=http://cooffice.ntu.edu.sg/sigce/|title=SIGCE - An International Special Interest Group on Collaborative Editing|website=cooffice.ntu.edu.sg|access-date=2020-01-10|archive-url=https://archive.today/20121224222231/http://cooffice.ntu.edu.sg/sigce/|archive-date=2012-12-24|url-status=dead}}</ref> 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==
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 (computer science)|lock-free]], [[Blocking (computing)|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 ([[Invariant (computer science)|invariant]]s) 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 [[www|the web]].

==Basics==

[[Image:basicot.png|250px|right|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:

# O1 = Insert[0, "x"] (to insert character "x" at position "0")
# 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.

==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",<ref name=Ellis1989/> two consistency properties are required for collaborative editing systems:

* '''C'''ausality 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.
*'''C'''onvergence: 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 different sites may diverge (inconsistent). The first OT algorithm was proposed in Ellis and Gibbs's paper<ref name=Ellis1989/> 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 consistency management in collaborative editing systems.<ref name=suntochi1998/><ref name=suntochi2002/> Under the CCI model, three consistency properties are grouped together:
* '''C'''ausality preservation : the same as in the CC model.
* '''C'''onvergence: the same as in the CC model.
* '''I'''ntention 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 (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,<ref name=suntochi1998/> 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<ref name=li2004sdt>{{cite conference
 | author = Du Li
 |author2=Rui Li
 | year = 2004
 | title = Preserving Operation Effects Relation in Group Editors
 | conference = Proceedings of the ACM CSCW'04 Conference on Computer-Supported Cooperative Work
 | pages = 457–466
 | publisher = ACM Press New York, NY, USA
 }}</ref> and LBT<ref name=Li2007>{{cite journal
 | author = Rui Li
 |author2=Du Li
 | year = 2007
 | title = A New Operational Transformation Framework for Real-Time Group Editors
 | location = IEEE Transactions on Parallel and Distributed Systems
 | volume = 18
 | pages = 307–319
 | doi = 10.1109/TPDS.2007.35
 | journal = IEEE Transactions on Parallel and Distributed Systems
 | issue = 3 
 |s2cid=18822760
 }}</ref> 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:
* '''''C'''ausality'': the same definition as in CC model
* '''''S'''ingle-operation effects'': the effect of executing any operation in any execution state achieves the same effect as in its generation state
* '''''M'''ulti-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 (i.e., new objects inserted by two current operations at the same position). 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'''.<ref name=Li2005b>{{cite conference
 | author = Rui Li
 |author2=Du Li
 | year = 2005
 | title = Commutativity-Based Concurrency Control in Groupware
 | conference = Proceedings of the First IEEE Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom'05)
 }}</ref> The CA model includes two aspects: 
* '''''C'''ausality'': the same definition as in CC model
* '''''A'''dmissibility'': 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.<ref name=Li2005b/> 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<ref name=Ellis1989/><ref name=Ressel1996/><ref name=suntochi1998/><ref name=nichols1995/><ref name=prakashtochi1994/><ref name=Vidot2000/> is to separate the high-level transformation control (or integration) algorithms from the low-level transformation functions.
{| class="wikitable floatright" style="text-align:center;" width="400"
|'''OT Control Algorithms'''<br />(determine which operations are transformed against others according to their concurrency/context relations)
|-
|'''OT properties and conditions'''<br />(divide responsibilities between algorithms and functions)
|-
|'''OT Transformation Functions'''<br />(determine how to transform a pair of primitive operations according to operation types, positions, and other parameters)
|}
The transformation control algorithm is concerned with determining:
# Which operation should be transformed against a causally ready new operation
# 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.<ref name=Li2005b/> In their approach, an OT algorithm is correct if it satisfies two formalized correctness criteria:
# Causality preservation
# 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.

==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<ref name=Ellis1989/> 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<ref name=suncscw2004>
{{cite conference
|author = D. Sun and S. Xia and C. Sun and D. Chen
|title  = Operational transformation for collaborative word processing
|conference = Proc. of the ACM Conf. on Computer-Supported Cooperative Work
|pages    = 437–446
|year     = 2004
}}
</ref> and 3D model editing.<ref name=agustinacscw2008>{{cite conference
|author= Agustina and F. Liu and S. Xia and H. Shen and C. Sun
|title= CoMaya: Incorporating advanced collaboration capabilities into {3D} digital media design tools
|conference= Proc. of ACM Conf. on Computer-Supported Cooperative Work
|pages= 5–8
|date=November 2008
}}</ref> The basic OT data model has been extended into a hierarchy of multiple linear addressing domains,<ref name=daviscscw2001>
{{cite conference
|author = Davis, Aguido Horatio and Sun, Chengzheng and Lu, Junwei
|title = Generalizing operational transformation to the standard general markup language
|conference = CSCW '02: Proceedings of the 2002 ACM conference on Computer supported cooperative work
|year = 2002
|pages = 58–67
|location = New Orleans, Louisiana, USA
|doi = 10.1145/587078.587088
}}</ref><ref name=ignatecscw2003>{{cite conference
 |author     = Claudia-Lavinia Ignat
 |author2    = Moira C. Norrie
 |year       = 2003
 |title      = Customizable collaborative editor relying on treeOPT algorithm
 |conference  = ECSCW'03: Proceedings of the eighth conference on European Conference on Computer Supported Cooperative Work
 |pages      = 315–334
 |publisher  = Kluwer Academic Publishers
 |doi = 10.1007/978-94-010-0068-0_17
 }}</ref><ref name=ignatjcscw2008>{{cite journal
|author     = Claudia-Lavinia Ignat
 |author2    = Moira C. Norrie
|title = Multi-level Editing of Hierarchical Documents
|journal = Computer Supported Cooperative Work (CSCW) 
|volume = 17
|year = 2008
|issue = 5–6
|pages = 423–468
|doi = 10.1007/s10606-007-9071-2
|s2cid = 42752275
}}</ref> 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.<ref name=suntochi2006/><ref name=googlewave>{{cite web|title=Google Wave Operational Transform|url=http://www.waveprotocol.org/whitepapers/operational-transform|access-date=2009-05-29|archive-url=https://web.archive.org/web/20090531063923/http://www.waveprotocol.org/whitepapers/operational-transform|archive-date=2009-05-31|url-status=dead}}</ref>

There exist two approaches to supporting application level operations in an OT system:
# Generic operation model approach: which is to devise transformation functions for three primitive operations: insert, delete, and update.<ref name=suntochi2006/> 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.
# Application-specific operation model approach: which is to devise transformation functions for each pair of application operations.<ref name=googlewave/><ref name=Palmer1998>{{cite conference
 | author = Christopher R. Palmer 
 |author2=Gordon V. Cormack 
 | year = 1998
 | title = Operation transforms for a distributed shared spreadsheet
 | conference = CSCW '98: Proceedings of the 1998 ACM conference on Computer supported cooperative work
 | pages = 69–78
 | publisher = ACM Press
 |doi=10.1145/289444.289474
 | doi-access = free
 }}</ref> 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.

==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:
* Inclusion transformation (or forward transformation): {{nowrap|IT(''O{{sub|a}}, O{{sub|b}}'')}} or {{nowrap|''T''(''op''{{sub|1}},''op''{{sub|2}})}}, which transforms operation ''O{{sub|a}}'' against another operation ''O{{sub|b}}'' in such a way that the impact of ''O{{sub|b}}'' is effectively included. This is, for example, the case of two insertions at different nodes.
* Exclusion transformation (or backward transformation): {{nowrap|ET(''O{{sub|a}}, O{{sub|b}}'')}} or {{nowrap|''T''{{issup|&minus;1}}(''op''{{sub|1}},''op''{{sub|2}})}}, which transforms operation ''O{{sub|a}}'' against another operation ''O{{sub|b}}'' in such a way that the impact of ''O{{sub|b}}'' is effectively excluded. This is, for example, the case of an insertion and a deletion at different nodes<ref>{{cite web |last1=Kagorskii |first1=Anton |title=Operational Transformations as an algorithm for automatic conflict resolution |url=https://medium.com/coinmonks/operational-transformations-as-an-algorithm-for-automatic-conflict-resolution-3bf8920ea447 |website=medium.com |access-date=21 December 2021}}</ref>

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 inclusion transformation function:<ref name=":0">{{Cite journal |date=2006-11-07 |title=Tombstone Transformation Functions for Ensuring Consistency in Collaborative Editing Systems |url=https://inria.hal.science/inria-00109039/document |journal=IEEE Conference on Collaborative Computing: Networking, Applications and Worksharing}}</ref>

 ''T''(ins({{nowrap|''p''{{sub|1}},''c''{{sub|1}},''sid''{{sub|1}}}}),ins({{nowrap|''p''{{sub|2}},''c''{{sub|2}},''sid''{{sub|2}}}})) :-
  if ({{nowrap|''p''{{sub|1}} < ''p''{{sub|2}}}}) return ins({{nowrap|''p''{{sub|1}},''c''{{sub|1}},''sid''{{sub|1}}}})
  else if ({{nowrap|''p''{{sub|1}}{{=}}''p''{{sub|2}}}} and {{nowrap|''sid''{{sub|1}} < ''sid''{{sub|2}}}}) return ins({{nowrap|''p''{{sub|1}},''c''{{sub|1}},''sid''{{sub|1}}}})
  else return ins({{nowrap|''p''{{sub|1}}+1,''c''{{sub|1}},''sid''{{sub|1}}}})

We can also write the following exclusion transformation function:<ref name=":0" />

 {{nowrap|''T''{{issup|&minus;1}}}}(ins({{nowrap|''p''{{sub|1}},''c''{{sub|1}},''sid''{{sub|1}}}}),ins({{nowrap|''p''{{sub|2}},''sid''{{sub|2}}}})) :-
  if ({{nowrap|''p''{{sub|1}} < ''p''{{sub|2}}}}) return ins({{nowrap|''p''{{sub|1}},''c''{{sub|1}},''sid''{{sub|1}}}})
  else if ({{nowrap|''p''{{sub|1}}{{=}}''p''{{sub|2}}}} and {{nowrap|''sid''{{sub|1}} < ''sid''{{sub|2}}}}) return ins({{nowrap|''p''{{sub|1}},''c''{{sub|1}},''sid''{{sub|1}}}})
  else return ins({{nowrap|''p''{{sub|1}}&minus;1,''c''{{sub|1}},''sid''{{sub|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,<ref name=sunpodc1999>{{cite conference
|author1=C. Sun  |author2=R. Sosic
 |name-list-style=amp |title = Optional Locking Integrated with Operational Transformation in Distributed Real-Time Group Editors
|conference= In Proc. of the 18th ACM Symposium on Principles of Distributed Computing
|pages = 43–52
|year = 1999
}}</ref> awareness, application sharing,<ref name=suntochi2006>{{cite journal
|author = C.Sun, S.Xia, D.Sun, D.Chen, H.Shen, and W.Cai
|title = Transparent adaptation of single-user applications for multi-user real-time collaboration
|journal = ACM Trans. Comput.-Hum. Interact.
|volume = 13
|year = 2006
|pages = 531–582
|doi = 10.1145/1188816.1188821
|issue = 4
|s2cid = 14184705
}}</ref><ref name=begoletochi1999>
{{cite journal
|author = Begole, James and Rosson, Mary Beth and Shaffer, Clifford A.
|title = Flexible collaboration transparency: supporting worker independence in replicated application-sharing systems
|journal = ACM Trans. Comput.-Hum. Interact.
|volume = 6
|year = 1999
|pages = 95–132
|doi = 10.1145/319091.319096
|issue = 2
|citeseerx = 10.1.1.23.1185
|s2cid = 17895848
}}</ref><ref name=licscw2002>{{cite conference 
|author1=Li, Du  |author2=Li, Rui
 |name-list-style=amp |title = Transparent sharing and interoperation of heterogeneous single-user applications
|conference= CSCW '02: Proceedings of the 2002 ACM conference on Computer supported cooperative work
|year = 2002
|pages = 246–255
|location = New Orleans, USA
}}
</ref><ref name=licscw2006>{{cite conference 
|author1=Li, Du  |author2=Lu, Jiajun
 |name-list-style=amp |title = A lightweight approach to transparent sharing of familiar single-user editors
|conference = CSCW '06: Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work
|year = 2006
|pages = 139–148
|location = Banff, Alberta, Canada
|doi = 10.1145/1180875.1180896
}}
</ref> 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.

==Transformation properties==
Various transformation properties for ensuring OT system correctness have been identified. These properties can be maintained by either the transformation control algorithm<ref name=suntochi1998/><ref name=nichols1995/><ref name=Vidot2000/><ref name=googlewave/><ref name=shencscw2002/><ref name=suntpds2009/> or by the transformation functions.<ref name=Oster>{{cite journal
 | author = Gerald Oster |author2=Pascal Molli |author3=Pascal Urso |author4=Abdessamad Imine
 | year = 2006
 | title = Tombstone Transformation Functions for Ensuring Consistency in Collaborative Editing Systems
 | journal = Procs. 2nd Intl. Conf. On Collaborative Computing: Networking, Appln. And Worksharing
 | url = http://hal.inria.fr/docs/00/10/90/39/PDF/OsterCollaborateCom06.pdf 
 | access-date = 2007-07-26
 }}</ref> 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===
[[File:OT TP1 property.jpg|thumb|right|Illustration of the TP1 property]]
[[File:OT TP2 property.jpg|thumb|right|Illustration of the TP2 property]] 
The following two properties are related to achieving convergence.

* '''CP1/TP1''': For every pair of concurrent operations <math>op_1</math> and <math>op_2</math> defined on the same state, the transformation function T satisfies CP1/TP1 property if and only if: <math> op_1 \circ T(op_2,op_1) \equiv op_2 \circ T(op_1,op_2) </math> where <math>op_i \circ op_j</math> denotes the sequence of operations containing <math>op_i</math> followed by <math>op_j</math>;and where <math>\equiv</math> 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 <math>op_1, op_2</math> and <math>op_3</math> defined on the same document state, the transformation function T satisfies CP2/TP2 property if and only if: <math>T(op_3, op_1 \circ T(op_2,op_1)) = T(op_3, op_2 \circ T(op_1,op_2))</math>. CP2/TP2 stipulates equality between two operations transformed with regard to two equivalent sequences of operations: the transformation of <math>op_3</math> against the sequence of operation <math>op_2</math> followed by <math>T(op_1,op_2)</math> must give the same operation as the transformation of <math>op_3</math> against the sequence formed by <math>op_1</math> and <math>T(op_2,op_1)</math>. '''CP2/TP2 precondition''': CP2/TP2 is required only if the OT systems allows two operations <math>op_1</math> and <math>op_2</math> be IT-transformed in two different document states (or contexts).

===Inverse properties===
The following three properties are related to achieving the desired group undo effect. They are:

* '''IP1''': Given any document state S and the sequence <math>op \circ \overline{op}</math>, we have <math>S \circ op \circ \overline{op} = S</math>, which means the sequence <math>op \circ \overline{op}</math> 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 <math>op \circ \overline{op}</math> has no effect on the transformation of other operations. The transformation functions satisfy IP2 if and only if: <math>T(op_x, op \circ \overline{op})=op_x</math>, which means that the outcome of transforming <math>op_x</math> against the sequence <math>op \circ \overline{op}</math> is equivalent to the outcome of transforming <math>op_x</math> against the identity operation I. '''IP2 precondition''': IP2 is required only if the OT systems allows an operation <math>op_x</math> to be transformed against a pair of do and undo operations <math>op \circ \overline{op}</math>, one-by-one.
* '''IP3''': Given two concurrent operations <math>op_1</math> and <math>op_2</math> defined on the same document state (or context), if <math>\overline{op_1}' = T(\overline{op_1}, T(op_2, op_1))</math> and <math>\overline{op_1'} = \overline{T(op_1, op_2)}</math>. The transformation functions satisfy the property IP3 if and only if <math>\overline{op_1}' = \overline{op_1'}</math>, which means that the transformed inverse operation <math>\overline{op_1}'</math> is equal to the inverse of the transformed operation <math>\overline{op_1'}</math>. '''IP3 precondition''': IP3 is required only if the OT system allows an inverse operation <math>\overline{op_1}</math> to be transformed against an operation <math>op_2</math> that is concurrent and defined on the same document state as (or context-equivalent to) <math>op_1</math>.

==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.<ref name=Ressel1996/><ref name=suntochi2002>{{cite journal 
|author = C. Sun
|title = Undo as concurrent inverse in group editors
|journal = ACM Trans. Comput.-Hum. Interact.
|volume = 9
|year = 2002
|pages = 309–361
|doi = 10.1145/586081.586085
|issue = 4
|s2cid = 47453660
}}</ref><ref name=prakashtochi1994/><ref name=suntpds2009/><ref name=resselgroup1999/> 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.<ref name=Ressel1996/><ref name=suntochi1998/><ref name=nichols1995/><ref name=suntochi2002/><ref name=Suleiman1998/> 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.<ref name=suntpds2009/>
 
The following table gives an overview of some existing OT control/integration algorithms

{| class="wikitable"
|-
! 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<ref name=Ellis1989/> (GROVE) 
|T (IT)
| {{Yes}}
| {{No}} 
| {{CNone|None}}
|CP1/TP1, CP2/TP2
|Causal order
|State vector
|-
|selective-undo<ref name=prakashtochi1994>{{cite journal
|author1=Prakash, Atul  |author2=Knister, Michael J.
 |name-list-style=amp |title = A framework for undoing actions in collaborative systems
|journal = ACM Trans. Comput.-Hum. Interact.
|volume = 1
|year = 1994
|pages = 295–330
|doi = 10.1145/198425.198427
|issue = 4
|citeseerx=10.1.1.51.4793
 |s2cid=10705127
 }}</ref> (DistEdit)
|Transpose (IT and ET)
| {{No}}
|Selective Undo
| {{N/A|N/A}}
|CP1/TP1, CP2/TP2, RP, IP1, IP2, IP3
|Causal order
| {{dunno}}
|-
|adOPTed<ref name=Ressel1996/><ref name=resselgroup1999>{{cite conference
|author1=M. Ressel  |author2=R. Gunzenhauser
 |name-list-style=amp |title = Reducing the Problems of Group Undo
|conference = Proc. of the ACM Conf. on Supporting Group Work
|pages = 131–139
|year = 1999
}}</ref> (JOINT EMACS)
|LTransformation (IT)
| {{Yes}}
|Chronological Undo
|IP2, IP3
|CP1/TP1, CP2/TP2, IP1
|Causal order 
|State vector
|-
|Jupiter<ref name=nichols1995/>
|xform (IT)
| {{Yes}}
| {{No}}
|CP2/TP2
|CP1/TP1
|Causal order + Central transformation server
|Scalar
|-
|Google Wave OT<ref name=googlewave/>
|transform and composition(IT)
| {{Yes}}
| {{No}}
|CP2/TP2
|CP1/TP1
|Causal order + Central transformation server + stop'n'wait propagation protocol
|Scalar
|-
| GOT<ref name=suntochi1998/> (REDUCE)
| IT and ET
| {{Yes}}
| {{No}}
| CP1/TP1, CP2/TP2
| {{CNone|None}}
| Causal order + Discontinuous total order
| State vector
|-
| GOTO<ref name=suncscw1998/> (REDUCE, [[CoWord]], CoPPT, CoMaya)
| IT and ET
| {{Yes}}
| {{No}}
| {{CNone|None}}
| CP1/TP1, CP2/TP2
| Causal order
| State vector
|-
| AnyUndo<ref name=suntochi2002/> (REDUCE, [[CoWord]], CoPPT, CoMaya)
| IT and ET
| {{No}}
| {{any|Undo any operation}}
| IP2, IP3, RP
| IP1, CP1/TP1, CP2/TP2
| Causal order
| State vector
|-
| SCOP<ref name=shencscw2002>
{{cite conference
|author1=Shen, Haifeng  |author2=Sun, Chengzheng
 |name-list-style=amp | title = Flexible notification for collaborative systems
| conference = CSCW '02: Proceedings of the 2002 ACM conference on Computer supported cooperative work
| year = 2002
| pages = 77–86
| doi = 10.1145/587078.587090
}}</ref> (NICE)
| IT
| {{Yes}}
| {{No}}
| CP2/TP2
| CP1/TP1
| Causal order + Central transformation server
| Scalar
|-
| COT <ref name=suntpds2009>{{cite journal
 |author1       = D. Sun
 |author2       = C. Sun
 |name-list-style = amp
 |title         = Context-based Operational Transformation for Distributed Collaborative Editing Systems
 |journal       = IEEE Transactions on Parallel and Distributed Systems
 |volume       = 20
 |issue       = 10
 |pages       = 1454–1470
 |year          = 2009
 |doi       = 10.1109/TPDS.2008.240
 |s2cid = 18740053
 }}</ref> (REDUCE, [[CoWord]], CoPPT, CoMaya)
| IT
| {{Yes}}
| {{any|Undo any operation}}
| CP2/TP2, IP2, IP3
| CP1/TP1, (no ET therefore no IP1 necessary)
| Causal order + Discontinuous total order
| Context vector
|-
|TIBOT <ref name=liicpads2004>{{cite conference
|author1=R. Li, D. Li  |author2=C. Sun
 |name-list-style=amp |title = A Time Interval Based Consistency Control Algorithm for Interactive Groupware Applications
|conference= ICPADS '04: Proceedings of the Parallel and Distributed Systems, Tenth International Conference
|year = 2004
|pages = 429
|doi = 10.1109/ICPADS.2004.12
}}</ref>
| IT
| {{Yes}}
| {{No}}
| CP2/TP2
| CP1/TP1
| Causal order
| Scalar
|- 
| SOCT4<ref name=Vidot2000>{{cite conference
 |author        = Vidot, N.
 |author2       = Cart, M.
 |author3       = Ferrie, J.
 |author4       = Suleiman, M.
 |year          = 2000
 |title         = Copies convergence in a distributed real-time collaborative environment
 |conference= Proceedings of the 2000 ACM conference on Computer supported cooperative work
 |pages         = 171–180
 |publisher     = ACM Press New York, NY, USA
 |url           = http://www.lirmm.fr/~nvidot/php/get.php?file=vidot-cscw2000.pdf
 |url-status       = dead
 |archive-url    = https://web.archive.org/web/20041012143148/http://www.lirmm.fr/~nvidot/php/get.php?file=vidot-cscw2000.pdf
 |archive-date   = 2004-10-12
}}</ref>
| Forward transformation (IT)
| {{Yes}} 
| {{No}} 
| CP2/TP2
| CP1/TP1
| Causal order + Continuous total order
| Scalar
|- 
| SOCT2<ref name=Suleiman1998>{{cite conference
 | author = Suleiman, M. |author2=Cart, M. |author3=Ferrié, J.
 | year = 1998
 | title = Concurrent Operations in a Distributed and Mobile Collaborative Environment
 | conference = Proceedings of the Fourteenth International Conference on Data Engineering, February
 | pages = 23–27
 |doi=10.1109/ICDE.1998.655755 }}</ref>
| Forward Transformation(IT) and Backward Transformation(ET)
| {{Yes}}
| {{No}}
| {{CNone|None}}
| CP1/TP1, CP2/TP2, RP
| Causal order
| State vector
|- 
| MOT2<ref name=mot2>{{cite conference
 | author = M. Cart, Jean Ferrié 
 | year = 2007
 | title = Synchronizer Based on Operational Transformation for P2P Environments
 | conference = Proceedings of the 3rd International Conference on Collaborative Computing: Networking, Applications and Worksharing
 | url = http://hal.archives-ouvertes.fr/docs/00/08/60/98/PDF/cart_document_RR_LIRMM.pdf 
 | pages = 127–138
 | access-date = 2007-07-26
 }}</ref>
| Forward transformation (IT)
| {{Yes}}
| {{No}}
| {{dunno}}
| CP1/TP1, CP2/TP2
| {{dunno}}
| scalar
|}
<blockquote>
A continuous total order is a [[Total order|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. 
 </blockquote>

The transformation-based algorithms proposed in <ref name=Li2007/><ref name=Li2005b/> 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<ref name=gugroup2005>{{cite conference
|author = Gu, Ning and Yang, Jiangming and Zhang, Qiwei
|title = Consistency maintenance based on the mark \& retrace technique in groupware systems
|conference = GROUP '05: Proceedings of the 2005 international ACM SIGGROUP conference on Supporting group work
|year = 2005
|pages = 264–273
|doi = 10.1145/1099203.1099250
}}
</ref>

The correctness problems of OT led to introduction of transformationless post-OT schemes, such as WOOT,<ref name=woot>{{cite conference
|author=Imine, Abdessamad and Molli, Pascal and Oster, Gerald and Urso, Pascal
|title=Real time group editors without Operational transformation
|pages=24
|conference=INRIA Research Report RR-5580
|year=2005
|url=http://hal.inria.fr/inria-00071240/en/
}}
</ref> Logoot<ref name=logoot>{{cite journal
|doi=10.1109/TPDS.2009.173
|author=Stephane Weiss and Pascal Urso and Pascal Molli
|title=Logoot-Undo: Distributed Collaborative Editing System on P2P Networks
|location=IEEE Transactions on Parallel and Distributed Systems
|year=2010
|page=1162
|volume=21
|journal=IEEE Transactions on Parallel and Distributed Systems
|issue=8
|s2cid=14172605
}}
</ref> and Causal Trees (CT).<ref name=ct>{{cite conference
 |author        = Victor Grishchenko
 |title         = Deep Hypertext with embedded revision control implemented in regular expressions
 |conference-url = http://www.wikisym.org/ws2010/
 |conference    = The Proceedings of the 6th International Symposium on Wikis and Open Collaboration (WikiSym '10)
 |year          = 2010
 |url           = http://bouillon.math.usu.ru/articles/ctre.pdf
 |access-date   = 2010-06-30
 |archive-url   = https://web.archive.org/web/20120309001037/http://bouillon.math.usu.ru/articles/ctre.pdf
 |archive-date  = 2012-03-09
 |url-status      = dead
}}</ref> "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.

==Critique of OT==
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)".<ref name=lili2010>{{cite journal
|author1=Du Li  |author2=Rui Li
 |name-list-style=amp |title = An Admissibility-Based Operational Transformation Framework for Collaborative Editing Systems
|journal=Computer Supported Cooperative Work (CSCW)
 |location = Computer Supported Cooperative Work
|year = 2010
|volume=19
|issue=1
|pages = 1–43
  |doi=10.1007/s10606-009-9103-1
|s2cid=35748875
 }}
</ref>

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."<ref>{{cite web |url=http://sharejs.org/ |title=ShareJS |date=2011-11-06 |access-date=2013-08-16 |archive-url=https://web.archive.org/web/20120511194130/http://sharejs.org/ |archive-date=2012-05-11 |url-status=dead }}</ref> 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."<ref>{{Cite web|url=https://news.ycombinator.com/item?id=12311984|title=Yes thats me! For what its worth, I no longer believe that wave would take 2 yea... {{!}} Hacker News|website=news.ycombinator.com|access-date=2019-02-13}}</ref>

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]].<ref>{{cite web
|author = Neil Fraser
|title = Differential Synchronization
|date = January 2009
|url = http://neil.fraser.name/writing/sync/
}}
</ref>

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

==See also==

* [[Data synchronization]]
* [[Collaborative real-time editor]]s
* [[Conflict-free replicated data type]]s
* [[Consistency model]]s
* [[Optimistic replication]]

==References==
{{Reflist|30em}}

==External links==
* [https://www3.ntu.edu.sg/scse/staff/czsun/projects/otfaq/ OT FAQ: Operational Transformation Frequently Asked Questions and Answers]
* [https://archive.today/20121224222231/http://cooffice.ntu.edu.sg/sigce/ SIGCE: Special Interest Group of Collaborative Editing]
* [https://web.archive.org/web/20090615070721/http://cooffice.ntu.edu.sg/sigce/conferences.php International Workshop on Collaborative Editing Systems]
* [https://web.archive.org/web/20110928210851/http://dsonline.computer.org/portal/site/dsonline/menuitem.20d6846e1c7ed783f1a516106bbe36ec/index.jsp?&pName=dso_level1_home&path=dsonline%2Ftopics%2Fcollaborative&file=index.xml&xsl=generic.xsl&   Distributed System Online - Collaborative editing]
*[https://drive.googleblog.com/2010/09/whats-different-about-new-google-docs_22.html Simple explanation of OT in Google Docs]
* [https://web.archive.org/web/20150928170646/http://opencoweb.org/ocwdocs/intro/openg.html Basics of OT in the Open Coweb Framework]

===Relevant online talks===
* [https://www.youtube.com/watch?v=3ykZYKCK7AM Google Wave: Live collaborative editing]
* [https://www.youtube.com/watch?v=84zqbXUQIHc Google Tech Talk: Issues and Experiences in Designing Real-time Collaborative Editing Systems]
* [https://web.archive.org/web/20061007135537/http://cooffice.ntu.edu.sg/coword/vods/lecture.htm Microsoft Research talk: Consistency maintenance in real-time collaborative editing systems]

{{DEFAULTSORT:Operational Transformation}}
[[Category:Concurrency control]]
[[Category:Collaboration]]
[[Category:Distributed algorithms]]
[[Category:Groupware]]