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 – 2015 by Chengzheng
Sun. All rights reserved.
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
- 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
COT-UNDO (Undo(O), DS)
1. I(O) := makeInvese(O); C(I(O) := C(O) U {O}; // I(O) is the
inverse of O
- 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.
IP1 Pre-condition
(IP1-PC): transformation functions are
required to preserve IP1 only if the OT system uses inverse operations to
achieve the undo effect. Note: IP1 is used to govern the creation of inverse
operations, but it is unrelated to the definition of transformation functions.
(5) Inverse Property 2 (IP2): Given any operation O
and a pair of
operations 
and 
, where O and Ox are context-equivalent, it
must be that
which means that the outcome of transforming O
against and in sequence must be equal to O. In other words, the sequence of and is equivalent to
a single identity operation I with
respect to the effect in transformation.
IP2 Pre-condition (IP2-PC):
transformation functions are required to preserve IP2 only if the OT system
allows an operation to be transformed against and one by one.
(6) Inverse Property (IP3): Given two context-equivalent operations 
and 
, if 
, 
and
, then
or
which means that 
, the outcome of IT-transforming the inverse operation 
against , must be equal to 
,
the inverse of IT-transforming against .
IP3 Pre-Condition
(IP3-PC): transformation functions are
required to preserve IP3 only if the OT system allows an inverse operation to be transformed against an operation 
and is defined on the
same context as, where .
It is worth mentioning that
·
convergence properties, CP1 and CP2, are
required for achieving convergence;
·
inverse properties, IP1, IP2 and IP3, are
required to support group undo
[50, 54].
[TOP | Previous section | Next section]
2.20. Which OT components are
responsible for achieving transformation properties?
Transformation
properties can be achieved by:
(1) designing transformation functions that can preserve
those properties, or
(2) designing control algorithms that can break the
pre-conditions of those properties.
Past
research has shown that it is relatively easy to design transformation
functions capable of preserving CP1 (e.g. the simple character-wise transformation functions able to
preserve CP1),
but non-trivial to design and verify transformation functions capable of
preserving CP2, IP2 and IP3.
It has also been known that ensuring RP by transformation
functions is difficult due to lossy
transformations [43, 50]. Therefore, it is advisable to solve RP, CP2, IP2 and
IP3 at the control algorithm level, which has the benefits of simplifying the
design of transformation functions and improving system efficiency [54]. A combined use of both
control algorithms and transformation functions for achieving transformation
properties is common in real OT systems.
[TOP | Previous section | Next section ]
2.21. How to break pre-conditions for both
CP1 and CP2?
One
basic idea of breaking preconditions of both CP1 and CP2 is to ensure all
concurrent operations are transformed in the same total order at all sites,
i.e. if Oa and Ob are concurrent and Oa is totally ordered before Ob, then Ob can be transformed against Oa (T(Ob, Oa)), but not the other way around (T(Oa, Ob)). This idea has been used in the GOT system
[43], which uses a undo-redo scheme to achieve totally
ordered transformation and execution effect at all sites. Since the GOT system
never transforms a pair of operations in different orders, the
precondition for CP1 is thus broken.
Breaking the precondition of CP1 also implies breaking the
precondition of CP2, i.e. the GOT system never transforms a pair of operations
in different contexts as well. Otherwise, suppose, under the control of the GOT
algorithm, Oa and
[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.23. 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.24. 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.25. 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.26. 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.
(2) 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.
(3) 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].
(4) 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.
(5) 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.
(6) 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.
(7) 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.27. 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.28.
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.29. 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.
(2)
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).
(3)
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] |
|
|
Transpose
Property 5 |
Prakash and Knister [28] |
|
|
Transformation
Property 2 |
Ressel et al. [30] |
|
|
Inverse
Property 1 |
Prakash and Knister [28] Sun [50] |
|
|
Inverse
Property 2 |
Prakash and Knister [28] Sun [50] |
|
|
Part of Undo
Property |
Ressel et al. [30] |
|
|
Inverse
Property 3 |
Sun [50] |
|
|
Part of Undo
Property |
Ressel et al. [30] |
[TOP | Previous
section ]
3.16. Which
OT components are responsible for meeting what algorithm correctness
requirements?
Context-based
transformation conditions (CC1 - CC6) must be met by (so compulsory to) OT
control algorithms to:
·
ensure correct ordering
of operation execution and transformation (CC1 and CC4),
·
determine correct
transformation reference operations (CC2 and CC5), and
·
ensure correct operation
execution and transformation (CC3 and CC6).
Transformation post-conditions Post-IT and Post-ET (if ET is
used in the OT system) must be met by (so compulsory to) transformation
functions to achieve correct
intention-preserving transformation effects [43].
Transformation properties RP,
CP1, CP2, IP2, IP3 may be met by either transformation functions or control
algorithms (by breaking their pre-conditions) [54]. (Note: IP1 is
unrelated to transformation functions or control algorithms, and should be met
by inverse operation definition).
These properties are optional to individual components (control algorithms
and transformation functions), but compulsory to the OT system as a while.
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 are able to preserve CP1), but non-trivial to
design and verify transformation functions capable of preserving CP2, IP2 and
IP3. Therefore, it is advisable to solve CP2, IP2 and IP3 at the control
algorithm level.
[TOP | Previous
section ]
3.17. Does
an OT system must meet all algorithm correctness requirements?
No. Whether an OT system needs to meet certain algorithm
correctness requirements depends on the capability and the design of the OT
system. Different OT systems may have different capabilities
(e.g. consistency maintenance, group undo, etc.) and/or different designs (e.g.
different control algorithms and transformation functions), and hence
require different transformation
conditions/properties to ensure algorithm correctness. For example, an OT
system for supporting only consistency maintenance may be required to ensure CP1 and CP2 (for achieving convergence), but
would not be required to ensure IP1, IP2,
and IP3, which are required only if the OT system supports group undo (for achieving undo effect and undo property). For another example, if both IT and ET functions are used in an OT system
(e.g. GOTO [42]), RP
must be met; otherwise, RP is not required for OT systems that use IT functions
only (e.g. COT [53, 54]). If the OT control algorithm (e.g. COT)
is able to break preconditions of certain transformation properties (e.g. CP2, IP2, IP3), then
transformation functions need not to ensure those properties.
[TOP | Previous section ]
3.18. Under
what conditions is an OT system algorithm-correct?
An OT system is algorithm-correct
if its components meet respective compulsory transformation conditions, and
match each other with respect to optional transformation properties. Specifically,
·
Control algorithms meet compulsory context-based transformation
conditions (e.g. CC1 - CC6);
·
Transformation functions meet compulsory transformation post-conditions (e.g. Post-IT and Post-ET if ET is
used);
·
Either transformation functions or control algorithms preserve
transformation properties (e.g. RP, CP1, CP2, IP2, and IP3).
For example, an OT system designed for consistency maintenance is algorithm correct
if its control algorithms (e.g. GOT[43], adOPTed [30], GOTO [42]) meet context-based
conditions, and its transformation functions are capable of preserving required
transformation post-conditions and other matching transformation properties (e.g. RP
if GOT or GOTO is the control
algorithm; CP1 and CP2 if adOPTed or GOTO
is the control algorithm). An OT system designed for both consistency maintenance and
group undo is algorithm correct if its control algorithms (e.g. COT [54]), in addition to meeting
context-based conditions, are capable of breaking preconditions for RP, CP2,
IP2 and IP3, and its transformation functions are able to preserve CP1, Post-IT
but without the capability of preserving RP, CP2, IP2 and IP3.
[TOP | Previous
section ]
A correct OT system can be made by combining existing control
algorithms (capable of preserving compulsory context-based conditions) with
suitably matching transformation functions (capable of preserving compulsory
transformation-post conditions). Given an OT control algorithm and its
supported correctness properties, it can be derived what correctness properties
transformation functions must support to make an algorithm-correct OT system.
In Table 5, some existing OT control algorithms, their
capabilities (consistency maintenance, undo, and/or operation compression),
supported optional correctness properties (compulsory context-based conditions
are omitted for conciseness), and required correctness properties for
transformation functions are listed. Some OT systems that do not fit well with
the taxonomy and characterization in Table
5 can be found in [7, 18, 22, 31].
Table 5. OT systems and their ways
of achieving algorithm correctness
(note: CM stands for
Consistency Maintenance, OC for Operation Compression)
|
Selected OT Control Algorithms
|
CE
Systems Using the OT Control Algorithms |
Supported Collaboration
Capabilities (CM/Undo/OC) |
Required
Transf. Function Types |
Supported
Correctness Properties by Control Algorithms |
Required
Correctness Properties for Transformation Functions |
|
dOPT [6] |
GROVE |
CM |
T (IT) |
Unable to meet Pre-IT, |
|
|
Selective-undo [28] |
DistEdit |
Selective Undo |
Transpose (IT and ET) |
|
|
|
adOPTed [30] |
JOINT EMACS |
Chronological- Undo, CM |
LTransform (IT) |
||
|
Jupiter OT [25] |
Jupiter |
CM |
xform (IT) |
||
|
Google Wave OT [59] |
Wave |
CM, OC, |
Transform (IT) |
||
|
GOT [43] |
REDUCE |
CM |
IT and ET |
||
|
GOTO [42] |
REDUCE, CodoxWord, |
CM |
IT and ET |
|
|
|
AnyUndo [50] |
REDUCE, CodoxWord, |
AnyUndo |
IT and ET |
|
|
|
SCOP [33] |
NICE |
CM, OC, |
IT |
||
|
CM, AnyUndo, |
IT |
||||
|
TIBOT [21] |
|
CM |
IT |
||
|
SDT[20] |
|
CM |
IT |
|
CP1, CP2, Post-IT |
|
SOCT4 [58] |
|
CM |
Forward T (IT) |
||
|
SOCT2 [37] |
|
CM |
Forward T (IT) Backward T (ET) |
|
[TOP | Previous
section ]
3.20. What
is the relationship between algorithm and application correctness?
OT algorithm correctness requirements are constraints imposed by
OT algorithm components to each other, whereas OT application correctness
requirements are imposed by target applications. The two facets of OT
correctness are related to but different from each other.
·
Some algorithm correctness requirements are related to achieving
certain application correctness requirements, e.g. convergence properties (CP1 and CP2) are related to ensuring convergence; context-based post-conditions for IT/ET are related to achieving intention preservation; inverse properties (IP1, IP2 and IP3) are related to supporting
group undo.
·
Some algorithm correctness requirements (e.g. context-based pre-conditions for transformation functions, the reversibility
property between IT and ET, and
other context-based conditions for OT control algorithms [53, 54]) are unrelated to specific
application correctness requirements, but are algorithmic constraints for
correct functioning of an OT system as a whole.
·
OT systems with different application correctness requirements may
have different algorithm correctness requirements. For example, an OT system
designed for supporting consistency maintenance (with convergence and intention
preservation as its application correctness requirements) must satisfy CP1, CP2
and context-based pre-/post conditions for transformation functions, but may
not necessarily satisfy IP1–3, which are required only if the OT system is
designed for supporting group undo (with undo effect and property as its application
correctness requirements) as well.
·
OT systems with the same application correctness requirements may
still have different algorithm correctness requirements. This is because
different OT system designs may result in different algorithm components, which
may require different algorithmic correctness constraints among them. For
example, some OT systems (e.g. GOT [43]], GOTO [42]) use both IT and ET
functions, so they must meet the reversibility property; but some OT systems
(e.g. COT [53, 54], adOPTed [30], Google Wave OT [59]) use IT functions only
and hence need not to meet the reversibility property requirement.
[TOP | Previous section ]
3.21. What
is the relationship between OT
puzzles and algorithm correctness?
OT puzzles are subtle and
characteristic scenarios in which certain OT algorithm constraints (e.g.
transformation properties and conditions) may be violated and the OT system may
produce incorrect results. Trying to detect and resolve various puzzles has
been a major stimulus in establishing OT algorithm correctness requirements and
advancing OT technology.
OT puzzles are closely
related to OT algorithm correctness requirements. OT algorithm correctness
requires the satisfaction of certain constraints (e.g. transformation conditions and
properties) by OT components. Violation of any of those constraints may
result in incorrect transformation results, which may lead to inconsistent
document states and then manifest
themselves as OT puzzles. For example, violation of Pre-IT
results in the dOPT puzzle [42]; violation of IP2/IP3 results in undo-related OT puzzles [50].
OT puzzles can be
classified according to the algorithm correctness requirements to which they
are related, such as Pre-IT puzzles (e.g. the dOPT puzzle), IP2 puzzles (e.g. coupled
and uncoupled do-undo-pair traps [50]), IP3 puzzles (e.g. insert-insert-tie dilemma and overlapping deletes [50]), etc. Classified OT
puzzles can be used as benchmarks for testing the algorithm correctness of an
OT system. If an OT system fails to solve certain class of OT puzzles, then the
OT system is incorrect with respect to the corresponding algorithm correctness
requirement. The ability to solve all known OT puzzles is a necessary condition
and an important indicator of algorithm correctness of an OT system, though it
does not provide a full proof of the algorithm correctness.
Accurate attribution of the
root of an OT puzzle to a specific algorithm correctness requirement is crucial
in resolving the puzzle. All OT puzzles could result in inconsistent document
states, which might be regarded as CP1/CP2-violation
in one way or another (because CP1 and CP2 are about convergence).
However, it is incorrect to attribute the root of all divergence-related OT
puzzles to CP1/CP2-violation. This is because divergence is only the symptom of the problem and could be
caused by violation of a variety of correctness requirements. For example, the root of the dOPT puzzle
is Pre-IT-violation, not CP1/CP2-violation; and hence the solution to the dOPT
puzzle is to design Pre-IT preserving control algorithms, rather than
CP1/CP2-preserving transformation functions (though such functions are useful
for different purposes). In fact,
CP1/CP2 cannot be guaranteed by IT functions if the Pre-IT condition is not met
by control algorithms. For another example, the FT puzzle
may cause CP2-violation, which results in divergent states, but a CP2-solution
may not solve the FT puzzle because the FT and CP2-violation are two different
problems (see Q&A 3.25 for when and how to resolve the FT puzzle).
The OTXplorer system can be used to help detect and
resolve OT puzzles and evaluate existing/new OT algorithms by scenario-based
benchmarks.
[TOP | Previous
section ]
3.22. What
is the dOPT
puzzle?
The dOPT puzzle is the well-known flaw in the first OT
control algorithm dOPT [6], which failed to produce
correct results when transforming concurrent but context-different operations.
The dOPT puzzle can be illustrated with a minimum two sites and 3 operations O1, O2, and O3,
as shown in Figure 13 (note: suitable
operation parameters are needed (see [42]) to produce inconsistent
document states under this dOPT puzzle scenario).
Figure 13. A simple scenario for illustrating the dOPT puzzle
In this scenario, O1
and O2 are concurrent and context-equivalent,
so there is no problem for direct IT-transformation between O1 and O2. However, O1
and O3 are concurrent but
context-different (O3 is
defined on the document state after O2
has been executed), so they cannot be directly used for IT-transformation
according to Pre-IT (or CC6). Pre-IT-violation,
i.e. failure to ensure the two IT-transformed operations be context-equivalent,
is the root of the dOPT puzzle.
The dOPT puzzle has been solved
in various ways [42], but the essential
property preserved by all dOPT-puzzle solutions is the Pre-IT,
rather than other transformation properties (e.g. CP2) [42].
[TOP | Previous section ]
No. It was shown that,
under the control of the adOPTed algorithm [30], CP1 and CP2 (named TP1
and TP2 in [30]) are necessary and
sufficient conditions for IT functions (named LTransformation functions in [30]) in order to achieve convergence [23, 30].
This is a useful OT correctness result.
However, CP1 and CP2 should not be interpreted as necessary
and sufficient conditions required for correctness of transformation functions.
CP1 and CP2 are unnecessary for transformation functions because
they can be met by the OT control algorithm
(by breaking preconditions CP1-PC and/or CP2-PC).
For example, neither CP1 nor CP2 is required for IT functions
under the control of the GOT algorithm [43], which never transforms a
pair of operations in different orders (CP1-PC) or in different contexts
(CP2-PC); CP2 is not required for IT functions under the control of the COT
algorithm [53,
54], which never transforms a
pair of operations in different contexts (CP2-PC).
CP1 and CP2 are insufficient for transformation functions since
there are other essential algorithm correctness conditions. If the OT
system is to support group undo, transformation functions are required to meet IP2 and IP3, in addition to CP1 and CP2. If
the OT system uses both IT and ET functions, then RP must be met. Even if the OT system is to support consistency
maintenance only, CP1 and CP2 are inadequate to ensure IT functions be
meaningful, let alone be correct. In fact, without satisfying the
post-condition of transformation functions (Post-IT),
CP1 and CP2 can be trivially achieved. For example, a trivial IT function can
be defined as follows: trivial-IT(O, Ox)
= O', where O′ is an operation that
always replaces the existing contents of
the document with a number X. It
can be shown that this trivial-IT
preserves CP1 and CP2. By assigning X
to an arbitrary number, one can get an infinite number of transformation
functions capable of preserving CP1 and CP2, but none of them is correct
(according to the Post-IT).
[TOP | Previous
section ]
3.24. What
is the False-Tie (FT) puzzle?
The FT puzzle is a scenario in which two (or more) concurrent insert operations with the same
inserting position (a tie) are
IT-transformed with each other, but their position tie is false in the sense that it was not original
but caused by previous transformations. The FT puzzle may cause abnormal object-ordering, which may
result in divergence or incorrect undo effect
under certain circumstances. A comprehensive set of FT benchmark scenarios
and solutions can be found in the OTXplorer
system.
The first FT scenario was reported in [40]
and later in [43]. A similar FT scenario is shown in a
Space-Time diagram in Figure 14.
Figure 14 A simple False-Tie scenario
This scenario involves
three collaborating sites with an initial document state “abc”, and three operations: two concurrent insert
operations O1 = Ins[1, “1”] and O3 = Ins[2, “2”], plus one concurrent delete operation O2 =
(1)
O2 is executed as-is, and
document becomes “ac”.
(2)
O1 arrives and is transformed
against O2 but no change
is made to its position; after executing O1
as-is, the document becomes “a1c”.
(3)
O3 arrives and is first
transformed against O2 to
become O3′ = T(O3, O2) = Ins [1, “2”], and then transformed against O1′ (=O1), i.e. T(O3′, O1) = T(Ins[1, “2”], Ins[1, “1”]), where the position
parameters of the two input operations are tied (both are 1). However, this insert-tie
is a false-tie because it was not
original but created by transformation. If a normal tie-breaking scheme (e.g.
based on user identifiers) is used to break this false-tie, then a possible
transformation result would be O3′′ = O3′ = Ins(1, “2”), i.e. no
change is made to O3′. After executing O3′′, the document would become “a21c”, in which the ordering
between characters “2” and “1” is abnormal
in the sense that this ordering is inconsistent with the ordering determined by
the original O1 and O3 in the presence of
character "b".
The
above abnormal object ordering problem may manifest itself (i.e. become
known to users) in the forms of document divergence or incorrect undo effect
under the following circumstances:
(1)
Document divergence. As concurrent operations
may be transformed and executed in different orders at different sites, the FT
problem may occur at one site but not at other sites, which could result in
divergent document states. As shown in Figure 14, the FT problem occurs only at site 2 but
not at sites 1 and 3; and the final document states at sites 1 and 3 are “a12c”, which is different from
“a21c” at site 2.
However, divergence can be
resolved without resolving the FT problem, e.g. by enforcing (one way or
another) all sites to have the same state “a21c” (or “a12c”). In other words, FT-caused divergence can be resolved without
resolving FT itself if the OT system is used for consistency maintenance
only.
(2)
Incorrect undo effect. When the FT problem has
resulted in abnormal object ordering, undoing the delete operation may result
in incorrect undo effect. For the scenario Figure 14,
if the delete operation O2
is undone later, then the document state should become “a1b2c”, which is the
state if O2 was never
performed but O1 and O3 were performed, according
to the undo effect requirement. However, if all sites
converged on the state “a21c” with abnormal object ordering, then undoing O2 may result in a state
“a2b1c”, which does not meet the undo effect requirement.
Therefore, a solution to
the FT problem is needed when the OT system is to support group undo, even if
consistency can be achieved without solving the FT problem.
[TOP | Previous section ]
3.25. Under
what circumstances is an FT-solution needed or not needed?
The FT needs a solution if it causes application
correctness problems (e.g. divergence or incorrect undo effect) in an OT target
application, but needs no solution if no such problem occurs or these problems
can be solved by other means in the target application.
(1)
When OT is used for consistency
maintenance but not for group undo (e.g. some
real-time group text editors [25, 42]), an FT solution is
optional (not necessary) if convergence can be achieved in some ways (see “How to achieve consistency without solving the FT
puzzle”). Whether the system converges on a normal or abnormal ordering
state does not cause any problem to the user or the system.
(2)
If OT is used for both consistency maintenance and group undo
(e.g. some real-time group text editors [50] and word processors [52, 60]), an FT solution is
necessary because, after undoing
the delete operation involved in a
FT, the FT-caused abnormal-ordering may lead to incorrect undo effect, which
may be visible to the user (if data objects are displayed sequentially at the
UI). Solutions for FT benchmark
scenarios (involving both consistency maintenance and group undo) can be found
in the OTXplorer system (one example is shown in
Figure 7).
(3)
If an OT target application has no sequence objects visible at the
UI and convergence can be achieved in some way, an FT solution is not necessary
even if OT is used for both consistency maintenance and group undo. This is
because neither FT-caused abnormal-ordering nor FT-caused incorrect undo effect
is visible to the user or problematic to the system as long as convergence is
ensured. This case is subtle and relevant to applying OT to advanced 2D/3D
collaborative digital media design systems (e.g. CoMaya), in which OT referred
data objects are not displayed in sequence at the UI.
In summary, an FT solution
is needed if OT is used for supporting both consistency maintenance
(convergence and intention preservation) and group undo (with requirements of
undo effect and undo property) and the target application displays data objects
linearly at the UI. Otherwise, an FT solution is not needed.
When an FT solution is
needed, it is advisable to localize the solution mechanism within the OT
components to which the FT problem is related. This is because the FT problem
is specific to insert and delete operations, but irrelevant to
other operations (e.g. update [51], lock [44, 49], point [52, 61]) or other parts (e.g. control algorithms) of the OT system; an FT
solution that is localized within transformation functions involving both insert and delete but isolated from the rest of the OT system helps control the complexity of OT system design. Alternative ways of dealing with the FT
puzzle can be found in [10,
18,
26,
31].
[TOP | Previous
section ]
3.26. How
to achieve consistency without solving the FT puzzle?
An OT system can achieve consistency (convergence and intention-preservation)
without a solution for the FT puzzle provided the OT system is able to break
the precondition of CP2. There are multiple solutions for
breaking the precondition of CP2 [21,
25, 33,
43,
54,
58,
59]. To give a concrete example, we
apply the COT algorithm [53, 54] in combination of the character-wise IT functions defined in Q&A 2.15
to the classic FT scenario with an initial document state
“abc”, and three concurrent/context-independent operations: two insert
operations O1 = Ins[1, “1”] and O3 = Ins[2, “2”], plus one delete operation O2
= Del[1, 1], generated at sites 1, 3, and 2, respectively (see Figure 14).
For these three operations, there exist six possible
execution orders:
- 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 any of these possible
orders to occur in a session, then its IT functions must preserve both CP1 and
CP2 and solve the FT problem at the
function level in order to achieve convergence. Otherwise, divergence may occur
due to the FT problem as shown in Figure 14. Under the control of the COT
algorithm, however, only a well-defined
(see Definitions
8 and 9 in [54]) subset of these possible execution
orders, named as permissible-execution
orders, are allowed to occur in a
session. There exist six possible groups of permissible-execution orders for this
3-operation scenario, as shown in Table 2, but only one of them may
actually occur in a session. Suppose
the group of permissible-execution orders that actually occurred is the
following:
- O1, O2, O3
- O2, O1, O3
- O3, O1, O2
which is based on the permissible-ordering constraint: O1→O2→O3. Using the COT algorithm and IT functions defined in Q&A
2.15,
the transformation and execution results in every step for these three
permissible execution orders are shown in Figure
15.
Figure 15. Achieving consistent and normal ordering result
under an FT scenario.
Clearly, the final document state "a12c" is
consistent (convergent and intention-preserved by the verification
criteria for character-wise transformation functions) across all three sites
(representing the three permissible-execution-transformation
orders). It can be observed that no FT occurs in any of this group of
execution-transformation orders, i.e.
every execution-transformation order in this group is a non-FT order.
If, however, the group of permissible-execution orders is the
following:
- O1, O2, O3
- O2, O1, O3
- O3, O2, O1
which is based on the permissible-ordering constraint: O2→O1→O3, then the transformation and
execution results in every step at all sites are shown in Figure
16. Clearly, the final document state
"a21c" is also consistent across all three sites. It can be observed
that the FT occurs at all sites for
this group of execution-transformation orders, i.e. every order in this group
is an FT-order. Under this condition, the FT can be consistently resolved by
using a normal tie-breaking rule
based on site/user ids (e.g. the one used in IT functions in Q&A 2.15).
Figure 16. Achieving consistent and abnormal
ordering result under an FT
scenario
Following the same idea and illustration, the reader can use
the information in Table
2
to create similar scenarios like Figure
15
or Figure
16
and verify
that consistency can be achieved without requiring an FT solution under every
group of permissible execution/transformation orders.
In summary, by applying the COT algorithm and the IT
functions in Q&A 2.15
(which does not have an FT
solution) to the classic FT scenario, consistency (convergence and intention-preservation)
across all sites can be guaranteed under any well-defined group of permissible
execution orders. This is because
the COT algorithm is able to break the precondition of CP2 by enforcing well-defined
permissible execution and transformation orders, which eliminates the
possibility of mixing both FT and non-FT execution-transformation orders in the
same session/scenario (as shown in Figure 14).
By comparing the two different sessions shown in Figure
15
or Figure
16,
we can see the final states
"a12c" and "a21c" are different in their ordering of "1" and "2". However, such difference does not matter (to
either the user or the system) because no user has any idea/knowledge about the
relative ordering relationship between the two independently inserted
characters "1" and "2" in the absence of character "b", let alone care about their
ordering. We have seen no
compelling (practical or theoretic) reason for arguing "a12c" against "a21c" (or vice versa) for the
purpose of consistency maintenance (in fact, the same rationale has been used
to determine the relative ordering of characters inserted by concurrent
operations involved in true-ties as
well). It is fairly clear that an FT solution (i.e. to achieve the state “a12c” in the above example) is not
required for consistency maintenance. It is, however, ironic that nearly all OT articles about
solving the FT problem (or under the name of TP2/CP2-puzzle) were confined to
the scope of consistency maintenance (regardless whether or not those proposed
FT solutions were viable), but OT consistency maintenance solutions were
criticized for not solving/addressing the FT problem. The misconception that a correct OT solution must solve the FT problem
had led to the myth that many OT
solutions were incorrect because they did not solve or even address the FT
problem. In fact, many OT solutions are correct for their target
applications (“application-correctness”)
and algorithm constraints (“algorithm-correctness”)
when made from suitably matching OT algorithms
and/or functions.
We have also known that an FT solution may be required for
achieving correct undo effect [28, 29,
30,
46,
50,
54]. For example, after undoing O2 in the classic FT scenario, the
document state must be "a1b2c", rather than "a2b1c", because it is under this situation that the relative relationship
among "1" and "2" with respect to "b" manifests itself and become
known to users, and "a1b2c" is the only correct undo effect that transforms the document
into a state as if O2 was never executed but other operations were executed and
their effects retained. Therefore, it is the undo effect criteria that imposes a
necessary condition (or provides a justification) for requiring an FT solution
if an OT system is to support both consistency maintenance and group undo (see Q&A 3.25
Error! Reference source not found. for more detailed discussions
on when an FT solution is needed or not).
It should be noted that in Figure
15
or Figure
16,
the COT
algorithm has been used in combination with the character-wise IT functions in Q&A 2.15 to achieve consistent results without
solving the FT problem. However, the COT algorithm can be (and has been)
combined with (string-wise) IT functions capable of solving the FT problem to
provide an integrated solution for consistency maintenance and group undo. With an FT solution at the IT function
level, the COT algorithm is not required to enforce the permissible execution
and transformation orders and can allow any of these possible executions orders
(which meet the causal/context-dependency ordering relationships among
operations) to occur in a session, but still achieve correct do and undo
effects. The reader is referred to Figure
7 for an illustration of achieving
correct do and undo effects under all six possible execution orders in the
classic FT scenario; or try the OTXplorer system
for a comprehensive suite of benchmarking scenarios for validating OT solutions
with respect to OT algorithmic correctness requirements for both do and undo, and
solutions to all known OT puzzles.
3.27. What
are the main differences between the FT puzzle and other OT puzzles?
The FT puzzle is operation-type-dependent (only related
to Insert and Delete operations), and its solution can be localized within
transformation functions related to these operations; but other OT puzzles
(e.g. CP2-violation, IP2-violation, IP3-violation, or Pre-IT-violation,
etc.) are operation-type-independent
and can be solved at the OT control algorithm level, which is generic to all
operations [54].
The
FT puzzle and CP2-violation are related but different problems. They are
different because the FT is about object-ordering,
whereas CP2-violation is about object-divergence;
and abnormal object-ordering may not necessarily result in object divergence.
They are also subtly related because FT-caused abnormal object-ordering
scenarios are the only known scenarios in which (published) IT
functions may fail to ensure the CP2. All known CP2-violation scenarios are
actually variations of the FT puzzle [10, 18, 26,
31 43]. Assuming this observation is generally
true (no counter-example so far), it can be derived that an FT solution at the
transformation function level would solve CP2 at the function level as well.
However, solving CP2 does not require an FT solution. There have existed numerous CP2
solutions at the OT control algorithm level, including Jupiter [25], GOT [43], SCOP [33], SOCT4 [58], TIBOT [21], COT [53,
54], and Google Wave/Doc OT [59].
The FT puzzle is also
different from the operation-independent intention-violation problem: FT-caused
abnormal object-ordering does not necessarily violate operation intention, and
achieving intention-preservation does not
require an FT solution either.
[TOP | Previous section]
3.28. What
role does the puzzle-detection-resolution approach play in OT research ?
One driving force for the
advancement of OT is the curiosity of researchers in detecting and resolving
intellectually challenging OT puzzles. The puzzle-detection-resolution approach
has played a key role in discovering, testing and refining OT algorithm correctness requirements and
inventing novel OT techniques. Some OT algorithm correctness requirements were
unknown to the designers of OT algorithms/functions, but were later discovered
in detecting and solving relevant OT puzzles. For
example, the context-based pre-condition for IT functions (Pre-IT
or CC6) was discovered in the process of resolving the
well-known dOPT puzzle [42]. Established
context-based conditions can in return inspire invention of novel OT
algorithms, e.g. GOT [43], GOTO [42], and COT – a
Context-based OT control algorithm [54].
Established algorithm
correctness requirements also provide theoretic insights and practical
guidelines to better resolving OT puzzles. Some OT puzzles were initially detected
and resolved separately using ad hoc technical patches, but they were later
found to be related to the same algorithm correctness requirement; and such
insights then inspired the invention of general solutions to all of them. For
example, the insert-insert-tie
dilemma and overlapping deletes were
separately detected and resolved [46], but later found to be
related to the same IP3, and this insight led to the general
solution based on an IP3-preserving function [50], or IP3-PC-breaking
control algorithm [54].
The OTXplorer system can be used to support the puzzle-detection-resolution approach and
enable OT researchers to evaluate existing/new OT algorithms by scenario-based
benchmarks, and help industry developers select suitable OT techniques and
systems to be used in real-world collaborative applications.
[TOP | Previous
section ]
3.29. What
role does theoretic verification play in OT algorithm correctness study?
Theoretic verification plays an important role in OT correctness
study. Theoretic verification is generally effective if the correctness issues
have been well-understood and the verification criteria and boundary conditions
have been well-defined. Theoretic
verification may be conducted manually [50, 23,
30, 54,
18] or assisted by tools such
as an automatic theorem prover [10].
Theoretic verification has
been effective for correctness study of OT control
algorithms because those algorithms are generic and governed mainly by
context-based transformation conditions CC1
– CC6, which lend themselves well for rigorous verification. Major OT
control algorithms have been theoretically verified for correctness with
respect to those context-based conditions [50, 54].
Theoretic verification has so-far been less effective for
correctness study of transformation
functions because those functions are operation-specific,
application-dependent, and governed by transformation properties (e.g. Post-IT, Post-ET, RP, CP1, CP2, IP2, IP3), whose verification necessitates
rigorous description/formalization of operation and data models of the target
application, which is non-trivial. However, some transformation properties
(e.g. CP1,
CP2, IP2, IP3) can be
achieved at the control algorithm level (if suitable control algorithms are used) by
breaking their pre-conditions, which are operation/application-independent and
can be relatively easily verified at the control algorithm level [54].
Despite its importance in OT research, theoretic verification should
not be taken as a guarantee or a necessity for the correctness of an OT
solution. It is not a guarantee because verification criteria may cover only a
restricted part of a complete OT solution, and verification itself (either
manual or automatic) is complex and can get wrong: we have often seen theoretically proven
solutions are actually wrong but disproven solutions are correct because
verifiers got their criteria or method wrong. It is not a necessity because many aspects of an OT
solution (e.g. dynamic interactions among control algorithms, transformation
functions, operation and data addressing models, operation propagation
protocols, operation history buffering strategies, etc.) do not lend themselves
well to rigorous description and verification, and can be more effectively
addressed by real implementation, testing and benchmarking
(based on tools like OTXplorer).
OT research is exploratory and requires flexible use of a variety
of approaches/methods. Experimental and theoretic methods complement each
other in addressing OT correctness issues: experimental methods like puzzle-detection-resolution provide necessary insights into real
correctness issues, and help establish suitable criteria and conditions for
theoretic verification, which in turn helps guide experimental
exploration. OT history so far has
shown that the most effective and often-used approaches to solving real OT
problems and achieving correctness are experimental, and no theoretic method is
a substitute for a real
implementation in validating an OT design.
[TOP | Previous
section ]
3.30. What
role do real-world applications play in OT research?
One driving force for the
advancement of OT is the need for supporting real-world applications.
Real-world applications give impetus to OT research, which in turn enables
novel collaborative applications. Many OT techniques and systems were motivated
by the need for supporting real-world collaborative
applications (also see Table
5):
·
Collaborative text editors had inspired the invention of the first
OT algorithm [6] and served as vehicles
for continuous OT research in the past decades [5, 8,
12,
28,
30,
31,
43,
50,
58].
·
Collaborative editing of HTML/XML or tree-structured documents had
motivated the invention of OT techniques for supporting hierarchical addressing
domains [5,
8].
·
Collaborative spreadsheet editing had motivated the invention of
OT techniques for supporting 2D addressing space [27, 56,
63].
·
Collaborative word processing applications, such as CodoxWord and CoPowerPoint, had
stimulated the extension of OT to support conflict resolution caused by
concurrent update operations [51], and the invention of the
OT-based Generic Collaborative Engine and Transformation Adaptation technologies [60, 52].
·
Collaborative computer-aided design and digital media tools, such
as CoMaya,
had driven the invention of OT techniques for supporting complex 3D objects [1, 2,
3].
On the other hand, OT
techniques for collaborative plain/rich text editing have supported commercial
real-time collaborative editors, such as SubethaEdit
and EtherPad. OT techniques for collaborative HTML/XML
editing and word processing have supported novel collaborative web-based
applications and services, such as Google Docs, Google Wave, Novell Vibe, and IBM OpenCoWeb. Existing
and emerging real-world applications provide exciting opportunities and fresh
stimuli to future OT research and technological innovation.
[TOP | Previous section
]
1.
2.
3.
Agustina, C. Sun and D. Xu:
“Operational Transformation for Dependency Conflict Resolution in Real-time
Collaborative 3D Design Systems,” Proc. of ACM Conf. on Computer Supported
Cooperative Work, Feb. 2012.
4.
J. Begole, M.B.
Rosson, and C.A. Shaffer: “Flexible collaboration transparency: supporting worker independence in
replicated application-sharing systems,” ACM Trans. On
Computer-Human Interaction, Vol. 6, No. 2, pp. 95 – 132, Jun. 1999.
5.
A. Davis, C. Sun and J. Lu:
“Generalizing operational transformation to the standard general markup
language,” Proc. of ACM Conf. on Computer Supported Cooperative Work,
pp. 58 – 67. Nov.16 – 22, 2002.
6.
C. A. Ellis and S. J. Gibbs: “Concurrency control in groupware systems,” Proc. of the ACM
SIGMOD Conf. on Management of data, pp. 399 – 407, 1989.
7.
N. Gu, J. Yang, and Q.
Zhang: “Consistency maintenance based on the mark & retrace technique in
groupware systems,” Proc. of the ACM
Conf. on Supporting Group Work, pp. 264 – 273, Sep. 2005.
8.
C. Ignat, and M.C. Norrie: “Customizable collaborative editor relying on treeOPT algorithm,” Proc. of the European
Conf. on Computer Supported Cooperative Work, pp. 315 – 334, Sep. 2003.
9.
C. Ignat, and M.C. Norrie: “Multi-level
editing of hierarchical documents,” Journal of Computer Supported Cooperative Work, Vol. 17,
No. 5-6, pp. 423 – 468, Dec. 2008.
10. A. Imine, P. Molli, G.
Oster, G., and M. Rusinowitch: “Proving correctness of
transformation functions in real-time groupware,” Proc. of the European
Conf. on Computer Supported Cooperative Work, pp. 277 – 293, Sep. 2003.
11. L. Lamport: “Time, clocks, and the ordering of events in a
distributed system,” Commun. ACM, Vol. 21, No. 7, pp. 558 – 565, 1978.
12. D. Li and R. Li: “Transparent sharing and
interoperation of heterogeneous single-user applications,” Proc. of the ACM
Conference on Computer-Supported Cooperative Work, pp. 246 – 255, Nov.
2002.
13. D. Li and R. Li: “Preserving operation effects relation in group editors,” Proc. of the ACM
Conf. on Computer Supported Cooperative Work, pp. 427 – 466, Nov. 2004.
14. D. Li and R. Li: “An operational
transformation algorithm and performance evaluation,” Journal of Computer
Supported Cooperative Work, Vol. 17, No. 5 – 6, pp. 469 – 508, Dec. 2008.
15. D. Li and R. Li: “A landmark-based transformation approach to concurrency control in
group editors,” Proc. of the ACM
Conf. on Supporting Group Work, pp. 248 – 293, Nov. 2005.
16. D. Li and R. Li: “An
approach to ensuring consistency in peer-to-peer real-time group editors,” Journal of Computer Supported Cooperative Work, Vol. 17,
No. 5 – 6, pp. 553 – 611, Dec. 2008.
17. D. Li and J. Lu: “An operational transformation algorithm and performance evaluation,” Journal of Computer Supported Cooperative Work, Vol. 17,
No. 5 – 6, pp. 469 – 508, Dec. 2008.
18. R. Li and D. Li: “A new operational transformation framework for real-time group editors,” IEEE. Trans. On
Parallel and Distributed Systems, Vol. 18, No. 3, pp. 307 – 319, Mar. 2007.
19. D. Li, L. Zhou, R. Muntz,
and C. Sun: “Operation propagation in
real-time group editors,” IEEE Multimedia, Vol. 7, No. 4, pp. 55 – 61, Oct. 2000.
21. R.
Li, D. Li and C. Sun: “A time interval based
consistency control algorithm for interactive groupware applications,” Proc. of the IEEE
Conf. on Parallel and Distributed Systems, pp. 429 – 436, Jul. 2004.
22. R. Li and D. Li:
“Commutativity-Based Concurrency Control in Groupware," Proc. of the First IEEE Conf. on
Collaborative Computing, 2005.
23.
B.
Lushman and G. Cormack: “Proof of correctness of Ressels’ adOPTed algorithm,” Information
Processing Letters, (86): 303 – 310, 2003.
24. P.
Molli, G. Oster, H.S. Molli, and A. Imine: “Using the transformational
approach to build a safe and generic data synchronizer,” Proc. of the ACM Conf. on Supporting Group Work,
pp. 212 – 220, Nov. 2003.
25.
D. Nichols, P. Curtis,
M. Dixon, and J. Lamping: “High-latency, low-bandwidth windowing in the Jupiter collaboration
system,”
Proc. of the ACM Symposium on User Interface Software and Technology,
pp.111 – 120, Nov. 1995.
26. G. Oster, P. Urso, P.
Molli, and A. Imine: “Data consistency for P2P collaborative editing,”
Proc. of the ACM Conf. on Computer Supported Cooperative Work, pp. 259 –
268, Dec. 2006.
27.
C.R. Palmer and G.V.
Cormack: “Operation transforms for a distributed shared spreadsheet,”
Proc. of the ACM Conf. on Computer Supported Cooperative Work, pp. 69 –
78, Nov. 1998.
28.
A. Prakash and M.
Knister: “A framework for undoing actions in collaborative systems,”
ACM Trans. On Computer-Human Interaction, Vol. 1, No. 4, pp. 295 – 330,
Dec. 1994.
29.
M. Ressel and R.
Gunzenhauser: “Reducing the problems of group undo,”
Proc. of the ACM Conf. on Supporting Group Work, pp.131 – 139, Nov.
1999.
30.
M. Ressel, D.N. Ruhland,
and R. Gunzenhauser: “An integrating, transformation-oriented approach to concurrency control
and undo in group editors,”
Proc. of the ACM Conf. on Computer Supported Cooperative Work, pp. 288 –
297, Nov. 1996.
31.
B.
Shao, D. Li, and N. Gu “A Sequence Transformation Algorithm for Supporting
Cooperative Work on
32. B.
Shao, D. Li, and N. Gu "An algorithm for selective undo of any operation
in collaborative applications," Proc.
of ACM Conf. on Supporting Group Work, 2010.
33. H.F. Shen and C. Sun: “Flexible
Notification for Collaborative Systems,” Proc. of ACM Conf. on
Computer Supported Cooperative Work, pp. 77 – 86. Nov.16 – 22, 2002.
34. H.F. Shen and C. Sun:
“Flexible Merging for Asynchronous Collaborative Systems,” Proc. of Tenth
International Conf. on Cooperative Information Systems, Lecture Notes in
Computer Science 2519, pp. 304 – 321, Oct. 30 – Nov. 1, 2002.
35. H.F. Shen and C. Sun: “A
log compression algorithm for operation-based version control systems,” Proc.
of the 26th IEEE Annual International Computer Software and Application
Conf., pp. 867 – 872, Aug., 2002.
36. D.
Spiewak: “Understanding and applying operational transformation,” http://www.codecommit.com/blog/java/understanding-and-applying-operational-transformation
.
37. M. Suleiman, M. Cart,
and J. Ferrié: “Serialization of concurrent
operations in a distributed collaborative environment,” Proc. of the ACM conf. on Supporting group work, pp. 435 – 445, Nov.
1997.
38.
C. Sun, Y. Yang, Y.
Zhang and D. Chen: “A consistency model and supporting schemes in real-time
cooperative editing systems,” Proc. of the 19th Australian Computer Science
Conf., pp. 582 – 591, Jan. 1996.
40.
C.
Sun, X. Jia, Y. Zhang and Y. Yang: “A Generic Operation Transformation Scheme
for Consistency Maintenance in Real-time Cooperative Editing Systems,” Proc.
of ACM Conf. on Supporting Group Work, pp. 425 – 434, Nov. 16 – 19,
1997.
42.
C.
Sun and
43.
C.
Sun, X. Jia, Y. Zhang, Y. Yang and D. Chen: "Achieving convergence,
causality-preservation, and intention-preservation in real-time cooperative
editing systems," ACM Transactions on Computer-Human Interaction, Vol.
5, No. 1, pp.63 – 108, Mar., 1998.
44. C. Sun and R. Sosic: “Optional
Locking Integrated with Operational Transformation in Distributed Real-Time
Group Editors,” Proc. of 18th ACM Symposium on Principles of Distributed
Computing, pp. 43 – 52, May 4 – 6, 1999.
46. C. Sun: “Undo any operation at any
time in group editors,” Proc. of ACM Conf. on Computer Supported Cooperative
Work, pp. 191 – 200, Dec. 2 – 6, 2000.
47. C.
Sun and D. Chen: "Consistency maintenance in real-time collaborative
graphics editing systems," ACM Transactions on Computer-Human
Interaction, Vol. 9, No.1, pp. 1 – 41, Mar. 2002.
49.
C.
Sun: "Optional and Responsive Fine-grain Locking in Internet-based
Collaborative Systems," IEEE Transactions on Parallel and Distributed
Systems, Vol. 13, No. 9, pp. 994 – 1008, Sep. 2002.
50. C. Sun: "Undo as
concurrent inverse in group editors," ACM Transactions on
Computer-Human Interaction, Vol. 9, No. 4, pp. 309 – 361, Dec. 2002.
51. D. Sun, S. Xia, C. Sun, and D.
Chen: “Operational transformation for collaborative word processing,” Proc.
of ACM Conf. on Computer Supported Cooperative Work, pp. 437 – 446,
Nov. 6 – 10, 2004.
52.
C.
Sun, S. Xia, D. Sun, D. Chen. H.F. Shen and W. Cai: “Transparent adaptation of
single-user applications for multi-user real-time collaboration,” ACM
Transactions on Computer-Human Interaction, Vol. 13, No.4, pp. 531 – 582,
Dec. 2006.
53.
D.
Sun and C. Sun: “Operation context and context-based operational
transformation,” Proceedings of ACM Conf. on Computer Supported Cooperative
Work, pp. 279 – 288, Nov. 4 – 8, 2006.
55. D.
Sun, C. Sun, S. Xia and HF. Shen: "Creative Conflict Resolution in
Collaborative Editing Systems,” Proceedings of ACM Conf. on Computer
Supported Cooperative Work, Feb.
2012.
56. C.
Sun, H. Wen and H. Fan: “Operational Transformation for Orthogonal Conflict
Resolution in Real-time Collaborative 2D Editing Systems,” Proc. of ACM Conf. on
Computer Supported Cooperative Work, Feb. 2012.
57. D.
Sun, S. Xia and C. Sun: “Transparent Adaptation
(TA) and Codox Engine (CE) Illustrated,” 2010.
58.
N. Vidot, M. Cart, J. Ferrie and M. Suleiman: “Copies convergence in a distributed real-time collaborative environment,”
Proc. of the ACM Conf. on Computer Supported Cooperative Work, pp. 171 –
180, Dec. 2000.
59. D.
Wang and A. Mah: “Google wave operational transformation,” http://www.waveprotocol.org/whitepapers/operational-transform.
60.
S.
Xia, D. Sun, C. Sun, H.F. Shen and D. Chen: “Leveraging single-user
applications for multi-user collaboration: the CoWord approach,” Proc. of
ACM Conf. on Computer-Supported Cooperative Work, pp.162 – 171, Nov. 6 –
10, 2004.
61. S. Xia, D. Sun, C. Sun
and D. Chen: “Object-Associated Tele-pointer for Real-Time Collaborative
Document Editing Systems” Proc. of the IEEE International Conf on
Collaborative Computing. Dec. 19 – 21, 2005.
62. S.
Xia, D. Sun,
C. Sun and D. Chen: “Collaborative Object Grouping in Graphics Editing
Systems,” Proc. of The First IEEE International Conf on Collaborative
Computing, Dec. 19 – 21, 2005.
63. S. Xia, D. Sun, C. Sun,
and D. Chen: “A Collaborative Table Editing Technique Based on Transparent
Adaptation,” Proc. of International Conf. on Cooperative Information Systems,
Nov. 2 – 4, 2005.
64. S. Xia, D. Sun, C. Sun and D. Chen:
"An integrated session and repository management approach for real-time
collaborative editing systems." Proc. the Fourth International Conf. on
Creating, Connecting and Collaborating through Computing, 2006.
[TOP]
Copyright © 2010 – 2011 by
Chengzheng Sun. All rights
reserved.