Operational transformation

From Wikipedia, the free encyclopedia

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 ^[1] ^[2] ^[3] ^[4] ^[5]. However, OT approach was also applied for merging hierarchical structures ^[6] ^[7] such as XML documents, rich text documents ^[8], spreadsheets ^[9] and tables. In ^[10] OT mechanism was proposed as a generic merge framework.

1 History
2 OT principles
- 2.1 Correctness models
3 Transformation Functions
- 3.1 Forward Transformation Functions
- 3.2 Backward Transformation Functions
4 Undo in OT
5 OT Integration Algorithms
6 Criticisms of OT
7 OT Software
8 See also
9 External links
10 References

[edit] History

OT was pioneered by Ellis and Gibbs^[1]. 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.

[edit] 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, ^[11]
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.

[edit] Correctness models

Up to now three correctness models of operational transformation were proposed.

[edit] The CC Model

The first and the basic correctness model of Operational Transformation was defined in dOPT and adOPTed ^[2]. These approaches use two criteria of correctness:

Causality : Considering two operations $o p 1$ and $o p 2$ , operation $o p 1$ is said to precede $o p 2$ if and only if $o p 2$ is generated on a copy after $o p 1$ was executed on this copy. Subsequently, $o p 2$ may depend on effects of execution of $o p 1$ . 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.

[edit] The CCI Model

Sun^[3] 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 intention has been often criticized as it lacks a formal and objective definition. Consequently, it is challenging to evaluate the adherence of an algorithm to the third correctness criteria proposed by GOT.

[edit] The CSM Model

Operation intention was not formally defined in CCI model. The SDT and LBT^[5] 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

[edit] Transformation Functions

Illustration of the TP1 property

Illustration of the TP2 property

A transformation function $T$ takes two concurrent operations $o p 1, o p 2$ defined on the same state $s$ and return a new operation $o p 1'$ defined on the state $s \circ op_2$ . A Transformation function is also named a forward transformation function or Inclusion transformation

[edit] 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( $p 1, c 1, s i d 1$ ),ins( $p 2, c 2, s i d 2$ )) :-
  if ( $p 1 < p 2$ ) return ins( $p 1, c 1, s i d 1$ )
  else if ( $p 1 = p 2$  and  $s i d 1 < s i d 2$ ) return ins( $p 1, c 1, s i d 1$ )
  else return ins( $p 1 + 1, c 1, s i d 1$ )

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 $o p 1$ and $o p 2$ defined on the same state, the transformation function T satisfies $T P 1$ property if and only if: $op_1 \circ T(op_2,op_1) \equiv op_2 \circ T(op_1,op_2)$ where $op_i \circ op_j$ denotes the sequence of operations containing $o p i$ followed by $o p j$ ; and where $\equiv$ denotes equivalence of the two sequences of operations.

the property TP2 is defined as :

For every three concurrent operations $o p 1, o p 2$ and $o p 3$ defined on the same state, the transformation function T satisfies $T P 2$ property if and only if: $T(op_3, op_1 \circ T(op_2,op_1)) = T(op_3, op_2 \circ T(op_1,op_2))$ This second property TP_2 stipulates equality between two operations transformed with regard to two equivalent sequences of operations. Given three operations $o p 1, o p 2$ and $o p 3$ , the transformation of $o p 3$ with regard to the sequence formed by $o p 2$ followed by $T (o p 1, o p 2)$ must give the same operation as the transformation of $o p 3$ with regard to the sequence formed by $o p 1$ followed by $T (o p 2, o p 1)$ .

The TP2 property is difficult to achieve and currently only the TTF transformation set^[12] ensures TP2

[edit] 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 $o p 3$ arrives on site 1, it cannot be transformed with $o p 1$ because $o p 1$ and $o p 3$ are not defined on the same state. However, if site 1 can compute the equivalent log $op_2 \circ op_1'$ (ensured by condition TP1), then $o p 3$ can be safely transformed with $o p 1'$ .

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 $T - 1 (o p 1, o p 2)$ take two concurrent operations $o p 1, o p 2$ where $o p 1$ is defined on the state $S \circ op_2$ and compute the operation $o p 1'$ which is defined on $S$ and is equivalent to $o p 1$ .

 $T - 1$ (ins( $p 1, c 1, s i d 1$ ),ins( $p 2, c 2, s i d 2$ )) :-
  if ( $p 1 < p 2$ ) return ins( $p 1, c 1, s i d 1$ )
  else if ( $p 1 = p 2$  and  $s i d 1 < s i d 2$ ) return ins( $p 1, c 1, s i d 1$ )
  else return ins( $p 1 - 1, c 1, s i d 1$ )

$T - 1$ transformations have to ensure the reversibility property: $T - 1 (T (o p 1, o p 2), o p 2) = o p 1$

It is not safe, in the general case, to backward transform two causally dependant operations i.e. if we have $S \circ op_1=ins(X,3) \circ op_2=del(3)$ , it is not safe to call $T - 1 (o p 2, o p 1)$ . However, some authors, within a particular context, allow integration algorithms to call backward transformation function with two causal operations.

[edit] 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 $o p$ is obtained by using its inverse operation $\overline{op}$ .

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 $op \circ \overline{op}$ has no effect on the document. This property has been formalized as: $S \circ op \circ \overline{op} = S$

Illustration of the IP3 property

Inverse Property 2 (IP2):

The property IP2 expresses that the sequence $op \circ \overline{op}$ has no effect on the transformation of other operations. In other words, transforming any operation $o p x$ with this sequence must not modify the operation $o p x$ . The transformation functions satisfy $I P 2$ if and only if: $T(op_x, op \circ \overline{op})=op_x$

Inverse Property 3 (IP3):

If $o p 1$ and $o p 2$ are two concurrent operations, the transformation functions satisfy the property IP3 if and only if $T(\overline{op_1},T(op_2,op_1))=\overline{T(op_1,op_2)}$ . This property ensures that the order of reception of operations has no influence on the undo effect.

[edit] 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 Requirements	Causality	Transformations	Undo
GOTO^[13]	TP1+TP2	State vectors	Forward and Backward transformations	Not supported
GOTO+AnyUndo^[14]	TP1+TP2+IP1	State Vectors	Forward and Backward transformations	Any operations
SOCT4^[15]	TP1+Continuous Total Order	Timestamps	Forward transformation	Not Supported
SOCT2^[4]	TP1+TP2	State vectors	Forward and Backward transformation	Not Supported
ADOPTED^[2]	TP1+TP2	State vectors	Forward transformation	Partially supported
COT^[16]	TP1+Continuous Total Order	Context Vectors	Forward transformation	Any Operation
GOT^[3]	UNDO-DO-REDO+Discontinuous Total order	State Vector	Forward + Backward transformations	??
MOT2^[17]	TP1	None	Forward Transformation	Not Supported

[edit] Criticisms of OT

Transformation functions are difficult to write and prove.
What is the formal definition for OT "intentions"?
There are many other ways to merge data and OT is too complex.
Is the theoretical framework completely sound?

[edit] 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^[10] is a free open-source version control system integrated in the LibreSource platform.

[edit] See also

[edit] External links

[edit] References

^ ^a ^b Ellis, C.A.; Gibbs, S.J. (1989). "Concurrency control in groupware systems". ACM SIGMOD Record 18 (2): 399–407. doi:10.1145/66926.
^ ^a ^b ^c Ressel, Matthias; Doris Nitsche-Ruhland ; Rul Gunzenhauser (1996). "An Integrating Transformation-Oriented Approach to Concurrency Control and Undo in Group Editors.". CSCW: 288-297.
^ ^a ^b ^c Chengzheng Sun; Xiaohua Jia ; Yanchun Zhang ; Yun Yang ; David Chen (1998). "Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems". ACM Trans. Comput.-Hum. Interact. 5 (1): 63–108. doi:10.1145/274444.274447.
^ ^a ^b Suleiman, M.; Cart, M.; Ferrié, J. (1998). "Concurrent Operations in a Distributed and Mobile Collaborative Environment". Proceedings of the Fourteenth International Conference on Data Engineering, February: 23-27.
^ ^a ^b Rui Li; Du Li (2005). "A landmark-based transformation approach to concurrency control in group editors". Proceedings of the 2005 international ACM SIGGROUP conference on Supporting group work: 284-293, ACM Press New York, NY, USA.
^ Claudia-Lavinia Ignat; Moira C. Norrie (2003). "Customizable collaborative editor relying on treeOPT algorithm". ECSCW'03: Proceedings of the eighth conference on European Conference on Computer Supported Cooperative Work: 315-334, Kluwer Academic Publishers.
^ Aguido Horatio Davis; Chengzheng Sun; Junwei Lu (2002). "Generalizing operational transformation to the standard general markup language". CSCW '02: Proceedings of the 2002 ACM conference on Computer supported cooperative work: 58-67, ACM Press.
^ David Sun; Steven Xia ; Chengzheng Sun ; David Chen (2004). "Operational transformation for collaborative word processing". CSCW '04: Proceedings of the 2004 ACM conference on Computer supported cooperative work: 437-446, ACM Press.
^ Christopher R. Palmer; Gordon V. Cormack (1998). "Operation transforms for a distributed shared spreadsheet". CSCW '98: Proceedings of the 1998 ACM conference on Computer supported cooperative work: 69-78, ACM Press.
^ ^a ^b Pascal Molli; Gerald Oster ; Hala Skaf-Molli ; Abdessamad Imine (2003). "Using the transformational approach to build a safe and generic data synchronizer". Proceedings of the 2003 international ACM SIGGROUP conference on Supporting group work: 212-220, ACM Press New York, NY, USA.
^ 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
^ Gerald Oster; Pascal Molli ; Pascal Urso ; Abdessamad Imine (2006). "Tombstone Transformation Functions for Ensuring Consistency in Collaborative Editing Systems". Procs. 2nd Intl. Conf. on Collaborative Computing: Networking, Appln. and Worksharing.
^ Sun, C.; Ellis, C. (1998). "Operational transformation in real-time group editors: issues, algorithms, and achievements". Proceedings of the 1998 ACM conference on Computer supported cooperative work: 59-68, ACM Press New York, NY, USA.
^ Sun, C. (2002). "Undo as concurrent inverse in group editors". ACM Transactions on Computer-Human Interaction (TOCHI) 9 (4): 309–361. doi:10.1145/586081.
^ Vidot, N.; Cart, M.; Ferrie, J.; Suleiman, M. (2000). "Copies convergence in a distributed real-time collaborative environment". Proceedings of the 2000 ACM conference on Computer supported cooperative work: 171-180, ACM Press New York, NY, USA.
^ Sun, D.; Sun, C. (2006). "Operation context and context-based operational transformation". Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work: 279-288, ACM Press New York, NY, USA.
^ M. Cart, Jean Ferrié, (2006). "Synchronizer Based on Operational Transformation for P2P Environments".

See also ebooksgratis.com: no banners, no cookies, totally FREE.