OT FAQ

 Operational Transformation Frequently Asked Questions and Answers

 

Chengzheng Sun

 

This FAQ is intended to provide comprehensive coverage of questions, answers and references related to the subject of OT. This document is Copyright © 2010 2011 by Chengzheng Sun. All rights reserved.

 

 

Table of Contents

1.        OT basics. 3

1.1...... What is OT?. 3

1.2...... What collaboration capabilities can OT support?. 3

1.3...... What collaborative applications can OT support?. 4

1.4...... What is the basic idea of OT for consistency maintenance?. 5

1.5...... What is the basic idea of OT for undo?. 7

1.6...... What is the basic idea of OT for operation compression?. 8

1.7...... What is a basic OT system?. 10

1.8...... What is the operation model of an OT system?. 10

1.9...... What is the data model of an OT system?. 10

1.10.... Can OT support documents other than plain texts?. 11

1.11.... Can OT support operations other than Insert and Delete?. 11

1.12.... Can OT support complex data objects without linear relationships?. 11

1.13.... Can OT support complex application operations?. 11

1.14.... Can OT preserve the user intention?. 12

1.15.... Can OT solve semantic consistency problems?. 12

2.        OT design. 13

2.1...... What is the structure of an OT system?. 13

2.2...... What is the role of transformation control algorithms in an OT system?. 14

2.3...... What is the role of transformation functions in an OT system?. 14

2.4...... What is the role of transformation conditions and properties in an OT system?. 14

2.5...... What is the benefit of separating control algorithms from transformation functions?. 15

2.6...... What is the concept of operation context in OT design?. 15

2.7...... How to represent operation context in OT design?. 17

2.8...... What is the context-equivalent relationship between operations?. 17

2.9...... What is the context-preceding relationship between operations?. 18

2.10.... What are the context-based conditions governing  OT control algorithm design?. 18

2.11.... How to design context-based OT control algorithms?. 19

2.12.... How to classify OT control algorithms by their capabilities?. 20

2.13.... What kinds of transformation function exist?. 21

2.14.... What are the basic ideas in designing transformation functions?. 21

2.15.... How to design character-wise transformation functions?. 22

2.16.... Why are string-wise transformation functions challenging to design?. 22

2.17.... What are the pre-/post-conditions for transformation functions?. 23

2.18.... Which OT components are responsible for ensuring transformation pre-/post-conditions?  24

2.19.... What are the OT transformation properties and their pre-conditions ?. 24

2.20.... Which OT components are responsible for achieving transformation properties?. 26

2.21.... How to break pre-conditions for both CP1 and CP2?. 26

2.22.... How to break the precondition of CP2 ?. 27

2.23.... How to deal with the complexity in OT system design?. 30

2.24.... What issues to consider in evaluating OT system time efficiency?. 30

2.25.... What are the space efficiency issues of an OT system?. 33

2.26.... What attributes can be used to differentiate OT systems?. 33

2.27.... What is the role of OT in the Generic Collaboration Engine (GCE) technology?. 34

2.28.... What is the role of OT in the Transparent Adaptation (TA) technology?. 35

2.29.... What is the role of the OTXplorer in OT research and design?. 36

3.        OT correctness. 37

3.1...... What are the multi-facets of  OT correctness?. 37

3.2...... What are the consistency-related application correctness requirements?. 38

3.3...... What are the undo-related application correctness requirements?. 41

3.4...... What are the compression-related application correctness requirements?. 42

3.5...... What are the OT-related application correctness requirements?. 43

3.6...... Does an OT system must meet all application correctness requirements?. 44

3.7...... Does a collaborative editor must meet all consistency correctness requirements?. 45

3.8...... Why are some application correctness requirements specified informally?. 45

3.9...... What are the multi-level specifications of  intention-preservation?. 46

3.10.... What are the context-based conditions for achieving intention preservation?. 46

3.11.... What are the criteria for verifying intention-preservation for character-wise operations?  47

3.12.... What is the relationship between convergence and intention preservation?. 47

3.13.... What is the relationship between the intention of an operation and the intention of the user?  48

3.14.... Under what conditions is an OT system application-correct?. 49

3.15.... What are the OT algorithm correctness requirements?. 49

3.16.... Which OT components are responsible for meeting what algorithm correctness requirements?  50

3.17.... Does an OT system must meet all algorithm correctness requirements?. 51

3.18.... Under what conditions is an OT system algorithm-correct?. 52

3.19.... How to make a correct OT system by combining existing control algorithms and transformation functions?  52

3.20.... What is the relationship between algorithm and application correctness?. 54

3.21.... What is the relationship between  OT puzzles and algorithm correctness?. 54

3.22.... What is the dOPT puzzle?. 55

3.23.... Are CP1 and CP2 necessary and sufficient conditions required for correctness of transformation functions?  56

3.24.... What is the False-Tie (FT) puzzle?. 57

3.25.... Under what circumstances is an FT-solution needed or not needed?. 59

3.26.... How to achieve consistency without solving the FT puzzle?. 60

3.27.... What are the main differences between the FT puzzle and other OT puzzles?. 64

3.28.... What role does the puzzle-detection-resolution approach play in OT research ?. 65

3.29.... What role does theoretic verification play in OT algorithm correctness study?. 65

3.30.... What role do real-world applications play in OT research?. 66

(4)       OT references. 67

 

1.      OT basics

 

1.1.What is OT?

OT is a technology for supporting collaborative computing functions and applications. OT has a rich set of collaboration capabilities and has been used to support a wide range of applications.

 

The first OT system was proposed for supporting concurrency control in real-time collaborative editing (CE) of plain text documents in 1989 [6]. Several years later, some correctness issues in the first OT system were detected and several approaches were independently proposed to solve these issues [42]. In 1998, a Special Interest Group of Collaborative Editing (SIGCE) was set up to promote communication and collaboration among CE and OT researchers. This was followed by another decade of continuous efforts of extending and improving OT by a community of researchers [164]. The capability and application scope of OT has been continuously expanding over the years.

 

[ TOP | Next section ]

1.2.What collaboration capabilities can OT support?

OT is able to support a rich set of collaboration capabilities or functionalities, including but not limited to:

(1)      Consistency maintenance or concurrency control: OT is able to maintain shared document consistency while allowing multi-users to generate operations freely and concurrently and the system to respond to local users quickly and execute remote operations in different orders [6, 7, 8, 13, 14, 20, 21, 25, 27, 30, 31, 37, 38, 39, 42, 43, 53, 54, 58, 59].

(1)      Conflict resolution: OT is able to resolve conflicts among concurrent operations targeting shared or dependent objects in a way that maintains consistency and preserves the effects of all operations in the face of conflict [3, 51, 56, 62, 63, 55].

(2)      Group undo: OT is able to support undoing operations in multi-user concurrent editing environments [28, 29, 30, 46, 50, 54].

(3)      Workspace awareness: OT is able to support workspace awareness features (e.g. telepointers, radar-views) in concurrent, dynamic, and complex (2D/3D) workspaces [2, 52, 61].

(4)      Locking: OT is able to support fine-grained and responsive locking to help protect the integrity of shared objects and maintain semantic maintenance in collaborative computing environments [44, 49].

(5)      Operation notification: OT is able to support a spectrum of operation notification strategies that cover the needs for both real-time and non-real-time collaborative applications [33].

(6)      Operation compression: OT is able to support compression of large number of operations accumulated in non-real-time and/or mobile collaborative computing environments [34, 35].

(7)      Transparent adaptation: OT is the corner-stone of the Transparent Adaptation (TA) approach [1, 2, 52, 60, 61, 62, 63], that is able to convert existing or new single-user applications/components into multi-user collaborative ones without making any change to the source code of the original application/component. TA-based collaborative applications preserve the functionalities and the “look-and-feel” of single-user applications, and provide advanced collaboration capabilities supported by OT.

 

[ TOP  | Next section ]

 

1.3.What collaborative applications can OT support?

OT has been applied to a wide range of real-time and non-real-time collaborative applications, including:

(1)      Collaborative text editing [4, 5, 8, 12, 28, 30, 31, 43, 50, 58]. Example systems:

·        Subethaedit: a collaborative real-time editor designed for Mac OS X.

·        CoVim: a real-time collaborative text editor that enables multiple users to edit the same text document simultaneously in Vim.

(2)      Collaborative graphics editing [51, 52, 62]. Systems available:

·        CoFlash: a real-time collaborative multimedia editor that enables multiple users to edit the same document simultaneously in Adobe Flash.

(3)      Collaborative HTML/XML and rich text documents editing [5, 59]. Example systems:

·         EtherPad: a web-based real-time collaborative editor.

·         CoCKEditor: a web-based real-time collaborative editor that enables multiple users to edit the same document simultaneously in CKEditor.

(4)      Collaborative word processing [51, 52, 60]. Systems available:

·        CodoxWord: a real-time collaborative word processor that enables multiple users to edit the same document simultaneously in Microsoft Word.

(5)      Collaborative slide creation and presentation tools [52]. Systems available:

·        CoPowerPoint: a real-time collaborative slide editor that enables multiple users to edit the same document simultaneously in Microsoft PowerPoint.

(6)      Collaborative spreadsheet editing [27, 56, 63]. Example systems:

·        CoCalc: a real-time collaborative spreadsheet editor that enables multiple users to edit the same document simultaneously in  OpenOffice.org Calc.

(7)      Collaborative computer-aided digital media design tools [1, 2, 3]. Example systems:

·        CoMaya: a real-time collaborative 3D design tool that enables multiple designers to edit the same document simultaneously in Autodesk Maya.

(8)      Collaborative web-based applications, services, and frameworks [59, 5]. Example systems:

·        Google Docs: a web-based real-time collaborative word processor.

·        Google Wave: OT is the core real-time collaborative technique behind Google Wave, which integrates e-mail, instant messaging, blogging, wiki, and social networking.

·        Novell Pulse [36]: an enterprise real-time collaboration software platform, that utilizes the Google Wave Federation Protocol.

·        Open Cooperative Web Framework: a Dojo Foundation Project that uses Operational Transformation algorithms to enable Cooperative web concepts.

 

[TOP | Next section ]

 

1.4.What is the basic idea of OT for consistency maintenance?

The basic idea of OT for consistency maintenance can be illustrated using a simple text editing scenario, as shown in Figure 1.

 

basicOT

Figure 1. A scenario for illustrating the basic idea of OT for consistency maintenance

 

In this scenario, the initial text document contains a string “abc” replicated at two collaborating sites; and there are two concurrent operations: O1 = Insert[0, “x”] (to insert character “x” at position 0), and O2 = Delete[2, 1] (to delete one (1) character at position 2, i.e. “c”) generated by collaborating users at sites 1 and 2, respectively. Under the control of OT, local operations will be executed as-is; remote operations will be transformed before their execution.

(1)      At site 1, O1 is first executed and the document becomes “xabc”. Then O2 arrives and is transformed against O1 to become O2 = T(O2, O1) = Delete[3, 1], whose positional parameter is incremented by one to include the impact of one character insertion caused by concurrent operation O1. Executing O2 on “xabc” shall correctly delete “c” and the document becomes “xab” (Note: if O2 was executed in its original form, then it would incorrectly delete “b”, rather than “c”).

(2)      At site 2, O2 is first executed and the document becomes “ab”. Then O1 arrives and is transformed against O2 to become O1 = T(O1, O2) = Insert [0, “x”]. In this case, the transformed operation O1  is the same as the original O1 because the prior execution of O2 has no impact on O1. Executing O1 on “ab” shall insert “x” at position 0 and the document becomes “xab”, which is identical to the document at site 1.

 

In summary, the basic idea of OT for consistency maintenance is to transform an editing operation into a new form according to the effects of previously executed concurrent operations so that the transformed operation can achieve the correct effect (Intention Preservation) and ensure replicated documents be identical (Convergence) [42, 43].

 

It is worth pointing out that, for simplicity and intuitiveness, collaborative text editing scenarios with concurrent operations on overlapping or adjacent objects have often been used in OT research literature to illustrate OT technical problems and algorithms. For example, the positions of the two concurrent editing operations in Figure 1 are separated by only a small number (three) of characters “abc”. Such simplistic examples should not be interpreted as that OT is needed or useful only when users are concurrently editing in adjacent characters, e.g. the same word, the same line, or the same paragraph, etc. In fact, the applicability of OT is not related to the number of characters/objects separating concurrent operations. OT is needed and useful for concurrency control of operations targeting at objects which have positional dependency (or shifting) relationships, regardless whether those target objects are overlapping, adjacent or far apart from each other (e.g. being separated by millions of objects in large Word documents [52, 60]).

 

[TOP  | Next section ]

 

1.5.What is the basic idea of OT for undo?

The basic idea of OT for supporting (nonlinear) undo can be illustrated using a simple text editing scenario in Figure 2.

Figure 2. A scenario for illustrating the basic idea of OT for undo

 

In this scenario, the initial text document contains a string “123” replicated at two collaborating sites.

(1)          First, O1 = Insert[2,“y”] (to insert character “y” at position 2) is generated by the user at site 2; O1 is then propagated to site 1 and executed as-is, resulting in the document state "12y" at both sites.

(2)          Second, O2 = Insert[0, "x"] (to insert character “x” at position 0) is generated by the user at site 1; then O2 is propagated to site 2, and executed as-is, resulting in the document state "x12y" at both sites. 

(3)          After executing O1  and O2  in sequence, the user at site 2 issues an undo command Undo(O1) to undo O1 , which is NOT the last executed operation. An OT-based undo system will first create an inverse operation !O1 = Inverse(O1 = Insert[2,“y”]) = Delete[2]; then transform the !O1 against O2, i.e. !O'1 = T(!O1, O2) = Delete[3]; and finally execute !O'1 , resulting in  the document state into "x12", which achieves the correct  Undo Effect, i.e. to eliminate the effect of O1   but retain the effect O2. If the original inverse !O1 = Delete[2] was executed without transformation,  the document state would become "x1y", which is incorrect.

 

In summary, the basic idea of OT for undo is to transform the inverse of O (the operation to  be undone) into a new form according to the effects of those operations executed after O, so that the transformed inverse operation can achieve the correct  Undo Effect. A correct undo effect will eliminate the effect of O, but retain the effects of other operations. In other words, a correct undo effect will transform the document state into one that it would have gone to if O had never been performed but other operations had been performed [50, 54].   

 

[TOP  | Next section ]

 

1.6.What is the basic idea of OT for operation compression?

The basic idea of OT for operation compression can be illustrated using a simple text editing scenario in Figure 3.

 

Figure 3. A scenario for illustrating the basic idea of OT for operation compression

 

In this scenario, the initial text document contains a string “123” replicated at two collaborating sites. At site 1, the user generates four operations in sequence: O1 = Insert[2,“X”] (to insert a character “X” at position 2),  O2 = Insert[1,“abc”] (to insert a string “abc” at position 1), O3 = Insert[2,“Y”] (to insert a character “Y” at position 2), and O4= Delete[7] (to delete the character “X” at position 7). Suppose these operations are all logged in L = [O1, O2, O3, O4], without being propagated immediately after their execution (this could happen in either real-time or non-real-time collaboration sessions). Under certain conditions (determined by the user or automatically), operations in L may be propagated to site 2 for remote integration. Before propagation, operations in L can be compressed by an  OT-based compression algorithm [34, 35], which scans the operations in L from the end (right-most) to the beginning  (left-most) one by one, examining the relationship between each pair of adjacent operations to decide whether to transpose, eliminate, or merge them. In this example, the following steps can take place:

(1)          The right-most operation O4 is transposed with adjacent operation O3: transpose(O3, O4) = [O'4, O'3], where O'4  = Delete[6], and O'3 = O3 , resulting in L' = [O1, O2, O'4, O3].

(2)          O'4 is further transposed with the new adjacent operation O2: transpose(O2, O’4) = [O''4, O'2], where O''4  = Delete[3], and O'2 = O2 , resulting in L' = [O1, O''4, O2, O3]. 

(3)          O''4  is examined with its new adjacent operation O1; and they  are found to be overlapping and complement with each other (i.e. with no effect on the document),  so both O''4  and O1 are eliminated from L, resulting in L' = [O2, O3].

(4)          The two adjacent and overlapping operations O2 and O3 in L’ are merged into a single operation O'2 = Insert[1, “aYbc”], resulting in L' = [O’2].

(5)          L' = [O’2], instead of L = [O1, O2, O3, O4], is propagated to remote site for integration. 

 

In summary, the basic idea of OT for operation compression is to transpose (a kind of transformation) accumulated operations to proper forms and locations in the log L, so that their overlapping and complementing relationships can be examined to decide whether they can be merged or eliminated, thus achieving the operation Compression Effect, i.e., to reduce the number of operations in L while preserving the original operation effect of L.  L' and L must be equivalent in the sense that they can result in the same document state when they are applied to the same initial document state: S o L' = S o L, where S is any document state.  The number of operations in L could potentially be very large (e.g. in non-real-time and/or mobile collaborative editing sessions), so OT-based operation compression is particularly useful and effective under such circumstances.

 

[TOP | Next section ]

1.7.What is a basic OT system?

The term of a basic OT system is often used to mean an OT system that has the basic capability of consistency maintenance for a pair of primitive character-wise insert and delete operations. The first OT system [6] is a basic OT system. Most existing OT systems are extensions of the basic OT system.

 

[TOP | Next section ]

1.8.What is the operation model of an OT system?

The operation model of an OT system is the set of operations directly processed by transformation functions. Different OT systems may have different operation models. For example, the operation model of a basic OT system consists of two primitive operations: character-wise insert and delete. This basic operation model has been extended to include additional primitive operations, e.g. update, to support collaborative Word document processing and 3D model editing [1, 51]. Other extensions to the basic OT operation model are application-dependent.

 

[TOP | Next section ]

1.9.What is the data model of an OT system?

The data model of an OT system defines the way data objects in a document are related to each other and referenced by operations. Different OT systems may have different data models. For example, the data model of a basic OT system is a collection of independent objects addressed by a single linear address space (each object has a positional reference in this address space). This basic data model is adequate for modeling documents with one-dimensional and linearly ordered data objects, such as a sequence of characters (in plain text documents), a sequence of slides (in presentation documents), etc. The basic OT data model has been extended into a hierarchy of multiple linear addressing domains for supporting word processor and HTML/XML documents [5, 8, 52, 56], and into dependent object graphs for supporting digital media documents [3].

 

[TOP  | Next section ]

1.10.    Can OT support documents other than plain texts?

Yes. OT can support collaborative editing of a wide range of documents, including text/graphics/word documents, spreadsheets, and digital media models.

 

[TOP  | Next section ]

1.11.    Can OT support operations other than Insert and Delete?

Yes. In addition to Insert and Delete, OT can support other primitive operations, such as update [51], point [61], lock [44], etc. and arbitrary complex application operations.

 

[TOP | Next section ]

1.12.    Can OT support complex data objects without linear relationships?

Yes. The basic OT requires data objects to be referable via a linear address space, but data objects in complex applications (e.g. word processors and 3D media design tools) may have non-linear relationships at the user interface (UI). This difference was considered to be a major obstacle in applying OT to applications with complex data models. However, later research [52] has discovered that OT applicability is independent of whether data objects are represented or viewed linearly at the UI level, but dependent on whether data objects can be addressed linearly via the program interface from which OT accesses the application data. This program interface can be either an internal data interface if OT is implemented inside the application (a collaboration-aware approach [43, 50]), or a public API (Application Programming Interface) if OT is implemented outside the application (a collaboration-transparent approach [4, 13, 52]). A data adaption process is often needed to bridge the application data model (accessible from the program interface) and the OT data model. CodoxWord, CoMaya, and Google Wave [59] are representative OT-supported collaborative editing systems capable of supporting complex and non-linear data objects.

 

[TOP  | Next section ]

1.13.    Can OT support complex application operations?

Yes. There exist two basic approaches to supporting complex application-level operations for manipulating shared data objects:

(1)      Primitive operation model approach: the OT system has an operation model consisting of a small number of primitive operations (e.g. string-wise insert, delete, and update). In this approach, transformation functions are defined at the primitive operation level, which is simple (relatively easy to design and to ensure correctness) and transformation functions so designed are reusable among different applications. This approach needs an operation-adaptation process to map application-specific operations into primitive operations for transformation. One example OT system using this approach is the Generic Collaboration Engine (GCE) [52] that supports CodoxWord, CoPowerPoint, CoMaya, etc.

(2)      Application-specific operation model approach: the OT system has an operation model consisting of a (potentially) large number of application operations. In this approach, transformation functions are defined at the application operation level, which is complex (relatively difficult to design and to ensure correctness) and transformation functions so designed are not reusable for different applications. For an application with N different operations, N × N transformation functions are needed for supporting this application. Example OT systems using this approach include Google Wave OT [59], Co-Spreadsheet [27], etc.

 

[TOP  | Next section ]

1.14.    Can OT preserve the user intention?

No existing OT technique can ensure the preservation of user intentions. However, OT is able to preserve the operation intention, which is related to but different from the intention of the user who issues the operation.

 

[TOP | Next section ]

1.15.    Can OT solve semantic consistency problems?

No existing OT technique can solve semantic consistency problems in collaborative editing systems. Most existing work on consistency maintenance in collaborative editing systems has focused on issues and techniques related to syntactic consistency, which is mainly concerned with whether operations are executed in the right order (causality preservation [42]) and whether the same (convergent and intention-preserved [42]) view of the shared document is maintained at all sites. Semantic consistency is concerned with whether a shared view is meaningful/correct in the application domain, as well as whether all sites have the same view.

 

To illustrate, consider a shared text document with the following text:

“OT preserve operation intention”

In this text, there is an English grammar error (highlighted by the underlined text), i.e. the underlined text should be “can preserve”, “preserves”, or the like. Assume that two users observed this grammar error and wanted to correct it in two different ways: one user issues an operation to insert “can” at the starting position of “preserve”, while another user issues a concurrent operation to insert “s” at the ending position of “preserve”. Suppose the collaborative editing system has used OT to achieve convergence and intention preservation [42]. Then, after the execution of these two concurrent operations at all sites, the text would become:

“OT can preserves operation intention”

From syntactic consistency point of view, this result is correct since both users have the same document contents and the intended effects of the two operations have been achieved. This syntactically correct result is, however, semantically incorrect according to English grammar. In other words, OT is able to ensure plain strings be correctly inserted/deleted at proper positions, but unable to ensure the final string make a correct English sentence – a semantic consistency problem.

 

However, if the two users are provided with locking facilities to enforce mutual exclusion over specific regions (e.g., an English word, a statement, or a section, etc.), then either one of the two users could obtain an exclusive lock on the original statement

“OT preserve operation intention”

before modifying it. Consequently, the final text would be either:

“OT can preserve operation intention”

or

“OT preserves operation intention”

which is semantically correct in terms of English grammar.

 

In general, by allowing only one user at a time to update a semantically meaningful text region, locking can help resolve semantic conflict problems because it prevents concurrent operations from updating the same region in semantically conflicting ways.

 

In summary, OT and locking are complementary to each other: OT is able to achieve syntactic consistency (convergence and intention-preservation [42]), which cannot be solved by locking, whereas locking is able to help resolve semantic consistency problems, which cannot be solved by OT. OT has been integrated with an optional, responsive, and fine-grained locking scheme to solve both syntactic and semantic consistency problems in collaborative editing systems [44, 49].

 

 [TOP | Next section ]

 

2.      OT design

 

2.1.What is the structure of an OT system?

One established strategy of structuring an OT system is to separate the high-level transformation control (or integration) algorithms from the low-level transformation functions [6, 21, 25, 30, 37, 42, 43, 53, 58], and specify the relationships (responsibilities and constraints) between these two layers as transformation properties and conditions in the middle of the OT system, as shown in Figure 4.

OTsystem

Figure 4. A layered structure of an OT system

 

Some alternative ways of structuring OT systems can be found in [7, 18, 22, 31].

 

[TOP  | Previous section | Next section ]

2.2.What is the role of transformation control algorithms in an OT system?

Transformation control algorithms are responsible for determining when an operation (transformation target) is ready for transformation, which operations (transformation reference) should be transformed against, and in which order should transformations be carried out. Transformation control algorithms are generic in the sense they rely on generic relations (e.g. context [54] and concurrency [11]) among operations to do the work. Control algorithms provide input operations to transformation functions.

 

[TOP | Previous section | Next section ]

2.3.What is the role of transformation functions in an OT system?

Transformation functions are responsible for performing actual transformations on the target operation according to the impact of the reference operation. Transformation functions are dependent on the types and parameters of operations, and data and operation model of the OT system. Transformation functions produce output operations for control algorithms.

 

[ TOC | Previous section | Next section ]

2.4.What is the role of transformation conditions and properties in an OT system?

Transformation conditions and properties define the relationships between transformation control algorithms and functions, and serve as OT algorithm correctness requirements, which can be used to verify whether a transformation control algorithm or function is correct with respect to certain correctness requirements. The correct functioning of an OT system requires transformation control algorithms and functions match each other in terms of those conditions and properties.

 

[TOP  | Previous section | Next section ]

2.5.What is the benefit of separating control algorithms from transformation functions?

Separating generic control algorithms from operation-specific transformation functions has the following benefits:

(1)      Reduce the complexity of OT system design: breaking the OT system into smaller and more manageable components, with well-defined transformation conditions and properties between them, helps reduce design complexity and allows the change of one component without affecting the other.

(2)      Increase modularity and reusability of OT components: control algorithms and transformation functions can be designed and verified separately. Components designed for different OT systems can be combined to create new OT systems for serving new purposes, as long as they are compatible with respect to the transformation conditions and properties required by each other.

(3)      Facilitate capability extension: the capability of an OT system can be extended by changing one component without affecting the other. For example, control algorithms can be extended to support new capabilities (e.g. extension from consistency maintenance to group undo) without changing existing transformation functions; transformation functions can be extended to support new features (e.g. conflict resolution, locking) or new applications with different data and operation models without changing control algorithms (e.g. the same control algorithm can be used for supporting concurrent editing, conflict resolution, locking, and pointing).

 

[TOP  | Previous section | Next section ]

2.6.What is the concept of operation context in OT design?

A core concept in OT design is operation context, which is the document state on which an operation is defined [42,54].  When an operation is generated, it is associated with an original context, which is the document state from which the operation is generated.  For example in Figure 5, the initial document state is S0 at both sites.  O1 is generated from the document state S0, so the context of O1 is S0.   O2 is generated from the same initial document state S0, so the context of O2 is S0  as well. After applying O2 on S0, the document state becomes S2, from which O3 is generated, so  S2  is the context of O3.  After generation, the context of an operation can only be changed by operational transformation [42,54]. 

Figure 5 A scenario for illustrating the concept of operation context.

 

The significance of operation context is that it provides a basis for interpreting the effect of an operation and reasoning about the effect relationships among operations, which are essential for ensuring correct operation execution and transformation. Among others, the following two context-based conditions are essential for OT system correctness:

(1)        An operation O can be correctly executed only if its definition context (the document state on which O is defined) equals to its execution context (the document state on which O is to be executed).   The key role that OT plays in consistency maintenance is to transform operations' definition contexts to match their execution contexts under all circumstances.  For example in Figure 5, when O1 arrives at Site 2, the document state is S4; if O1 were executed in its original form, the resulting document state would be "a1x234bc", which is clearly incorrect.  The reason for this incorrectness is that S0S4, i.e. the definition context of O1  (S0) does not match its execution context (S4).  In this example, O1 must be transformed against O2 and O3: O1'=T(T(O1,O2),O3)=Insert[6, "x"], where O1' preserves the effect of O1 but is defined on a new document state S4. Executing O1' on S4 will achieve the same effect as executing O1 on S0.

(2)        Two operations can be correctly transformed only if they have the same definition context, i.e. they are defined on the same document state.  For example in Figure 5, O1 and O2 are defined on the same initial document state S0, so their positional parameters are comparable and they can be directly transformed with each other.  Based on the linear addressing model and the position parameters (1 for O2 and 2 for O1), it can be derived that O2 is inserting at the left side of O1. If O2 is executed after O1 (Site 1), the prior execution O1 has no impact on O2, so O2' = T(O2, O1) = O2; if O1 is executed after O2 (Site 2), the prior execution of O2 has position shifting effect on O1, so T(O1, O2) = Insert[4,"x"], as shown in Figure 5.  However, O1 and O3 have different definition contexts S0 and S2,   so it is impossible to correctly derive the effect relationships among O1 and O3 by comparing their positional parameters.  Consequently, O1 and O3 cannot be directly transformed with each other. The correct way of transforming O3 at Site 1 is: first transform O1 against O2 to get O1' which preserves the effect of O1 but is defined on S2 (the same context as O3); then transform O3 against O1', which are defined on the same context, as shown at Site 1.  Note: if O3 were directly transformed against O1, it would be incorrectly assessed that the prior execution of O1 has position shifting effect on O3 and the position parameter of O3 would be mistakenly incremented by one, which is one instance of the well-known dOPT puzzle [42].

 

Last but not least, operation context relationships and conditions are general and applicable for all types of operation in OT systems [42,54], regardless whether those operations are concurrent or sequential, normal (for doing something) or inverse (for undoing a prior action), original (generated by users) or transformed (outcomes of prior transformation).   The ability to determine, compare, and change operation contexts is essential for OT systems to correctly transform operations for the purpose of consistency maintenance,  group undo, or operation compression.

 

2.7.How to represent operation context in OT design?

For the purpose of OT algorithm design,  the context of an operation O  does not need to be represented by a real document state (which is application-dependent), but can be generically represented as a set of original operations that have been executed to create the document state on which O is defined [54].  For example in Figure 5, C(O1) = C(O2) = { } (an empty set) as O1 and O2 are generated from the initial document state in a session (no operation has been executed); C(O3) = {O2} as O3 is generated from a document state after executing O2.  This context representation is adequate for capturing the essential information for OT design and applicable to all OT-based applications.

 

Operations in a context can be represented by a context-vector [54], which uses integers to count the number of original operations generated by each collaborating site. The set and vector representations are equivalent and their mappings can be found in [54].

 

[TOP | Previous section | Next section ]

2.8.What is the context-equivalent relationship between operations?

Given two (original or transformed) operations Oa and Ob, with contexts C(Oa) and C(Ob), respectively, Oa and Ob are context-equivalent if and only if C(Oa) = C(Ob) [42, 54]. If two operations are not context-equivalent, then they are context-different. 

 

For example, in Figure 5, both operation  O1 and O2 are generated from the same initial document state, so they are context-equivalent, i.e. C(O1) = C(O2); but O1 and O3 are generated from different document states, so they are context-different, i.e. C(O1) ≠ C(O3). Operation context can be changed by operational transformation.

 

 

[TOP | Previous section | Next section ]

2.9.What is the context-preceding relationship between operations?

Given two (original or transformed) operations Oa and Ob, with contexts C(Oa) and C(Ob), respectively, Oa is context-preceding Ob, if and only if C(Ob) = C(Oa)  {Ob} [42, 54].

 

[TOP | Previous section | Next section ]

2.10.    What are the context-based conditions governing  OT control algorithm design?  

Context-based Conditions (CCs) capture essential requirements for correct operation execution and transformation in OT systems and govern the design of OT control algorithms. Six context-based conditions (for supporting consistency maintenance and group undo) have been identified [53, 54]:

 

(1)      CC1: Given an original operation O and a document state DS, where O DS, O can be transformed for execution on DS only if:

C(O)  DS.

(2)      CC2: Given an original operation O and a document state DS, where O DS and C(O)  DS, the set of operations that O must be transformed against before being executed on DS is:

DS C(O).

(3)      CC3: Given any operation O and a document state DS, O can be executed on DS only if:

C(O) = DS.

(4)      CC4: Given an original operation Ox and an operation O of any type, where Ox C(O), Ox can be transformed to the context of O only if:

C(Ox)  C(O).

(5)      CC5: Given an original operation Ox and an operation O of any type, where Ox C(O) and C(Ox)  C(O), the set of operations that Ox must be transformed against before being IT-transformed with O is:

C(O) – C(Ox).

(6)      CC6: Given two operations Oa and Ob, they can be IT-transformed with each other, i.e. IT(Oa, Ob) or IT(Ob, Oa), only if:

C(Oa) = C(Ob).

 

In summary,

·        CC1 and CC4 are required for ensuring correct ordering of operation execution and transformation,

·        CC2 and CC5 are required for determining correct transformation reference operations, and

·        CC3 and CC6 are required for ensuring correct operation execution and transformation.

 

Apart from CC1, which must be ensured by external schemes/protocols before invoking the OT control algorithm, CC2–CC6 must be ensured by the OT control algorithm. These conditions are generally applicable for evaluating the correctness of existing OT algorithms (e.g. GOT [43], GOTO [42], adOPTed [30], etc.) or guiding the design of new OT algorithms (e.g. COT [54]).

 

[TOP  | Previous section | Next section ]

 

2.11.    How to design context-based OT control algorithms?  

Context-based conditions can be explicitly used in designing OT control algorithms. One example is the COT (Context-based OT) algorithm [53, 54]. The basic COT algorithm consists of two components: one (COT-DO) for consistency maintenance, and the other (COT-UNDO) for supporting group undo, as shown below.  Some notations used in the following description: O denotes an operation to do or undo;  C(O) represents the context of O, represented as a set of original operations that  collectively define the document state on which O is defined; and DS denotes the current document state, represented as a set of original operations that have been executed so far.

 

COT-DO (O, DS) // precondition (CC1): C(O)  DS.

1.      transform(O, DS – C(O)); // governed by CC2 and CC3

2.      execute(O);   DS := DS U {org(O)}. // org(O) is the original form of O                      

transform(O, CD)

       Repeat until CD = { }:

1.      remove Ox from CD, where C(Ox)  C(O); // required by CC4

2.      transform(Ox, C(O) – C(Ox));   // governed by CC5 and CC6

3.      O:= IT(O, Ox);  C(O) := C(O) U {org(Ox)}       

COT-UNDO (Undo(O), DS) 

1.      I(O) := makeInvese(O);  C(I(O) := C(O) U {O}; // I(O) is the inverse of O

2.      COT-DO(I(O), DS). // precondition (CC1): C(I(O))  DS.

A precondition for invoking COT-DO is that all operations in the context of O must have been executed, i.e. C(O)  DS (CC1). 

 

In COT-DO, the procedure transform( )  is first invoked to transform O against operations in CD = DS - C(O) (according to CC2). This is to upgrade the context of O to DS (as required by CC3), so that the transformed O can be correctly executed in the current DS in the next step. Second, O is executed, and the original form of O is added to DS (to represent the new DS after execution of O).

 

The heart of COT-DO is the recursive procedure transform(O, CD), which transforms an operation O against operations in CD -- the context difference between C(O)  and a new context on which O is to be defined (e.g. DS). This procedure repeats the following steps until CD becomes empty:

(1)   Select and remove an operation Ox from CD, where C(Ox)  C(O) (as required by CC4). One convenient and efficient way to ensure CC4 is to select operations in CD in their execution order determined by CC1.

(2)   The procedure transform is recursively invoked to transform Ox against operations in C(O) - C(Ox) (according to CC5). This is to upgrade Ox to the context of O (as required by CC6), so that they can be used for IT-transformation in the next step.

(3)   After the recursive call to transform( ),  O is IT-transformed against Ox, and the context of O is updated by adding the original of Ox into C(O) (to represent the new context with the effect of Ox).

In COT-UNDO, the undo command Undo(O) is simply interpreted as an inverse of O, denoted as I(O),  with context: C(I(O)) = C(O) U {O}; COT-DO is directly invoked to process I(O).  With explicit and uniformed representation of operation contexts for all types of operation,  inverse and normal operations are treated uniformly in COT-DO. 

 

It has been theoretically verified that the COT algorithm can ensure all context-based conditions [54]. The basic COT algorithm has also been extended to break preconditions for transformation properties (e.g. CP2, IP2, IP3), and integrated with efficient operation buffering schemes to achieve high time and space efficiency in consistency maintenance and group undo [54].

 

[TOP | Previous section | Next section ]

2.12.    How to classify OT control algorithms by their capabilities?

OT control algorithms can be classified according to their capabilities:

(1)      algorithms for consistency maintenance only: e.g. dOPT [6], GOT [43], GOTO [42], etc;

(2)      algorithms for group undo only: e.g. Selective undo [28] and AnyUndo [50];

(3)      algorithms for both consistency maintenance and group undo: e.g. adOPTed [30], and COT [53, 54]; and

(4)      algorithms for operation compression only: e.g. SCOP [33].

 

It is worth noting that the operation compression problem is orthogonal with consistency maintenance and group undo problems, and can be solved independently; but consistency maintenance and group undo problems are intimately related. An integrated OT algorithm capable of solving both do (consistency maintenance) and undo problems is significantly more challenging to design than an OT algorithm capable of solving only one of them.

 

[TOP  | Previous section | Next section ]

2.13.    What kinds of transformation function exist?

There exist two kinds of transformation functions (for consistency maintenance and group undo):

(1)      Inclusion Transformation (IT), denoted as IT(Oa, Ob), which transforms operation Oa against another operation Ob in such a way that the impact of Ob is effectively included.

(2)      Exclusion Transformation (ET): denoted as ET(Oa, Ob), which transforms operation Oa against another operation Ob in such a way that the impact of Ob is effectively excluded.

 

Transformation functions are named differently in different OT systems, and some compound transformation functions may combine both IT and ET functionalities in one function. Table 1 lists some representative OT-supported collaborative editing (CE) systems, and the names of their OT control algorithms and transformation functions.

 

Table 1 Transformation functions used in real OT systems

CE Systems

Control Algorithms

Transformation Functions

GROVE

dOPT [6]

T (IT)

DistEdit

Selective-undo [28]

Transpose (IT and ET)

JOINT EMACS

adOPTed [30]

LTransformation (two IT)

Jupiter

Jupiter OT [25]

xform (IT)

Google Wave

Google Wave OT [59]

Transform (IT)

REDUCE, CodoxWord CoPPT

GOT [43], GOTO [42], AnyUndo [50]

IT and ET

CodoxWord, CoPPT, CoMaya, CoVim, CoFlash, CoCKEditor

COT [53, 54]

IT

 

SDT [20]

IT

 

SOCT2 [37]

Forward Transformation (IT) and

Backward Transformation (ET)

[TOP  | Previous section | Next section ]

2.14.    What are the basic ideas in designing transformation functions?

 A transformation function takes a pair of operations Oa (the transformation target) and Ob (the transformation reference) as inputs and produce Oa as the output. For consistency maintenance, a pre-condition for Oa and Ob is that they must be defined on the same context (for IT functions); this condition is required to ensure the relationships of Oa and Ob in the document state can be correctly determined by simply comparing their parameters. The following basic strategies can be used in designing IT functions (designing ET functions may follow similar strategies):

(1)      compare the parameters of Oa and Ob to determine their relationships in the common document state (e.g. a linear data address space);

(2)      assume Ob has been executed to (conceptually) create a new document state; and

(3)      adjust the parameters of Oa to create a new operation Oa, according to the comparison result in (1) and the impact of the assumed execution of Ob in (2), so that the execution of Oa in the new document state achieve the correct effect (e.g. preserves the original effect of Oa in the old document state). The criteria for the correct effect are application-dependent.

 

[TOP  | Previous section | Next section ]

2.15.    How to design character-wise transformation functions?

Designing character-wise transformation functions (for consistency maintenance) is simple. As an example, for a pair of character-wise operations Ins[p, c] (to insert a character c at the position p) and Del[p] (to delete a character at position p), four IT functions, denoted as Tii, Tid, Tdi, Tdd, can be defined as follows:

 

Tii(Ins[p1,c1], Ins[p2, c2]) {

      if p1 < p2  or (p1 = p2 and u1 > u2)     // breaking insert-tie using user identifiers (u1, u2)

            return Ins[p1, c1];                           // e.g. Tii(Ins[3, “a”], Ins[4, “b”]) = Ins[3, “a”]

      else return Ins[p1+1, c1]; }                //        Tii(Ins[3, “a”], Ins[1, “b”]) = Ins[4, “a”]

 

Tid(Ins[p1,c1], Del[p2]) {          

      if p1 <= p2 return Ins[p1, c1];        //e.g. Tid(Ins[3, “a”], Del[4]) = Ins[3, “a”]

     else return Ins[p1-1, c1]; }          //       Tid(Ins[3, “a”], Del[1] ) = Ins[2, “a”]

 

Tdi(Del[p1], Ins[p2, c2]) {

      if p1 < p2 return Del[p1];                     //e.g.  Tdi(Del[3], Ins[4, “b”]) = Del[3]

      else return Del[p1+1]; }                      //        Tdi(Del[3], Ins[1, “b”]) = Del[4]

 

Tdd(Del[p1], Del[p2]) {

      if p1 < p2 return Del[p1];                     //e.g.   Tdd(Del[3], Del[4]) = Del[3]

      else if p1 > p2 return Del[p1-1];       //         Tdd(Del[3], Del[1]) = Del[2]

      else return I; } // breaking delete-tie using I (identity op)  Tdd(Del[3]. Del[3]) = I 

 

[TOP  | Previous section | Next section ]

2.16.    Why are string-wise transformation functions challenging to design?

Designing string-wise transformation functions is significantly more challenging than designing character-wise operations because:

(1)      a string delete covers a deleting range, which may include the characters in the string as well as the interval positions between characters;

(2)      concurrent string delete operations may arbitrarily overlap with each other and even with concurrent insert operations; and

(3)      a string inserted by a previous insert operation may be changed by following (causally after) insert and delete operations.

 

The above factors make simplistic design methods for character-wise transformation functions unsuitable to string-wise transformation functions (see [43] for an example of string-wise transformation functions). When string-wise transformation functions are designed for group undo as well as consistency maintenance, additional complications (e.g. undo puzzles related to arbitrarily overlapping deletes [50, 54]) come into play.  Whether or not supporting string-wise transformations may have major impact on various aspects (e.g. correctness, complexity and efficiency)  of an OT system.

 

[TOP  | Previous section | Next section ]

2.17.    What are the pre-/post-conditions for transformation functions?   

Transformation functions take input operations and produce transformed output operations. OT algorithm correctness requires those operations to meet certain pre/post conditions:

(1)      Let Oa' = IT(Oa, Ob), where Oa is the transformation target and Ob is the transformation reference.

·        Pre-Condition for IT (Pre-IT): C(Oa) = C(Ob) which means that Oa and Ob can be IT-transformed only if they are context-equivalent.

·        Post-Condition for IT (Post-IT): C(Oa') = C(Oa)  {Ob}, and the effect of Oa' in the document state expressed by C(Oa') is equivalent to the effect of Oa in the document state expressed by C(Oa).

(2)      Let Oa' = ET(Oa, Ob), where Oa is the transformation target and Ob is the transformation reference.

·        Pre-Condition for ET (Pre-ET): C(Oa) = C(Ob) {Ob}, which means that Oa and Ob can be ET-transformed only if Ob is context-preceding Oa.

·        Post-Condition for ET (Post-ET): C(Oa') = C(Ob), and the effect of Oa' in the document state expressed by C(Oa') is equivalent to the effect of Oa in the document state expressed by C(Oa).

[TOP | Previous section | Next section ]

2.18.    Which OT components are responsible for ensuring transformation pre-/post-conditions?    

OT control algorithms are responsible for ensuring transformation pre-conditions, which are imposed on input operations of a transformation function and required to facilitate the correct derivation of the adjustment to the target operation’s parameters according to the impact of the reference operation.

 

Transformation functions are responsible for ensuring transformation post-conditions, which are imposed on the output operation of a transformation function and required to achieve intention-preserving transformation effect.

 

[TOP  | Previous section | Next section ]

2.19.    What are the OT transformation properties and their pre-conditions ?

Transformation properties capture some essential conditions for correct functioning of OT systems [50, 54]. Under certain pre-conditions, transformation functions are required to preserves those properties. All known transformation properties (for consistency maintenance and group undo) and their pre-conditions are listed below.

(1)      Reversibility Property (RP): Given two context-equivalent operations Oa and Ob, it must be that Oa = ET(IT(Oa, Ob), Ob);

 

RP Pre-Condition (RP-PC): transformation functions are required to preserve RP only if the OT system uses both IT and ET functions.

(2)      Convergence Property 1 (CP1): Given a document state S and two context-equivalent operations Oa and Ob, if Oa' = IT(Oa, Ob), and Ob' = IT(Ob, Oa), then 

S  Oa  Ob' = SOb  Oa'

which means that sequence Oa  Ob' is equivalent to sequence Ob  Oa' in terms of their effects on S.

 

CP1 Pre-Condition (CP1-PC): transformation functions are required to preserve CP1 only if the OT system allows two operations Oa and Ob to be IT-transformed in different orders.

(3)      Convergence Property 2 (CP2): Given three context-equivalent operations O, Oa, and Ob, if Oa' = IT (Oa, Ob), and Ob' = IT(Ob, Oa), then  

IT(IT(O, Oa), Ob') = IT(IT(O, Ob), Oa')

which means that the outcome of transforming O against Oa and Ob in sequence equals the outcome of transforming O against Ob and Oa' in sequence.

 

CP2 Pre-Condition (CP2-PC): transformation functions are required to preserve CP2 only if the OT system allows two operations Oa and Ob to be IT-transformed in different contexts, e.g. IT(Oa, Ob) is invoked in one transformation path, while IT(Oa', Ob') is invoked in another transformation path.  Note: this CP2 pre-condition does not directly correspond to the definition of CP2 (so not intuitive to understand); the reader is referred to [54] for detailed analysis and theoretic verification of this pre-condition.

(4)      Inverse Property 1 (IP1): Given a document state S and the sequence of operations , we have     

which means sequence  is equivalent to a single identity operation I with respect to the effect on the document state.

 

IP1 Pre-condition (IP1-PC): transformation functions are required to preserve IP1 only if the OT system uses inverse operations to achieve the undo effect. Note: IP1 is used to govern the creation of inverse operations, but it is unrelated to the definition of transformation functions.

(5)      Inverse Property 2 (IP2): Given any operation O and a pair of operations  and , where O and Ox are context-equivalent, it must be that

which means that the outcome of transforming O against  and in sequence must be equal to O. In other words, the sequence of  and  is equivalent to a single identity operation I with respect to the effect in transformation.

 

IP2 Pre-condition (IP2-PC): transformation functions are required to preserve IP2 only if the OT system allows an operation to be transformed against and  one by one.

(6)      Inverse Property (IP3): Given two context-equivalent operations  and , if ,  and , then  

 

or

which means that , the outcome of IT-transforming the inverse operation  against , must be equal to , the inverse of IT-transforming  against .

 

IP3 Pre-Condition (IP3-PC): transformation functions are required to preserve IP3 only if the OT system allows an inverse operation to be transformed against an operation  and   is defined on the same context as, where .

 

It is worth mentioning that  

·        convergence properties, CP1 and CP2, are required for achieving convergence;

·        inverse properties, IP1, IP2 and IP3, are required to support  group undo  [50, 54].

 

[TOP  | Previous section | Next section]

2.20.    Which OT components are responsible for achieving transformation properties?

Transformation properties can be achieved by:

(1)      designing transformation functions that can preserve those properties,  or

(2)      designing control algorithms that can break the pre-conditions of those properties. 

 

Past research has shown that it is relatively easy to design transformation functions capable of preserving CP1 (e.g. the simple character-wise transformation functions able to preserve CP1), but non-trivial to design and verify transformation functions capable of preserving CP2, IP2 and IP3. It has also been known that ensuring RP by transformation functions is difficult due to lossy transformations [43, 50]. Therefore, it is advisable to solve RP, CP2, IP2 and IP3 at the control algorithm level, which has the benefits of simplifying the design of transformation functions and improving system efficiency [54]. A combined use of both control algorithms and transformation functions for achieving transformation properties is common in real OT systems.

 

[TOP  | Previous section | Next section ]

 

2.21.    How to break pre-conditions for both CP1 and CP2? 

One basic idea of breaking preconditions of both CP1 and CP2 is to ensure all concurrent operations are transformed in the same total order at all sites, i.e. if  Oa and Ob are concurrent and Oa is totally ordered before Ob,  then Ob can be transformed against Oa  (T(Ob, Oa)),  but not the other way around (T(Oa, Ob)).  This idea has been used in the GOT system [43], which uses a undo-redo scheme to achieve totally ordered transformation and execution effect at all sites. Since the GOT system never transforms a pair of operations in different orders, the precondition for CP1 is thus broken.  Breaking the precondition of CP1 also implies breaking the precondition of CP2, i.e. the GOT system never transforms a pair of operations in different contexts as well. Otherwise, suppose, under the control of the GOT algorithm,  Oa and Ob were transformed in different contexts, e.g.  T(Oa, Ob) and T(Oa’, Ob’), where  C(Oa) ≠ C(Oa’). There must be at least one operation Ox that is not in both C(Oa) and C(Oa’) and Ox must be concurrent with Oa (otherwise Ox would be in both C(Oa) and C(Oa’) by the definition of operation context), which implies that Oa is transformed against Ox before Ob in one path (in the case of T(Oa’, Ob’)), but Oa is transformed against Ob before Ox in another path (in the case of T(Oa, Ob)), but this contradicts to the basic property of the GOT system – it  never transforms a pair of operations in different orders.

 

[TOP  | Previous section | Next section ]

2.22.    How to break the precondition of CP2 ?

There are multiple solutions for breaking the precondition of CP2 [21, 25, 33, 43, 54, 58, 59].   In the COT algorithm [53, 54],  for example, the basic idea of breaking the precondition of CP2 is to impose constraints on the order of remote operation execution (governed by CC1) and the order of operation transformation (governed by CC4) [54]. 

 

To give a concrete example, we apply the COT algorithm to a scenario with three concurrent/context-independent operations: O1, O2, and O3 generated from three collaborating sites (e.g. the three operations in the classic False-Tie (FT) scenario). For such three operations, there exist six possible execution orders that respect their causal/context dependency relationships:

 

  1. O1, O2, O3
  2. O1, O3, O2
  3. O2, O1, O3
  4. O2, O3, O1
  5. O3, O1, O2
  6. O3, O2, O1

 

If an OT system (e.g. those based on adOPTed [30], and GOTO [42]) allows all six possible orders in execution and transformation, then its IT functions have to meet both CP1 and CP2 in order to achieve convergence.  However, a COT-based system is able to restrict operation execution orders to a subset of these six possible orders, e.g. the following  group of three permissible-execution orders:

 

  1. O1, O2, O3
  2. O2, O1, O3
  3. O3, O1, O2

 

where each execution order meets the following conditions (based on Definition 8 in [54]): a local operation is allowed to be executed (immediately after generation) in any order, but remote operations must be executed in an order that respects the total ordering O1→O2→O3.  For example, in the execution order "O2, O1, O3", the local operation O2 is executed first (without being constrained by the total ordering), but remote operations O1 and O3 are executed in an order that respects O1O3 (for discussions on how to restrict operation execution orders to a well-defined subset like the three in this example, please read Section 7.2 of [54]). 

 

Furthermore, a COT-based OT system can also use the same total ordering used for determining the permissible-execution orders (e.g. O1→O2→O3 in the running example) to define permissible-transformation orders (based on Definition 9 in [54]): to transform O against a group of operations in CD (in Procedure 2 Transform(O, CD) in [54]), the transformation order must respect the total ordering ,  i.e. for any Oa and Ob in CD, if   OaOb, then O is transformed against Oa before Ob. For an  operation Ox in CD, O can be transformed against Ox even if OxO (note: there can be at most one such operation in CD under the constraint of permissible-execution orders; also pay attention to the difference between this permissible-transformation ordering and the total transformation ordering used in the GOT system for breaking the precondition of CP1). Under these permissible-transformation order constraints, each operation in the three permissible-execution orders of our running example will be transformed as follows:

 

  1. O1 (no transformation);   O2' = T(O2,O1);  O3' = T(T(O3,O1), T(O2,O1))
  2. O2 (no transformation);  O1' = T(O1,O2);  O3' = T(T(O3,O1), T(O2,O1))
  3. O3 (no transformation);  O1' = T(O1,O3); O2' = T(T(O2,O1), T(O3, O1))

 

It can be checked that all above transformations meet the permissible-transformation ordering constraint, with respect to the total ordering O1→O2→O3: 

  1. In the execution order "O1, O2, O3," operations are transformed in the order of their execution, which is consistent with the total ordering: O1→O2→O3.   
  2. In the execution order "O2, O1, O3," O1 is allowed to be transformed against O2 even though O1O2; but when O3 is to be transformed against a group of two operations O2 and O1, it is transformed against  O1 before O2 (though O2 is executed before O1) because O1O2. By reordering O2 and O1 in the process of transforming O3, we force O3 to be transformed against O1 in the same context (and against O1 and O2 in the same order) as that in Case 1.
  3. In the execution order "O3, O1, O2," O1 is allowed to be transformed against O3 even though O1O3; but when O2 is to be transformed against a group of two operations O3 and O1, it is transformed against O1 before O3 (though O3 is executed before O1) because O1O3.  By reordering O3 and O1 in the process of transforming O2, we force O2 to be transformed against O3 in the same context as that of transforming O3 against O2 in Cases 1 & 2.

 

By examining all transformations involved in these three execution orders, one can verify that a COT-based system, with the capability of enforcing these permissible execution and transformation orders, never transforms a pair of operations in different contexts, thus breaking  the precondition of CP2. 

 

In fact, for this particular three-operation scenario, there are six possible total orderings, and each of them has three permissible-execution orders and corresponding permissible-transformations (according to Definitions 8 and 9 in [54]), which are all shown in Table 2.  For breaking the precondition of CP2, a COT-based system should ensure only one of those six total orders and its corresponding permissible execution and transformation orders could  occur in a session (note: it does not matter which specific total order and corresponding execution and transformation orders actually occur in a session).  By examining all transformations under each of the possible total orders, one can verify that, no matter which particular total order actually occurs in a session, a COT-based system would never transform a pair of operations in different contexts, thus breaking the precondition of CP2.  The reader is referred to [54] for a theoretic proof that shows the COT algorithm is able to break the precondition of CP2 under any collaborating scenario, and for discussions on how to determine the total ordering and permissible execution and transformation orders in real-time collaborative editing systems (e.g. CodoxWord).   The ability to break the precondition of CP2 can be used to achieve consistency without solving the FT problem.

 

Table 2  Possible total orders and permissible execution and transformation orders for the 3-operation scenario under the control of the COT algorithm.

Possible Total Orders: for N context-equivalent operations, there are N! total orderings that respects their context-dependency relations, but, with proper control mechanisms,  only one of them may actually occur in a session. 

 

E.g. there are 6 total orderings for 3 context-independent operations (e.g. in the classic FT scenario).

Permissible-Execution Orders (Definition 8 in [54]):  local operations are executed without order constraint;  remote operations must be executed in the order determined by a total ordering , i.e. if OxOy, Ox is executed before Oy. 

 

E.g.  there are  3 permissible-execution orders for each of the total ordering of three context-independent operations.  

Permissible-Transformation Orders (Definition 9 in [ 54]): To transform O against a group of operations in CD, the transformation order must respect the  same total order (used for determining permissible-execution orders), i.e. for any Oa and Ob in CD, if Oa Ob, then O is transformed against Oa before Ob. 

 

E.g. under the total ordering O1O2O3, and in the permissible execution order O3,O1,O2,  O2 must be transformed against O1 before O3 because O1O3 (as shown in T(T(O2,O1), T(O3, O1))).

O1 O2O3

O1, O2, O3

O1;  T(O2,O1);  T(T(O3,O1), T(O2,O1))

O2, O1, O3

O2;  T(O1,O2); T(T(O3,O1), T(O2,O1))

O3, O1, O2

O3,  T(O1,O3); T(T(O2,O1), T(O3, O1))

O1O3O2

 

 

O1, O3, O2

O1; T(O3, O1); T(T(O2,O1), T(O3,O1))

O2, O1, O3

O2; T(O1,O2); T(T(O3,O1), T(O2,O1))

O3, O1, O2

O3; T(O1,O3); T(T(O2,O1), T(O3, O1))

 

O2O1O3

 

O1, O2, O3

O1; T(O2, O1); T(T(O3,O2), T(O1,O2))

O2, O1, O3

O2; T(O1,O2); T(T(O3,O2), T(O1,O2))

O3, O2, O1

O3; T(O2,O3); T(T(O1,O2), T(O3,O2))

 

O2O3O1

O1, O2, O3

O1; T(O2, O1); T(T(O3,O2), T(O1,O2))

O2, O3, O1

O2; T(O3,O2); T(T(O1,O2), T(O3,O2))

O3, O2, O1

O3; T(O2,O3); T(T(O1,O2), T(O3,O2))

 

 

O3O1O2

O1, O3, O2

O1; T(O3, O1); T(T(O2,O3), T(O1,O3))

O2, O3, O1

O2; T(O3,O2); T(T(O1,O3), T(O2,O3))

O3, O1, O2

O3; T(O1,O3); T(T(O2,O3), T(O1,O3))

 

 

O3O2O1

O1, O3, O2

O1; T(O3, O1); T(T(O2,O3), T(O1,O3))

O2, O3, O1

O2; T(O3,O2); T(T(O1,O3), T(O2,O3))

O3, O2, O1

O3; T(O2,O3); T(T(O1,O3), T(O2,O3))

 

[TOP  | Previous section | Next section ]

 

2.1.How to deal with the complexity in OT system design?

In the spirit of "divide and conquer" in designing complex systems, a strategy that separates control algorithms and transformation functions has been commonly used to deal with the complexity of OT systems. Separating generic OT capabilities (in a Generic Collaboration Engine) and application-specific OT capabilities (in Collaboration Adaptors) can reduce the complexity of OT system design and increase the reusability of OT components.

 

Some problems are relevant to only one or a few components of the OT system, so solutions to them are best localized within those components as well, to avoid global changes to other parts of the OT system. For example, the extension of OT address space from a single linear space to a hierarchy of multiple linear domains is relevant to operation addresses only, and the solution can be encapsulated in a component for mapping vector and singular addresses [52], without affecting existing OT control algorithms or transformation functions. For another example,  the  False-Tie (FT) problem is relevant to Insert and Delete operations only, so an FT solution localized in those transformation functions related to Insert and Delete operations can avoid causing any change to other parts of the system (e.g. control algorithms, or transformation functions unrelated to Insert and Delete, or data/operation models of the system) [ 43, 53].  

 

Dividing responsibilities among multiple components deserves careful consideration in OT system design.  A difficult issue in one OT component may be resolved easily, or avoided altogether, if this issue is addressed from a different OT component. For example, it is known that devising and proving transformation functions capable of preserving properties CP2, IP2 and IP3 are difficult. However, these difficulties can be avoided by devising control algorithms (like COT [53, 54]) capable of breaking the pre-conditions for requiring transformation function to preserve these properties; it is also easier to prove a control algorithm is capable of breaking the pre-conditions for these properties, than to prove transformation functions are capable of preserving them.

 

Some OT issues are intimately related, and a solution to one issue, if examined in isolation, is unlikely to be correct or complete and may even cause unexpected adverse impact on solutions to other issues. For example, a solution that works well for consistency maintenance (do), may fail when both do and undo problems are considered; and an undo solution (e.g. preserving IP2) may violate the solution to consistency maintenance [46]. A complete OT solution to both do and undo problems is significantly more difficult to design than a partial solution to only one of them [50, 53].

 

[TOP  | Previous section | Next section ]

 

2.2.What issues to consider in evaluating OT system time efficiency?

One measurement of OT system time efficiency is the total number of IT/ET functions invoked to transform a normal operation (for consistency maintenance) or an inverse operation (for group undo). Various linear/nonlinear worst-case theoretic time complexity claims have been reported under a variety of conditions, including:

·     linear complexity for consistency maintenance [56, 31];

·     linear complexity for chronologic undo [30, 50, 54];

·     non-linear complexity for anyundo [50, 54];

·     linear complexity for a special kind of selective undo [32].   

 

However, those worst-case theoretic time complexity claims may not tell the complete or the most important story about time efficiency issues in real OT systems.  For OT time efficiency evaluation to be meaningful in theory and useful in practice, the following issues deserve special attention:  

·     What input variables are used in theoretic complexity claims? In OT literature, the theoretic time complexity has been defined on a variety of input variables that have quite different implications on time efficiency in real OT systems. In most OT systems (e.g.  [29, 30, 46, 50, 54]),  time complexity is  defined in relation to the number of operations that are concurrent or context-independent with the operation in concern, which is independent of sequential operations and the session duration time. In some OT systems (e.g. [31, 32]), however, time complexity is  defined in relation to the total number of operations accumulated in the history buffer, which depends on the session duration time and all  operations generated in a session, regardless whether those operations are sequential or concurrent.  In real-time collaboration sessions, the number of concurrent operations is often much smaller than the total number of operations accumulated in the history. Furthermore, the number of concurrent operations can be bounded by the propagation-time (e.g. <200ms) between any pair of collaborating users and the number of collaborating users (e.g. <5) in a session; but the total number of operations (i.e. the size of history) grows without limit as long as the session continues. Therefore, OT systems with time complexity bounded by concurrency often perform much more efficiently than those with the same time complexity but defined on the history size. In assessing the actual time efficiency of real OT systems, one should not only examine whether the theoretic complexity is linear or non-liner, but also differentiate what input variables were used in defining the theoretic complexity.

·     Under what conditions is the time complexity achieved? OT systems are differentiated by their functionalities/capabilities, which are important conditions in determining OT complexity, efficiency and other aspects (even correctness). For instance, group undo has been supported by various OT systems under different undo capabilities and conditions, resulting in different time complexities. Under the same undo effects and undo properties but different undo modes, group undo has been achieved with a  linear time complexity for chronological undo [30, 50, 54], and with a non-linear time complexity for  any-undo or selective undo [50, 54]. A linear time complexity has been reported for supporting a kind of selective undo under different undo effects and properties (and other conditions) [31, 32].  In evaluating time efficiency of OT systems, one should consider under what conditions is certain time complexity achieved and pay attention to those conditions (e.g. undo modes, effects, properties, string- or character-wise operations, etc.) that have played an important part in determining OT complexity and efficiency.   

·      Whether string-wise operation transformation can be supported?  String-wise transformations are more efficient than character-wise transformations because the cost of invoking a transformation function for either string-wise or character-wise operations is basically the same, but a single string-wise transformation can represent a large number of character-wise transformations, and hence significantly reduce the total number of transformations. Most OT control algorithms are independent of the types of transformation functions (which may support string- or character-wise insert/delete/update/etc operations defined on 1D/2D or hieratical addressing models) [28, 29, 30, 46, 50, 52, 54, 57]; some OT systems mix control algorithms and transformation functions and support only character-wise operations [31, 32]. Generally, OT systems capable of supporting string-wise operations perform more efficiently than those capable of supporting only character-wise transformations under the same theoretic time complexity. In evaluating time efficiency of OT systems, one should examine not only whether the transformation number is linear or nonlinear, but also whether the transformation is string-wise or character-wise.  

·       Whether garbage collection is applicable? Garbage collection can be used to reduce the total number of operations to be examined in transformation, thus increasing the time (and space) efficiency.  However, garbage collection is applicable only if the OT system works by performing transformations among concurrent/context-independent operations [43, 56]. If an OT system works by performing transformations among all accumulated operations in the history buffer (e.g. maintaining executed operations in some special orders such that all operations are potentially needed for future transformations), it is unable to  take advantage of garbage collection for the purpose of reducing time and space complexity.  

·     Whether operation compression is applicable? Operation compression [34,35] is an effective way of reducing the total number of accumulated operations, particularly useful in OT-supported non-real-time or mobile collaborative editing systems.   However, operation compression is applicable only if the OT system supports string-wise operations (for both transformation and execution). If an OT system supports character-wise operations only, it will be unable to take advantage of operation compression. 

·      How much does it cost per transformation in a real OT system?  Last but not least, one should realize that the cost of one transformation is cheap as it involves only a few arithmetic addition/subtraction and comparison operations (see Q&A 2.15).  If we assume 100 instructions per IT function invocation, which is quite conservative considering the small number of simple operations that have to be performed in each IT, then for a computer of 1G instructions per second (e.g. a single 2-3 GHz CPU capable of performing 2-3 CPI (Cycle Per Instruction)), 10 million IT transformations per second can be achieved, i.e. 10MIT/s, or 1 million per 100 mini-second (the time for responding a local operation), i.e. 1MIT/100ms. With these roughly estimated numbers in mind, one can assess whether and when the theoretic worst-case time complexity should be worried about in a particular OT system. In reality, time efficiency of a real OT system has much more to do with its practical implementation than the theoretic worst-case complexity.  One example high performance OT implementation is the Generic Collaboration Engine that has the power to drive a wide range of real-world collaborative applications (e.g. CodoxWord, CoMaya, and CoFlash, etc.).

 

[TOP | Previous section | Next section ]

 

2.3.What are the space efficiency issues of an OT system?

Space efficiency of an OT system can be measured by the number of operations that must be saved for the purpose of transformation. Some OT systems save only transformed (executed) operations [6, 43, 37, 25, 30, 50, 59].  For the purpose of consistency maintenance, operations that are potentially concurrent or context-independent [54] to future arriving operations must be saved. For group undo, operations that are potentially undoable by the user and those that may be involved in transforming an undo operation must be saved. Operations that are no longer needed in future transformation (for either consistency maintenance or undo) can be collected as garbage to save space [43]. In OT-supported non-real-time systems, operation compression can be used to reduce the total number of accumulated operations for saving both space and time.

 

[TOP | Previous section | Next section ]

2.4.What attributes can be used to differentiate OT systems?

Some main attributes for differentiating OT systems are as follows:

(1)      Capabilities: OT systems may support a variety of collaboration capabilities. For instance, some OT systems are capable of supporting consistency maintenance, group undo, operation compression, and/or others. Capability requirements on an OT system may influence the design of both control algorithms and transformation functions.

(1)      Operation models: some OT systems support only two primitive insert and delete operations; some others support, in addition to insert and delete, more primitive operations, such as update, lock, point, and/or other application-specific operations. Different operation models require different transformation functions, but have no influence on control algorithms.

(2)      Data models: Different data models may require different transformation functions.

a.    Single-object vs sequence-object addressing: some OT systems support single-object (e.g. character-wise) operations only; some support sequence-object (e.g. string-wise) operations;

b.   1D vs 2D addressing: some OT systems support one-dimensional (1D) address space (e.g. a sequence of characters/objects); some support two-dimensional (2D) address space (e.g. spreadsheets, and tables);

c.    Flat vs hierarchical addressing domains: some OT systems support a single address space; some support a hierarchy (or tree) of multiple address domains;

d.   Independent vs dependent objects: some OT systems support a collection of objects that are independent in the sense that an update of one object’s attributes has no impact on the attributes of another object) [42]; some support a graph of objects that are dependent in the sense that an update of one object’s attributes leads to the change of other objects’ attributes [3].

(3)      Responsibility division between control algorithms and transformation functions: OT systems that have the same capability, operation and data models, may still differ due to different division of responsibilities (in the form of transformation conditions and properties) between control algorithms and transformation functions, which could lead to varying complexity in different OT components.

(4)      Tradeoffs in time-space complexity: some OT systems achieve high time efficiency (e.g. linear time complexity for consistency maintenance [54]) at the expense of space efficiency, e.g. by saving original and (selected) intermediate transformed operations; some achieve high space efficiency (by saving original or executed operations only) at the expense of time efficiency.

(5)      Real-time vs non-real-time support: some OT systems support real-time collaboration only; some support non-real-time collaboration only; some support both real-time and non-real-time (anytime) collaboration.

(6)      Homogenous vs heterogeneous design: most OT systems are homogenous in the sense the same OT algorithms are used at all collaborating sites; but some are heterogeneous as different OT algorithms are used for different (e.g. client and server) sites, e.g. Jupiter OT [25], Google Wave OT [59], and NICE [33].

 

[TOP  | Previous section | Next section ]

 

2.5.What is the role of OT in the Generic Collaboration Engine (GCE) technology?

OT is the empowering-technology in the Generic Collaboration Engine (GCE) which is a re-usable collaborative software component that encapsulates a comprehensive set of  advanced collaboration capabilities [43, 49, 50, 51, 52, 54]. The GCE has been used to support a wide range of collaborative editing systems, including collaborative text editors (e.g. CoVim), graphic/multimedia editors (e.g. CoFlash), word processors (e.g. CodoxWord), slide creation and presentation tools (e.g. CoPowerPoint),  spreadsheet editors (e.g. CoCalc), and digital media design tools (e.g. CoMaya).  A GCE SDK (Software Development Kit) is available for supporting GCE-based collaborative application development.

[TOP | Previous section | Next section ]

 

2.6.What is the role of OT in the Transparent Adaptation (TA) technology?

OT is the cornerstone of the Transparent Adaptation (TA) technology [52, 57], which can be used to build collaborative applications by integrating advanced collaboration capabilities with existing single-user interactive applications, without making any change to the source code of the single-user application, or reinventing the wheel for conventional functionalities or collaboration capabilities [52, 57]. The TA-based collaborative application reference architecture is shown in Figure 6. The reference architecture consists of three layers:

 

TA.jpg

Figure 6. The Reference Architecture of TA-based collaborative applications

(1)      Single-user Application (SA), which can be any existing or new single-user application (e.g. MS Word, PowerPoint). This component provides conventional single-user functionalities and interface features, but does not need to have any knowledge about multi-user collaboration.

(2)      Collaboration Adaptor (CA), which provides application-specific collaboration capabilities. The CA component interacts with the API (Application Programming Interface) to augment the SA with collaboration capabilities, without making any change to the source code of the SA. The CA plays a central role in converting the SA into a CoSA by bridging the SA and the underlying OT-powered GCE, and in extending generic OT-based collaboration capabilities to support specific single-user applications. 

(3)      Generic Collaboration Engine (GCE), which provides OT-powered collaboration capabilities in consistency maintenance, concurrency control, workspace awareness, interaction control, etc. This component is generic and can be reused in adapting a wide range of applications.  

 

The TA reference architecture separates single-user functionalities (SA) from multi-user collaboration capabilities, and separates application-specific collaboration capabilities (CA) from generic collaboration capabilities (GCE). Based on this architecture and the reusable GCE component, the task of converting a single-user application is reduced into the task of investigating, designing, and implementing a new CA for this new application. 

 

Apart from TA-related publications [1, 2, 52, 60, 61, 62, 63], the source code of a real-time collaborative rich-text editor CoRTE is provided to illustrate how to use the TA and the GCE Software Development Kit to build real-world collaborative applications [57].

 

[TOP | Previous section | Next section ]

 

2.7.What is the role of the OTXplorer in OT research and design?

The OTXplorer (Operational Transformation eXplorer) is a web-based software tool for benchmarking and evaluating real OT systems.  The OTXplorer has been designed to support:

·        researcher to explore and benchmark OT issues and solutions,  and

·        developers to test and evaluate real OT implementations.

 

In OT research literature, simple collaborative editing scenarios have often been used to illustrate why an OT system works or fails. In OT system design, however, a real implementation and comprehensive testing scenarios are crucial in validating a design. Tools, like OTXplorer, for evaluating OT system design and implementation play an important role in OT research and design.

 

The OTXploer has a STD (Space-Time Diagram)-based GUI (Graphic User Interface), as shown in Figure 7, which allows users to draw arbitrary collaborative editing scenarios and view operation transformation and execution results produced by real OT implementations (e.g. the GCE). With the support of the OTXploer, a STD-based real-time collaborative editing scenario can be manually drawn by the user, or automatically created according to user-provided operation causal relation expressions. Given a user-drawn scenario or a user-provided causal relation expression, the OTXploer can automatically validate them and derive all valid operation sequences and scenarios, which can be used for selective or exhaustive case testing.  The OTXploer system also contains a comprehensive suite of benchmarking scenarios for validating OT algorithmic correctness requirements (for both consistency maintenance and group undo, including context-based conditions, and transformation properties and conditions) and solutions to all known OT puzzles.

 

The OTXplorer can translate STD-based scenarios into testing cases, drive real OT implementations to run the testing cases, and finally display operation transformation and execution results in the STD scenarios. Detailed traces of internal working of OT algorithm components are also provided to support debugging (for OT system developers).  Multiple OT implementations (e.g. COT-based GCE, GOTO-ANYUNDO-based GCE) can be plugged into the same OTXplorer.  A public programming interface is being designed to  support plugging OT implementations into the OTXplorer for comparison study.

 

Figure 7. The OTXplorer GUI based on  Space-Time Diagram.

 

[TOP  | Previous section | Next section ]

 

3.      OT correctness 

 

3.1.What are the multi-facets of  OT correctness?

OT correctness has two facets:

(1)      One is the application correctness (“to get the right OT”), which concerns with whether an OT system meets the requirements of the target application.  Consistency maintenance requirements (e.g. convergence and intention preservation) and group undo requirements (e.g. undo effect and undo property) are examples of application correctness requirements.  Different applications may impose different correctness requirements on OT, and an OT system is application-correct if it meets the correctness requirements imposed by its target applications.  Whether an application correctness requirement is relevant to a specific OT system depends on whether the target application of this OT system needs it.  In evaluating and selecting OT systems for specific applications, one ought to understand the needs of the target application in the first place.

(2)      The other is the algorithm correctness (“to get the OT right”), which concerns with whether the design of an OT system satisfies the constraints imposed by various algorithmic components in the OT system.  Transformation conditions and properties (e.g. context-based conditions, convergence properties, and inverse properties) are examples of OT algorithm correctness requirements.  Different OT system designs may result in different algorithmic components and impose different constraints among those components, and an OT system is algorithm-correct if its algorithmic components meet the constraints imposed by those components themselves.   Whether an algorithm correctness constraint is relevant to a specific OT system depends on whether the design of this OT system imposes such a constraint on its components (provided the OT system has those relevant components).  

Differentiating the multi-facets of OT correctness is important for properly evaluating OT correctness claims/results in research and in selecting OT systems for practical usage. 

There have been quite some controversies and misconceptions/myths related to OT correctness in literature.  Various OT correctness criteria have been proposed, but for any OT correctness criterion to be meaningful or relevant, it has to be justified by either application needs or algorithm design requirements. Various OT systems have been proposed for supporting a variety of applications and using different design approaches; and there has been no single application or algorithm correctness requirement that is unconditionally required for all OT systems. Many existing OT systems are correct in terms of meeting their target application requirements and meeting their algorithm design constraints when combined with suitably matching OT components (algorithms or functions).   Other views on OT correctness can be found in [13, 15, 18, 22].

 

[TOP  | Previous section ]

 

3.2.What are the consistency-related application correctness requirements?

Real-time collaborative editors may impose the following consistency-related correctness requirements [6, 43]:

(1)      Causality-preservation requires operations to be executed in their causal-effect orders (based on the happen-before relation [11]). This property is required to help the system to function properly and the user to maintain a logical mental model about what is going on during a collaboration session. An example scenario for illustrating causality-preservation is given in Figure 8.

Figure 8.  A scenario for illustrating causality-preservation requirement

(2)      Convergence requires the copies of the shared document be identical when the same group of operations has been performed, particularly at the end of a collaboration session. This property is needed for those applications in which the identical final result is essential (e.g. text document editing). An example scenario for illustrating convergence requirement is given in Figure 9.

Figure 9.  A scenario for illustrating convergence requirement

(3)      Intention-preservation requires the intention of an operation be preserved at all sites, regardless of interleaving execution of concurrent operations. The intention of an operation O is defined as the execution effect that can be achieved by performing O on the document state from which O was generated. This property imposes a constraint on operation execution effects in collaborative editing: the execution effect of an operation at remote sites should achieve the same effect as defined when the operation was generated at the local site. This property is desirable to make collaborative editing effects as meaningful as individual editing effects. An example scenario for illustrating intention-preservation requirement is given in Figure 10.

Figure 10. A scenario for illustrating intention-preservation requirement

OT is capable of achieving convergence and intention-preservation in a range of collaborative editing systems (e.g. group text editors), but incapable of achieving causality-preservation (so OT must be integrated with a suitable distributed computing technique to preserve causality). Convergence can also be achieved by other techniques (e.g. by serialization protocols), so, if the group text editor (e.g. REDUCE [43]) has used other techniques to achieve convergence, the OT system is not required to achieve convergence.

[TOP | Previous section ]

3.3.        What are the undo-related application correctness requirements?

OT has been used to support user-initiated undo (called group undo) in collaborative editors, which impose additional correctness requirements [50, 54]: 

(1)      One is the undo effect, which requires that undoing an operation O achieves the effect of eliminating the effect of O but retains the effects of other operations in the document. In other words, the effect of undoing O is to transform the document state into one that it would have gone to if O had never been performed but other operations had been performed. This undo effect is consistent with the linear undo effect in single-user editing environments, and also suitable for non-linear undo (e.g. “undoing any operation at any time”) in multi-user and concurrent editing environments.

(2)      The other is the undo property, which requires that the document be restored to any previous state by undoing all operations executed after that state, regardless of the order in which those operations are undone. This property is required to ensure the capability of “restoring any prior state”, which is essential for an undo solution to support error-recovery and alternative exploration.

An example illustrating the undo effect and undo property is given in Figure 11:

Figure 11  A scenario for illustrating undo effect and undo property.

It has been shown in [50] that OT-based undo solutions are able to meet undo effect and undo property requirements.  The basic idea of using OT to achieve the undo effect is illustrated in Figure 2.

[TOP  | Previous section ]

3.4.        What are the compression-related application correctness requirements?

OT has also been applied to achieve operation compression in group text editors (e.g. FORCE in [35]), which imposes another correctness requirement:

·        Compression Effect: The effect of compressing a group of operations GO should retain the original effect of GO while reducing the number of operations in GO. More precisely, given a document state S and a group of operations GO, if GO = compress(GO), it must be that:  |GO'| ≤ |GO| and S GO = S GO, which means the compressed group of operations GO may have a smaller number of operations but  equivalent effect compared to the original group of operations GO.

An example illustrating the compression effect is given in Figure 12:

Figure 12 A scenario for illustrating compression effect.

All compression solutions (OT-based or not) are required to meet the above operation compression effect imposed by applications.  The basic idea of using OT to achieve the compression effect is illustrated in Figure 3.

[TOP  | Previous section ]

3.5.        What are the OT-related application correctness requirements?

Collaborative applications may impose a variety of correctness requirements on the underlying supporting techniques. Some requirements may be related to OT; some may not. All known OT-related application correctness requirements are summarized in the table below.

Table 3. OT-related application correctness requirements

Correctness

Requirements

Brief Description

Reference Articles

Convergence

Replicas of the shared document should be identical when the same group of operations has been performed on all replicas.

Ellis [6] and

Sun et al. [43]

Intention

Preservation

The execution effect of an operation at remote sites should achieve the same effect as when the operation was generated at the local site, regardless of interleaving executions of concurrent operations.

Sun et al. [38, 43]

Undo Effect

The effect of undoing an operation O should eliminate the effect of O but retain the effects of other operations in the document, which will transform the document state into one that it would have gone to if O had never been performed but other operations had been performed.

Prakash [28],  Sun [50]

Undo Property

An undo solution should be able to restore the document to any previous state by undoing all operations executed after that previous state, regardless of the order in which those operations are undone.

Sun [50]

Compress Effect

The effect of compressing a group of operations GO should retain the original effect of GO while reducing the number of operations in GO. 

Shen and Sun [33]

It should be pointed out that the requirements in this table may not be complete; additional application correctness requirements could be discovered or imposed out of the needs of new collaborative applications. 

 [TOP  | Previous section ]

3.6.        Does an OT system must meet all application correctness requirements?

No. Whether an OT system is required to meet certain application correctness requirements depends on the purpose for which the OT system is designed. For example, an OT system designed only for supporting consistency maintenance needs not meet “undo effect”, “undo property”, or “compression effect” correctness requirement. Some requirements (e.g. convergence) can also be achieved by other techniques (e.g. undo/redo, serialization); so if other techniques have been used for supporting those requirements, there is no need to require OT to meet them. Some requirements (e.g. intention preservation) may take a variety of forms, which allow different OT supports. Some application correctness requirements (e.g. causality preservation) cannot be achieved by OT, hence irrelevant to OT. 

 

[TOP  | Previous section ]

 

3.7.        Does a collaborative editor must meet all consistency correctness requirements?

No. Despite the general applicability of the three consistency-related correctness requirements to a range of collaborative editing applications, they are not unconditionally required by every collaborative editing application under all circumstances.

(1)      Causality preservation based on the “happen-before” relation [11] may be too restrictive to some applications. It is well-known that the “happen-before” relation may not capture the real causal relationship among events in distributed systems. Operations with “happen-before” relations may not have any real causal- or data-dependency relation, so causality-preserving execution order may not be strictly necessary for them. 

(1)      Convergence may not be required by collaborative editing systems in which an identical final result is not essential. For example, in collaborative bitmap drawing tools, concurrent overlapping drawings may result in divergent results in overlapping pixels, but such divergence is tolerable, and convergence at the fine-grained pixel level is not essential for draft drawing applications. For another example, in text-based chatting applications (a special kind of collaborative text editing tool), concurrent chatting statements may be inserted on chatting UIs in different orders at different sites, resulting in non-identical chatting logs, but such divergence does not cause any problem to users since chatting statements are properly tagged (e.g. with user names and times).  

(2)      The notion of intention preservation captures only part of a general requirement on operation effects in collaborative editing environments, but leaves unspecified details of operation effects in specific applications. Therefore, intention preservation can be broadly interpreted and specialized in a variety of ways in concrete applications.  In fact, intention preservation has been specialized in different ways in group text editors [43] and graphics editors [47], respectively. Also, weaker forms of intention preservation (e.g. preserving part of the original operation effect in the face of conflict) are also acceptable in some collaborative editing applications [3].

 

[TOP  | Previous section ]

 

3.8.        Why are some application correctness requirements specified informally?

Application correctness requirements are generally applicable to a range of applications (general-applicability), and independent of the techniques to support them (technique-independency). Some application correctness requirements, such as intention-preservation (a do effect) and undo effect, have been specified informally and broadly because their precise specification would require reference to concrete applications and/or specific techniques, which would contradict the general-applicability and technique-independency. Informal descriptions are intuitive to users (so application users can roughly understand what correctness assurance the application provides), and allow broad interpretation in different applications and techniques (so application designers have the flexibility to specialize these general requirements in different applications and devising different techniques to support them).

 

Informal specifications are not intended for the purpose of rigorous verification of those application-correctness requirements. In case that theoretic verification is needed, those general correctness requirements should be specialized into precise/formal ones for the specific technique (e.g. OT) and the target application (e.g. a group text editor with two primitive insert and delete operations).  The reader can find precise intention-preservation verification criteria for character-wise insertion and deletion transformations in Q&A 2.15 and for string-wise insertion and deletion transformations in Specification 3 (Verification Criteria) of [43].  

 

[TOP | Previous section ]

3.9.        What are the multi-level specifications of  intention-preservation?

The notion of Intention-Preservation was proposed in [38, 43] as an application correctness requirement for collaborative editors, and has been described at three different levels:

(1)      The 1st-level description is at the consistency model level as one of three general consistency requirements for collaborative editing systems. This description is independent of applications and techniques, thus being OT-independent.

(2)      The 2nd-level description is a specialization for the OT technique (see [38, 43] for key points of this specialization). This description specifies context-based conditions for achieving intention preservation in OT-supported collaborative editing applications, but this description is independent of operation and data models.

(3)      The 3rd-level description is a specialization for an OT system supporting a pair of string-wise insert and delete operations in a single linear address space (a plain text document). This description provides detailed criteria for verifying whether an OT transformed operation preserves the original effect under specific operation and data models.  This specialization is not the only possibility; and alternative specializations are also possible as long as they meet the needs of the target application.

 

An alternative specialization of intention preservation for collaborative object-based graphics editing systems and a non-OT supporting technique (i.e. multi-versioning) can be found in [47].

[TOP  | Previous section ]

 

3.10.    What are the context-based conditions for achieving intention preservation?

To achieve intention preservation in OT-supported collaborative editing systems, the following context-based conditions are required:   

(1)      Intention-preserving execution: The execution of operation O on document state S preserves the intention of O if the definition context of O (i.e. the document state on which O is defined), denoted as DC(O), is equivalent to its execution context (i.e. the document state S on which O is executed), denoted as EC(O); i.e. DC(O) = EC(O) (see CC3 in 2.10). 

(2)      Intention-preserving transformation: A transformed operation O preserves the intention of the original operation O if the effect of O in the new context C(O) is equivalent to the effect of O in the original context C(O) (see Post-IT and Post-ET in 2.17).  

 

[TOP  | Previous section ]

3.11.    What are the criteria for verifying intention-preservation for character-wise operations?

For a pair of character-wise insert and delete operations based on a single linear address model, the following criteria can be used to verify intention-preserving transformation:

(1)      A transformed delete operation preserves the intention of the original delete operation if it deletes and only deletes the character deleted by the original operation.

(2)      A transformed insert operation preserves the intention of the original insert operation if: (a) the transformed insert operation inserts and only inserts the character inserted by the original operation; and (b) the insert position relative to other existing characters in the document is preserved. To elaborate point (b), let the original operation O = insert(c, p), and the transformed operation O = insert(c, p). For any character “x” existing in both document states determined by C(O) and C(O), if “x” is at the left/right of p in C(O), then it must also be at the left/right of p in C(O).

The above simple and precise criteria can be used for guiding the design of new transformation functions or for verifying correctness (with respect to intention-preservation) of existing transformation functions. For example, it can be used to verify  that the transformation functions in Q&A 2.15 are capable of preserving operation intention.   For criteria of verifying intention-preservation of string-wise transformations, the reader is referred to Specification 3 (Verification Criteria) of [43].

 

[TOP  | Previous section ]

 

3.12.    What is the relationship between convergence and intention preservation?

First, the intention preservation requirement does not capture the convergence requirement, i.e. the intention preservation verification criteria may not enforce a unique (or convergent) result [42, 43]. For example, two concurrent operations inserting at the same position with characters “a” and “b”, respectively, may result in a state of either “ab” or “ba”, both of which meet the general intention preservation requirement as well as the concrete verification criteria for character-wise transformation functions, but they are divergent. For another example, two concurrent operations inserting at the same position with two strings: “a” and “ab”, respectively, may result in a state of “ab” (merged effect),  or  “aab” or "aba" (two possible non-merged effects) –  the merged and non-merged effects all meet the intention preservation requirement and verification criteria, but they are all different (to the best of this author's knowledge,  all existing transformation functions choose the non-merged effect). 


Second, a convergent result may violate the operation intention. For example, given a shared document state “abc”, and two concurrent operations O1 = Insert[1, “X”] (to insert character “X” at position 1), and O2 = Insert[2, “Y”] (to insert character “Y” at position 2). After executing the two operations, the final document state may converge to “aXYbc”, which could be achieved by enforcing a totally ordered execution: O1 followed by O2. However, this convergent result violates the intention of O2, and the correct intention-preserved effect should be a document state “aXbYc”. 

 

The essential difference between convergence and intention preservation is that the former can always be achieved by a serialization technique, which enforces a totally ordered execution effect, but the latter may not be achievable by serialization if operations were always executed in their original forms [42, 43].

 

[TOP  | Previous section]

 

3.13.    What is the relationship between the intention of an operation and the intention of the user?

The intention of an operation O is the execution effect that can be achieved by applying O on the document state from which O was generated. The intention of an operation is related to but different from the intention of the user who issues the operation. The intention of the user may or may not be captured by the issued operation [50].

·     For example, if the intention of a user is simply to insert a character “x” at the beginning of a document, then the operation O = Insert[0, x] will fully capture this user’s intention. However, if the user mistakenly hits the wrong key for character “z,” then the generated operation O = Insert[0, z] does not capture the user’s intention at all.

·     For another example, consider a document with the English word: “researcher.” If the intention of a user is to change this singular word into a plural one by issuing an operation O = Insert[10, “s”], then O captures only the syntactic part (i.e., to insert a plain character “s” at position 10) but not the semantic part (i.e., to change the English word “researcher” into “researchers”) of the user’s intention.

 

If an operation fully captures the intention of the user and there is no concurrency in the system, or concurrent operations do not change the document in any semantically conflicting way, then preserving the operation’s intention may also preserve the user’s intention. Otherwise, the user’s intention may still be violated even if the operation’s intention has been preserved. How to capture and preserve the user’s intention in collaborative environments is an open issue, but not covered by the notion of intention preservation as defined in existing OT literature.

 

[TOP  | Previous section ]

 

3.14.    Under what conditions is an OT system application-correct?

An OT system is application-correct if it is able to meet the correctness requirements of the target application. Different applications may use OT for different purposes, thus imposing different application correctness requirements on the used OT system. Some OT systems are designed only for supporting consistency maintenance, some only for group undo, some for both consistency maintenance and group undo, and some for operation compression. Consequently, these OT systems are application-correct/-incorrect if they match/mismatch the requirements of the target application. 

 

For example, the REDUCE OT system (consisting of the GOT/GOTO control algorithm and a set of IT/ET functions [43]) is application-correct to the REDUCE group text editor since the OT system provides the intention-preservation capability required by the target application (note: an undo-redo-based optimistic serialization technique was used to achieve convergence); the COT system (consisting of the COT control algorithm [53, 54] and a set of (unpublished) IT functions) is application-correct to CodoxWord/CoPPT/CoMaya since the COT system is able to achieve  convergence and intention-preservation (for consistency maintenance), and undo effect and property (for group undo) as required by the target applications.

 

In evaluating and selecting OT systems for specific applications, one needs to first understand the needs/requirements of the target application, and then select the suitable OT system that meets those application needs.    

 

[TOP | Previous section ]

 

3.15.    What are the OT algorithm correctness requirements?

A large number of algorithm correctness requirements have been identified in the form of transformation conditions and properties, as shown in Table 4. Transformation conditions/properties are named differently in different OT systems and the name correspondence is given in Table 4 as well.  Which OT components are responsible for achieving which algorithm correctness requirements can be found in Q&A 3.16.

 

Table 4  OT algorithm correctness requirements

Names used in OTFAQ

Names used in various OT systems

Reference Articles

CC1

Context-based Condition 1

(Context-ordered transformation)

Sun and Sun [53, 54]

CC2

Context-based Condition 2

(Context-independent reference operations)

Sun and Sun [53, 54]

Concurrent reference operations

Ellis and Gibbs [6]

Sun et al. [43]

CC3

Context-based Condition 3

(Context-equivalent execution)

Sun and Sun [53, 54]

Intention-preserved execution

Sun and Ellis [42]

CC4

Context-based Condition 4

(Context-ordered transformation)

Sun and Sun [53, 54]

CC5

Context-based Condition 5

(Context-independent reference operations)

Sun and Sun [53, 54]

Concurrent reference operations

Sun  et al. [43]

CC6

Context-based Condition 6 

(Context-equivalent transformation)

Sun and Sun [53, 54]

Pre-condition for IT

Sun  et al. [43]

Pre-IT

Pre-condition for IT

Sun  et al. [43]

Post-IT

Post-condition for IT

Sun  et al. [43]

Pre-ET

Pre-condition for ET

Sun  et al. [43]

Post-ET

Post-condition for ET

Sun  et al. [43]

RP

Reversibility Property

Sun et al. [43], Sun [50]

Transpose Property 3

Prakash and Knister [28]

CP1

 

Convergence Property 1

Sun [50]

Transformation Property

Ellis and Gibbs [6]

Transformation Property 1

Prakash and Knister [28]

Ressel et al. [30]

CP2

Convergence Property 2

Sun [50]

Transpose Property 5

Prakash and Knister [28]

Transformation Property 2

Ressel et al. [