Operational transformation
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.
The basic idea of OT can be illustrated by using a simple text editing scenario as follows.
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.
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 CCI model was proposed as a consistency management in collaborative editing systems.
OT has been found particularly suitable for achieving convergence and intention preservation in collaborative editing systems.
In,[4] 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.
[11] In their approach, an OT algorithm is correct if it satisfies two formalized correctness criteria: As long as these two criteria are satisfied, the data replicas converge (with additional constraints) after all operations are executed at all sites.
This way the control procedure and transformation functions work synergistically to achieve correctness, i.e., causality and admissibility preservation.
OT functions used in different OT systems may be named differently, but they can be classified into two categories: 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.
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][29][31] In addition, different OT control algorithm designs make different tradeoffs in: 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.
[3][4][5][8][32] 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.
The transformation-based algorithms proposed in [10][11] are based on the alternative consistency models "CSM" and "CA" as described above.
For example, Mark and Retrace[35] The correctness problems of OT led to introduction of transformationless post-OT schemes, such as WOOT,[36] Logoot[37] and Causal Trees (CT).
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.
[39] Similarly, Joseph Gentle who is a former Google Wave engineer and an author of the Share.JS library wrote, "Unfortunately, implementing OT sucks.
