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. In 2009, OT was adopted as a core technique behind the collaboration features in then-Google Wave and Google Docs.
History Operational Transformation was pioneered by C. Ellis and S. Gibbs in the GROVE (GRoup Outline 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 on Collaborative Editing (CE) was set up to promote communication and collaboration among CE and OT researchers. Since then, SIGCE holds annual CE workshops in conjunction with major Computer Supported Cooperative Work (CSCW) conferences, such as ACM, CSCW, GROUP and ECSCW.
System architecture Collaboration systems utilizing Operational Transformations typically use replicated document storage, where each client has their own copy of the document; clients operate on their local copies in a lock-free, non-blocking manner, and the changes are then propagated to the rest of the clients; this ensures the client high responsiveness in an otherwise high-latency environment such as the Internet. When a client receives the changes propagated from another client, it typically transforms the changes before executing them; the transformation ensures that application-dependent consistency criteria (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.
Basics
The basic idea of OT can be illustrated using a simple text-editing scenario. Consider a text document containing the 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 of the key functionalities of OT is to support consistency maintenance in collaborative editing systems. Several consistency models have been proposed in the research community, some of which are designed for collaborative editing systems in general, while others are specifically tailored to OT algorithms.
The CC model In Ellis and Gibbs's 1989 paper "Concurrency control in groupware systems", two consistency properties are required for collaborative editing systems:
Causality preservation: ensures the execution order of causally dependent operations be the same as their natural cause-effect order during the process of collaboration. The causal relationship between two operations is defined formally by Lamport's "happened-before" relation. When two operations are not causally dependent, they are concurrent. Two concurrent operations can be executed in different order on two different document copies. Convergence: ensures the replicated copies of the shared document be identical at all sites at quiescence (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 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. Under the CCI model, three consistency properties are grouped together:
… excerpt ends here. Continue reading the full article.
