Operational Transformation Frequently
Asked Questions and Answers
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
Table
of Contents
1.2...... What
collaboration capabilities can OT support?
1.3...... What
collaborative applications can OT support?
1.4...... What
is the basic idea of OT for consistency maintenance?
1.5...... What
is the basic idea of OT for undo?
1.6...... What
is the basic idea of OT for operation compression?
1.7...... What
is a basic OT system?
1.8...... What
is the operation model of an OT system?
1.9...... What
is the data model of an OT system?
1.10.... Can
OT support documents other than plain texts?
1.11.... Can
OT support operations other than Insert and Delete?
1.12.... Can
OT support complex data objects without linear relationships?
1.13.... Can
OT support complex application operations?
1.14.... Can
OT preserve the user intention?
1.15.... Can
OT solve semantic consistency problems?
2.1...... What
is the structure of an OT system?
2.2...... What
is the role of transformation control algorithms in an OT system?
2.3...... What
is the role of transformation functions in an OT system?
2.4...... What
is the role of transformation conditions and properties in an OT system?
2.5...... What
is the benefit of separating control algorithms from transformation functions?
2.6...... What
is the concept of operation context in OT design?
2.7...... How
to represent operation context in OT design?
2.8...... What is the context-equivalent relationship
between operations?
2.9...... What is the context-preceding relationship between
operations?
2.10.... What
are the context-based conditions governing
OT control algorithm design?
2.11.... How
to design context-based OT control algorithms?
2.12.... How
to classify OT control algorithms by their capabilities?
2.13.... What
kinds of transformation function exist?
2.14.... What
are the basic ideas in designing transformation functions?
2.15.... How
to design character-wise transformation functions?
2.16.... Why
are string-wise transformation functions challenging to design?
2.17.... What
are the pre-/post-conditions for transformation functions?
2.18.... Which
OT components are responsible for ensuring transformation pre-/post-conditions?
2.19.... What are the OT transformation properties
and their pre-conditions ?
2.20.... Which
OT components are responsible for achieving transformation properties?
2.21.... How
to break pre-conditions for both CP1 and CP2?
2.22.... How
to break the precondition of CP2 ?
2.23.... How
to deal with the complexity in OT system design?
2.24.... What
issues to consider in evaluating OT system time efficiency?
2.25.... What
are the space efficiency issues of an OT system?
2.26.... What
attributes can be used to differentiate OT systems?
2.27.... What
is the role of OT in the Generic Collaboration Engine (GCE) technology?
2.28.... What
is the role of OT in the Transparent Adaptation (TA) technology?
2.29.... What
is the role of the OTXplorer in OT research and design?
3.1...... What
are the multi-facets of OT
correctness?
3.2...... What
are the consistency-related application correctness requirements?
3.3...... What are the undo-related application
correctness requirements?
3.4...... What are the compression-related application
correctness requirements?
3.5...... What are the OT-related application
correctness requirements?
3.6...... Does an OT system must meet all application
correctness requirements?
3.7...... Does a collaborative editor must meet all
consistency correctness requirements?
3.8...... Why are some application correctness
requirements specified informally?
3.9...... What are the multi-level specifications
of intention-preservation?
3.10.... What are the context-based conditions for
achieving intention preservation?
3.11.... What are the criteria for verifying
intention-preservation for character-wise operations?
3.12.... What is the relationship between convergence
and intention preservation?
3.14.... Under what conditions is an OT system
application-correct?
3.15.... What are the OT algorithm correctness
requirements?
3.16.... Which OT components are responsible for
meeting what algorithm correctness requirements?
3.17.... Does an OT system must meet all algorithm
correctness requirements?
3.18.... Under what conditions is an OT system
algorithm-correct?
3.20.... What is the relationship between algorithm
and application correctness?
3.21.... What is the relationship between OT puzzles and algorithm correctness?
3.22.... What is the dOPT puzzle?
3.24.... What is the False-Tie (FT) puzzle?
3.25.... Under what circumstances is an FT-solution
needed or not needed?
3.26.... How to achieve consistency without solving
the FT puzzle?
3.27.... What are the main differences between the FT
puzzle and other OT puzzles?
3.28.... What role does the
puzzle-detection-resolution approach play in OT research ?
3.29.... What role does theoretic verification play
in OT algorithm correctness study?
3.30.... What role do real-world applications play in
OT research?
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 [1–64]. 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.
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.
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 S0 ≠ S4, 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(
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) 
{
[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(
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
(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
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) |
|
IT and ET |
||
|
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
(1) compare the parameters of Oa and
(2)
assume
(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],
if p1 <= p2 return Ins[p1,
c1]; //e.g. Tid(Ins[3, “a”],
else return Ins[p1-1, c1]; } // Tid(Ins[3, “a”], Del[1] ) = Ins[2, “a”]
Tdi(
if p1 < p2 return
else return
Tdd(
if
p1 < p2 return
else if p1 > p2 return
else return
I; } //
breaking delete-tie using I (identity
op) Tdd(
[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
·
Pre-Condition for IT (Pre-IT): C(Oa) =
C(Ob)
which means that Oa and
·
Post-Condition for IT (Post-IT): C(Oa') = C(Oa) {
(2)
Let Oa' = ET(Oa, Ob), where Oa
is the transformation target and
·
Pre-Condition for ET (Pre-ET): C(Oa)
= C(Ob) {Ob}, which means that Oa
and Ob can be
ET-transformed only if
·
Post-Condition for ET (Post-ET): C(Oa') = C(
[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),
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(
S 
Oa Ob' = SOb Oa'
which means that sequence Oa Ob' is equivalent to sequence 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(
IT(IT(O, Oa),
Ob') = IT(IT(O,
which means that the
outcome of transforming O against Oa and Ob′ in sequence equals the outcome of transforming O against
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.
(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.
(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
[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:
- O1, O2, O3
- O1, O3, O2
- O2, O1, O3
- O2, O3, O1
- O3, O1, O2
- 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:
- O1, O2, O3
- O2, O1, O3
- 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 O1→O3 (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 Oa→Ob, then O is transformed against Oa before Ob. For
an operation Ox in CD, O can be transformed against Ox even if Ox→O (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:
- O1 (no
transformation); O2' =
T(O2,O1); O3' = T(T(O3,O1),
T(O2,O1))
- O2 (no
transformation); O1' =
T(O1,O2); O3' = T(T(O3,O1),
T(O2,O1))
- 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:
- 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.
- In the execution order "O2, O1, O3," O1 is allowed to
be transformed against O2 even though O1→O2;
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 O1→O2. 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.
- In the execution order "O3, O1, O2," O1 is allowed to
be transformed against O3 even though O1→O3;
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 O1→O3. 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 Ox→Oy, 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 E.g. under the total ordering O1→O2→O3, and in the permissible
execution order O3,O1,O2, O2
must be transformed against O1 before O3 because O1→O3 (as shown in T(T(O2,O1), T(O3, O1))). |
|
O1→
O2→O3 |
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)) |
|
|
O1→O3→O2 |
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)) |
|
|
O2→O1→O3 |
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)) |
|
|
O2→O3→O1 |
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)) |
|
|
O3→O1→O2 |
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)) |
|
|
O3→O2→O1 |
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:
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 |
|
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] |
|
|
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. |
||
|
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. |
||
|
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] |
|
|
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 |
|
Context-based Condition 1 (Context-ordered transformation) |
||
|
Context-based Condition 2 (Context-independent reference operations) |
||
|
Concurrent reference operations |
Ellis and Gibbs [6] Sun et al. [43] |
|
|
Context-based Condition 3 (Context-equivalent execution) |
||
|
Intention-preserved execution |
Sun and Ellis [42] |
|
|
Context-based Condition 4 (Context-ordered transformation) |
||
|
Context-based Condition 5 (Context-independent reference operations) |
||
|
Concurrent reference operations |
Sun et al. [43] |
|
|
Context-based
Condition 6 (Context-equivalent
transformation) |
||
|
Pre-condition
for IT |
Sun et al. [43] |
|
|
Pre-condition
for IT |
Sun et al. [43] |
|
|
Post-condition
for IT |
Sun et al. [43] |
|
|
Pre-condition
for ET |
Sun et al. [43] |
|
|
Post-condition
for ET |
Sun et al. [43] |
|
|
Reversibility
Property |
||
|
Transpose
Property 3 |
Prakash and
Knister [28] |
|
|
|
Convergence Property 1 |
Sun [50] |
|
Transformation Property |
Ellis and Gibbs [6] |
|
|
Transformation Property 1 |
Prakash and
Knister [28] Ressel et al. [30] |
|
|
Convergence Property 2 |
Sun [50] |
|