العربية
中国
Français
Deutsch
Ελληνική
हिन्दी
Italiano
日本語
Português
Русский
EspañolOPERATIONAL TRANSFORMATION
'Operational transformation' (OT) is a theoretical framework of concurrency control that has been continuously researched in the context of group editing, a subfield of computer supported cooperative work (CSCW). OT typically replicates the shared document at all sites and allows any user to edit any part of the document at any time. Local editing operations are executed often without being delayed or blocked. Remote operations are transformed before execution to repair inconsistencies. The lockfree, nonblocking property of OT makes the local response time not sensitive to networking latencies. As a result, OT is particularly good for implementing group editing in the Web/Internet context.
OT can also be considered as an optimistic replication framework. Therefore, optimistic replication systems such as distributed file systems and distributed version control systems can be built on top of the OT framework.
OT was initially proposed for merging text documents represented as a sequence of characters . However, OT approach was also applied for merging hierarchical structures
such as XML documents, rich text documents ,
spreadsheets and tables. In OT mechanism was proposed as a generic merge framework.
OT was pioneered by Ellis and Gibbs Concurrency control in groupware systems, Ellis, C.A., , , ACM SIGMOD Record, 1989 . They proposed the dOPT approach and the GROVE group editor based on it. Several years later, some correctness issues were identified and several approaches such as adOPTed, Jupiter and GOT were proposed to solve these issues.
An OT framework considers n sites, each site owning a copy
of shared data. When a site performs an update, it generates a
corresponding operation. Every operation is processed in four steps:
# executed on one site,
# broadcasted to other sites, [1]
# received by other sites,
# integrated and executed on other sites.
OT frameworks distinguish two main components:
★ an 'integration algorithm'. This algorithm is in charge of reception, diffusion and execution of operations. When necessary, it calls transformation functions. This algorithm does not depend on type of replicated data ;
★ a set of 'transformation functions'. These functions merge concurrent modifications in serializing two concurrent operations. These functions are specific to a particular type of replicated data like string of characters, XML document or file system.
Up to now three correctness models of operational transformation were proposed.
The first and the basic correctness model of Operational Transformation was defined in dOPT and adOPTed
. These approaches use two criteria of correctness:
★ ''Causality'' : Considering two operations and , operation is said to precede if and only if is generated on a copy after was executed on this copy. Subsequently, may depend on effects of execution of . Causality preservation criterion ensures that all operations ordered by a precedence relation will be executed in the same order on every copy.
★ ''Convergence'' : When two operations are not causally connected by a precedence relation, they are concurrent. Two concurrent operations can be executed in different order on two different copies. Consequently, when an operation is received on one site, the current state of shared object may be different from the one where the operation has been generated. Thus, executing this operation in its generated form on a remote site may not preserve its effects and the copies may diverge.
Sun Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems, Chengzheng Sun, , , ACM Trans. Comput.-Hum. Interact., 1998 approach extended the correctness model defined in previous approaches by the concept of operation intention. The correctness criteria proposed by GOT are the following:
★ ''Causality'': the same definition as in CC Model
★ ''Convergence'': the same definition as in CC Model
★ ''Intention preservation''. Intention preservation criteria is expressed as follows: For any operation O, the effects of executing O at all sites are the same as the intention of O, and the effect of executing O does not change the effects of independent operations.
Operation intention was not formally defined in CCI model. The SDT and LBT approaches tried to formalise the notion of intention by means of the effects relation concept. The effects relation between two operations relies on the fact that there exists a total order relation between the target characters of the operations. The consistency model proposed by these approaches consist of the following properties:
★ ''Causality'': the same definition as in CC Model
★ ''Single-operation effects'':the effect of executing any operation in any execution state achieves the same effect as in its generation state
★ ''Multi-operation effects'': the effects relation of any two operations is maintained after they are both executed in any states
A transformation function takes two concurrent operations defined on the same state and return
a new operation defined on the state . A Transformation function is also named a ''forward transformation function'' or ''Inclusion transformation''
For example, suppose a type String with an operation ins(p,c,sid) where p is the position of insertion, c the character to insert and
sid the identifier of the site that has generated the operation. We can write the following transformation function:
T(ins(),ins()) :-
if () return ins()
else if ( and ) return ins()
else return ins()
In order to ensure correction, integration algorithms may require properties on transformation functions:
★ the property 'TP1' is defined as :
★ the property 'TP2' is defined as :
The TP2 property is difficult to achieve and currently only the TTF transformation set Tombstone Transformation Functions for Ensuring Consistency in Collaborative Editing Systems, Gerald Oster, , , Procs. 2nd Intl. Conf. on Collaborative Computing: Networking, Appln. and Worksharing, 2006 ensures TP2
Some integration algorithm (SOCT2, GOTO) requires to re-order operations in the local log in the case of partial concurrency. On the figure on the right, when arrives on site 1,
it cannot be transformed with because and are not defined on the same state. However, if site 1 can compute the equivalent log (ensured by condition TP1), then can be safely transformed with .
In this case, integration algorithms will call a ''backward transformation'' or ''exclusion transformation'' or ''inverse transformation''.
(caution ! definitions are not rigorously equivalent)
A backward transformation take two concurrent operations where is defined on the state and compute the operation which is defined on and is equivalent to .
(ins(),ins()) :-
if () return ins()
else if ( and ) return ins()
else return ins()
transformations have to ensure the reversibility property:
The Undo feature in OT allows users to Undo any operation at anytime i.e. not only the last operation, or your last operation. Ensuring the CC or the CCI correctness model
with the Undo feature is complex.
The undo effect of an operation is obtained by using its inverse operation .
More properties are required on transformation functions such as IP1, IP2, IP3. Some of those properties can be forced by the integration algorithm as in AnyUndo or COT.
★ Inverse Property 1 (IP1):
★ Inverse Property 2 (IP2):
★ Inverse Property 3 (IP3):
A continuous total order is a strict total order where it possible to detect a missing element i.e. 1,2,3,4,... is a continuous total order, 1,2,3,5,... is not a continuous total order. A continuous total order is costly to maintain in a distributed system.
★ OT has been mainly used for real-time group editors. Who really needs Real-time group editors ?
★ Transformation functions are difficult to write and prove.
★ What is really intentions ?
★ There are many other ways to merge data and OT is too complex.
★ Is the theoretical framework completely sound ?
★ CoWord is a free closed-source Collaborative real-time editor based on Ms Word
★ Ace is a free open-source Collaborative real-time editor
★ Gobby is a free open-source Collaborative real-time editor
★ Subethaedit is a commercial Collaborative real-time editor
★ So6 is a free open-source version control system integrated in the LibreSource platform.
★ Optimistic Replication
★ Data synchronization
★ Collaborative Editing
★ Consistency models
★ International Workshop on Collaborative Editing Systems
★ Distributed System Online - Collaborative editing
1. how the operation is broadcasted is out of the scope of OT. OT suppose that operations eventually arrive. The order of arrival is not ensured. see reliable multicast
OT can also be considered as an optimistic replication framework. Therefore, optimistic replication systems such as distributed file systems and distributed version control systems can be built on top of the OT framework.
OT was initially proposed for merging text documents represented as a sequence of characters . However, OT approach was also applied for merging hierarchical structures
such as XML documents, rich text documents ,
spreadsheets and tables. In OT mechanism was proposed as a generic merge framework.
History
OT was pioneered by Ellis and Gibbs Concurrency control in groupware systems, Ellis, C.A., , , ACM SIGMOD Record, 1989 . They proposed the dOPT approach and the GROVE group editor based on it. Several years later, some correctness issues were identified and several approaches such as adOPTed, Jupiter and GOT were proposed to solve these issues.
OT principles
An OT framework considers n sites, each site owning a copy
of shared data. When a site performs an update, it generates a
corresponding operation. Every operation is processed in four steps:
# executed on one site,
# broadcasted to other sites, [1]
# received by other sites,
# integrated and executed on other sites.
OT frameworks distinguish two main components:
★ an 'integration algorithm'. This algorithm is in charge of reception, diffusion and execution of operations. When necessary, it calls transformation functions. This algorithm does not depend on type of replicated data ;
★ a set of 'transformation functions'. These functions merge concurrent modifications in serializing two concurrent operations. These functions are specific to a particular type of replicated data like string of characters, XML document or file system.
Correctness models
Up to now three correctness models of operational transformation were proposed.
The CC Model
The first and the basic correctness model of Operational Transformation was defined in dOPT and adOPTed
. These approaches use two criteria of correctness:
★ ''Causality'' : Considering two operations and , operation is said to precede if and only if is generated on a copy after was executed on this copy. Subsequently, may depend on effects of execution of . Causality preservation criterion ensures that all operations ordered by a precedence relation will be executed in the same order on every copy.
★ ''Convergence'' : When two operations are not causally connected by a precedence relation, they are concurrent. Two concurrent operations can be executed in different order on two different copies. Consequently, when an operation is received on one site, the current state of shared object may be different from the one where the operation has been generated. Thus, executing this operation in its generated form on a remote site may not preserve its effects and the copies may diverge.
The CCI Model
Sun Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems, Chengzheng Sun, , , ACM Trans. Comput.-Hum. Interact., 1998 approach extended the correctness model defined in previous approaches by the concept of operation intention. The correctness criteria proposed by GOT are the following:
★ ''Causality'': the same definition as in CC Model
★ ''Convergence'': the same definition as in CC Model
★ ''Intention preservation''. Intention preservation criteria is expressed as follows: For any operation O, the effects of executing O at all sites are the same as the intention of O, and the effect of executing O does not change the effects of independent operations.
''the notion of ''Intentions'' has been often critized because it does not exist a formal definition of ''Intentions''. Consequently, how to prove that the model is correct ?''
The CSM Model
Operation intention was not formally defined in CCI model. The SDT and LBT approaches tried to formalise the notion of intention by means of the effects relation concept. The effects relation between two operations relies on the fact that there exists a total order relation between the target characters of the operations. The consistency model proposed by these approaches consist of the following properties:
★ ''Causality'': the same definition as in CC Model
★ ''Single-operation effects'':the effect of executing any operation in any execution state achieves the same effect as in its generation state
★ ''Multi-operation effects'': the effects relation of any two operations is maintained after they are both executed in any states
Transformation Functions
Illustration of the TP1 property
Illustration of the TP2 property
A transformation function takes two concurrent operations defined on the same state and return
a new operation defined on the state . A Transformation function is also named a ''forward transformation function'' or ''Inclusion transformation''
Forward Transformation Functions
For example, suppose a type String with an operation ins(p,c,sid) where p is the position of insertion, c the character to insert and
sid the identifier of the site that has generated the operation. We can write the following transformation function:
T(ins(),ins()) :-
if () return ins()
else if ( and ) return ins()
else return ins()
In order to ensure correction, integration algorithms may require properties on transformation functions:
★ the property 'TP1' is defined as :
For every pair of concurrent operations and defined on the
same state, the transformation function T satisfies property
if and only if:
where denotes the sequence of operations containing
followed by ; and where denotes equivalence of
the two sequences of operations.
★ the property 'TP2' is defined as :
For every three concurrent operations and
defined on the same state, the transformation function T satisfies
property if and only if:
This second property TP_2 stipulates ''equality'' between two
operations transformed with regard to two equivalent sequences of
operations. Given three operations and , the
transformation of with regard to the sequence formed by
followed by must give the same operation as the
transformation of with regard to the sequence formed by
followed by .
The TP2 property is difficult to achieve and currently only the TTF transformation set Tombstone Transformation Functions for Ensuring Consistency in Collaborative Editing Systems, Gerald Oster, , , Procs. 2nd Intl. Conf. on Collaborative Computing: Networking, Appln. and Worksharing, 2006 ensures TP2
Backward Transformation Functions
Illustration of the Partial Concurrency problem
Some integration algorithm (SOCT2, GOTO) requires to re-order operations in the local log in the case of partial concurrency. On the figure on the right, when arrives on site 1,
it cannot be transformed with because and are not defined on the same state. However, if site 1 can compute the equivalent log (ensured by condition TP1), then can be safely transformed with .
In this case, integration algorithms will call a ''backward transformation'' or ''exclusion transformation'' or ''inverse transformation''.
(caution ! definitions are not rigorously equivalent)
A backward transformation take two concurrent operations where is defined on the state and compute the operation which is defined on and is equivalent to .
(ins(),ins()) :-
if () return ins()
else if ( and ) return ins()
else return ins()
transformations have to ensure the reversibility property:
It is not safe, in the general case, to backward transform two causally dependant operations i.e. if we have , it is not safe to call . However, some authors, within a particular context, allow integration algorithms to call backward transformation function with two causal operations.
Undo in OT
The Undo feature in OT allows users to Undo any operation at anytime i.e. not only the last operation, or your last operation. Ensuring the CC or the CCI correctness model
with the Undo feature is complex.
The undo effect of an operation is obtained by using its inverse operation .
More properties are required on transformation functions such as IP1, IP2, IP3. Some of those properties can be forced by the integration algorithm as in AnyUndo or COT.
★ Inverse Property 1 (IP1):
The property IP1 expresses that the sequence has no effect on the document. This property has been formalized as:
Illustration of the IP3 property
★ Inverse Property 2 (IP2):
The property IP2 expresses that the sequence has no effect on the transformation of other operations. In other words, transforming any operation with this sequence must not modify the operation . The transformation functions satisfy if and only if:
★ Inverse Property 3 (IP3):
If and are two concurrent operations, the transformation functions satisfy the property IP3 if and only if . This property ensures that the order of reception of operations has no influence on the undo effect.
OT Integration Algorithms
A continuous total order is a strict total order where it possible to detect a missing element i.e. 1,2,3,4,... is a continuous total order, 1,2,3,5,... is not a continuous total order. A continuous total order is costly to maintain in a distributed system.
| Algorithm | Convergence | Causality | Transformations | Undo |
|---|---|---|---|---|
| GOTO | TP1+TP2 | State vectors | Forward and Backward transformations | Not supported |
| GOTO+AnyUndo Undo as concurrent inverse in group editors, Sun, C., , , ACM Transactions on Computer-Human Interaction (TOCHI), 2002 | TP1+TP2+IP1 | State Vectors | Forward and Backward transformations | Any operations |
| SOCT4 | TP1+Continuous Total Order | Timestamps | Forward transformation | Not Supported |
| SOCT2 | TP1+TP2 | State vectors | Forward and Backward transformation | Not Supported |
| ADOPTED | TP1+TP2 | State vectors | Forward transformation | Partially supported |
| COT | TP1+Continuous Total Order | Context Vectors | Forward transformation | Any Operation |
| GOT | UNDO-DO-REDO+Discontinuous Total order | State Vector | Forward + Backward transformations | ?? |
| MOT2 Synchronizer Based on Operational Transformation for P2P Environments, M. Cart, Jean Ferrié,, , , , 2006 | TP1 | None | Forward Transformation | Not Supported |
Criticisms of OT
★ OT has been mainly used for real-time group editors. Who really needs Real-time group editors ?
★ Transformation functions are difficult to write and prove.
★ What is really intentions ?
★ There are many other ways to merge data and OT is too complex.
★ Is the theoretical framework completely sound ?
OT Software
★ CoWord is a free closed-source Collaborative real-time editor based on Ms Word
★ Ace is a free open-source Collaborative real-time editor
★ Gobby is a free open-source Collaborative real-time editor
★ Subethaedit is a commercial Collaborative real-time editor
★ So6 is a free open-source version control system integrated in the LibreSource platform.
See Also
★ Optimistic Replication
★ Data synchronization
★ Collaborative Editing
★ Consistency models
External Links
★ International Workshop on Collaborative Editing Systems
★ Distributed System Online - Collaborative editing
References
1. how the operation is broadcasted is out of the scope of OT. OT suppose that operations eventually arrive. The order of arrival is not ensured. see reliable multicast
This article provided by Wikipedia. To edit the contents of this article, click here for original source.
psst.. try this: add to faves
