Patent Publication Number: US-8527440-B2

Title: System and apparatus for performing consistency maintenance of distributed graph structures that compares changes to identify a conflicting operation

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims priority to U.S. Provisional App. No. 61/392,273 filed on Oct. 12, 2010, the disclosure of which is expressly incorporated herein by reference in its entirety. 
    
    
     BACKGROUND 
     Real-time collaboration can allow remote participants to concurrently manipulate the same document and immediately see the other participant&#39;s changes without locking parts of the document or having to merge different versions. This can provide an improved user experience. 
     SUMMARY 
     In order to provide real-time collaboration to a wide range of applications in a flexible, domain independent and scalable way, the disclosed procedures work on a graph structure, which can be interpreted, for example, as (but not limited to) Business Process Model and Notation (BPMN) or Unified Modeling Language (UML) models, tables, text documents. Initially, identical copies of the graph structure are replicated at each participant&#39;s site. A small number of primitive operations can be used to manipulate this structure. As graphical editors manipulating the graph structure can perform complex and domain-specific operations, primitive operations can be grouped into complex operations, which can be exchanged by the participants to update their respective copies of the graph structure. To account for concurrent changes, these operations may need to be transformed against other concurrently performed operations. The transformation may be solely applied to the generic primitive operations and thus may be domain independent. This can allow the disclosed procedures to be reused for any application whose data can be mapped to a graph structure. 
     Implementations of the present disclosure include methods for synchronizing distributed graph structures representing application data. These methods can be independent from the actual application domain and can be reused for any application whose data can be mapped to a graph. In some implementations, methods include retrieving, at a computing device, the data structure from computer-readable memory, the data structure comprising a model including a plurality of objects and references between objects, receiving, at the computing device, first user input indicating a set of first changes to the model, each change in the set of first changes comprising one or more primitive operations, each primitive operation being executable to modify the model, applying changes of the set of first changes to the model to provide a first modified model, receiving, at the computing device, second user input indicating a set of second changes to the model, each change in the set of second changes comprising one or more primitive operations, each primitive operation being executable to modify the model, comparing the set of first changes to the set of second changes to identify a conflicting operation, applying one or more inverse operations to the first modified model to provide a second modified model, the one or more inverse operations corresponding to the conflicting operation and to one or more changes occurring after the conflicting operation, removing the conflicting operation from the set of first changes, defining a subset of first changes, the subset of first changes comprising the one or more changes occurring after the conflicting operation, reconciling one or more changes in the subset of first changes based on removal of the conflicting operation to provide a reconciled subset of first changes, defining an updated model by applying changes of the reconciled subset of first changes to the second modified model, and storing the updated model in computer-readable memory. 
     In some implementations, methods further include accessing one or more operational transformations stored in computer-readable memory, each transformation specifying how one primitive operation is transformed against another primitive operation, wherein comparing the set of first changes to the set of second changes is performed based on the one or more operational transformations. 
     In some implementations, the conflicting operation corresponds to an exclusive operational transformation, in which an operation of a change in the set of first changes conflicts with an operation of a change in the set of second changes. 
     In some implementations, reconciling one or more changes in the subset of first changes based on removal of the conflicting operation to provide a reconciled subset of first changes includes: accessing one or more operational transformations stored in computer-readable memory, each transformation specifying how one primitive operation is transformed against another primitive operation, and transforming the one or more changes in the subset of first changes based on the one or more operational transformations to account for absence of the conflicting operation. 
     In some implementations, defining an updated model further includes applying one or more changes of the set of second changes. 
     In some implementations, the set of second changes is generated at a first time and the set of first changes is generated as a second time, the second time being later than the first time. 
     In some implementations, applying one or more inverse operations includes: accessing an execution log comprising a sequence of operational transformations that have been applied to the model, determining a reverse sequence based on the sequence, and applying one or more inverse operations in the reverse sequence. 
     In some implementations, each change in the subset of first changes is affected by the conflicting operation. 
     In some implementations, the set of first changes includes a change. 
     In some implementations, the set of first changes includes a plurality of changes. 
     In some implementations, the set of second changes includes a change. 
     In some implementations, the set of second changes includes a plurality of changes. 
     In some implementations, the second user input is generated at a remote computing device and is transmitted to the computing device over a network. 
     In some implementations, the first user input is provided by a first user and the second user input is provided by a second user different from the first user. 
     In some implementations, the conflicting operation is a complex operation including a plurality of primitive operations. 
     The present disclosure also provides a computer-readable storage medium coupled to one or more processors and having instructions stored thereon which, when executed by the one or more processors, cause the one or more processors to perform operations in accordance with implementations of the methods provided herein. 
     The present disclosure further provides a system for implementing the methods provided herein. The system includes one or more processors, and a computer-readable storage medium coupled to the one or more processors having instructions stored thereon which, when executed by the one or more processors, cause the one or more processors to perform operations in accordance with implementations of the methods provided herein. 
     It is appreciated that methods in accordance with the present disclosure can include any combination of the aspects and features described herein. That is to say that methods in accordance with the present disclosure are not limited to the combinations of aspects and features specifically described herein, but also include any combination of the aspects and features provided. 
     The details of one or more embodiments of the present disclosure are set forth in the accompanying drawings and the description below. Other features and advantages of the present disclosure will be apparent from the description and drawings, and from the claims. 
    
    
     
       DESCRIPTION OF DRAWINGS 
         FIG. 1  is a diagram of an example of two participants manipulating a shared distributed document. 
         FIG. 2  is a block diagram of a generic platform for a collaborative modeling system that handles maintenance of graph structures. 
         FIG. 3  is a block diagram of an example model data structure. 
         FIG. 4  is a diagram showing a history of a model. 
         FIG. 5  is a diagram showing transforming a complex operation to be executed on a model. 
         FIG. 6  is a diagram showing the transforming of an alternative complex operation to be executed on a model. 
         FIG. 7  is a block diagram of an example for handling conflicting operations in a business process model. 
         FIGS. 8A-C  are diagrams showing the removal of a conflicting operation. 
         FIG. 9  is a flow chart of an example process for handling and removal of conflicting operations in a business model. 
         FIG. 10  is a schematic diagram of an example computing system that can be used to execute implementations of the present disclosure. 
     
    
    
     Like reference symbols in the various drawings indicate like elements. 
     DETAILED DESCRIPTION 
       FIG. 1  is a diagram of an example of two participants, a first participant  102  and a second participant  104  manipulating a shared distributed document. In the example of  FIG. 1 , operational transformations can be used to facilitate the collaborative editing of the shared distributed document. As shown in  FIG. 1 , initially both the first participant  102  and the second participant  104  have identical copies of a document (first document  102   a  and second document  104   a ). The document includes the string “ABC” in the first three positions in the document. Each document  102   a ,  104   a  is then subject to concurrent operations  106 ,  108  by the first participant  102  and the second participant  104 , respectively. For example, the first participant  102  one inserts “x” at position two in the document (insertion  106 ) leading to the string “AxBC”. Concurrently, the second participant  104  inserts “z” at position three in the document (insertion  108 ) leading to the string “ABzC”. 
     In some implementations, the first participant  102  and the second participant  104  can exchange the operations they have performed on their respective copy of the document, such that the other participant can also change their version of the document accordingly. However, each participant cannot apply the other&#39;s operation to their local document as the position for insertion of the character is changed once each participant inserts their character into the string. For example, if the first participant  102  inserted the changes of the second participant  104  into their copy of the document, the document would then include the string “AxzBC”. If the second participant  104  inserted the changes of the first participant  102  into their copy of the document, the document would then include the string “AxBzC”. At this stage, the documents have diverged and are not synchronized. In order to synchronize the copies of the document, the first participant  102  can transform the operation of the second participant  104  against the changes made to the document by the first participant  102 . In doing so, the first participant  102  can adjust the position at which the new character (‘x’) is inserted. Since the first participant  102  inserted the character ‘x’ at position two in the string “ABC”, the first participant  102  now has to insert the character ‘z’ at position four rather than position three in the string “ABC” in order to synchronize the changes to the string. This process can be referred to as an operational transformation (OT). 
     OT techniques can be applied to text as well as to data structures (e.g., Hypertext Markup Language (HTML) and XML) and tree structures. OT techniques can be used for synchronizing word processing documents in an application independent way. For example, trees can be used as approximations of software models. The force-fitting of the software model into a tree structure can result in dangling references across sub-trees. This can result in the generation of a corrupted software model. In some implementations, a graph can be used as an approximation of a software model where the graph includes different versions of nodes in order to handle conflicts. In some cases, ordered references as well as collaborative editing of an attribute of the software model (e.g., a text field documenting a specific node) may not be supported without applying an OT to the graph. 
     Control algorithms can determine what operations being performed in the collaborative editing of a distributed document are concurrent and therefore can be transformed. In some implementations, the control algorithms may not be tied to the underlying data structure of the document or the operations performed and therefore can be reused. In some implementations, the complexity of the control algorithms can cause the data structures to diverge. In such cases, a modified control algorithm can consider operation contexts as opposed to causal dependencies when determining what operations are concurrent. The modified control algorithm may work with inclusive transformations. In some cases, the modified control algorithm may not work with exclusive transformations, which can be more relevant when using a graph as approximation of a software model. 
     For example, when using a graph as an approximation of a software model, a graphical editor for manipulating the software model (e.g. UML, BPMN) can involve the use of fifteen to twenty different operations. In some cases, for example, approximately 225 to 400 different combinations of operations may be considered when implementing an OT. In addition, proof of convergence of the 225 to 400 different combinations of operations can be included when implementing an OT. The complexity of each proof of convergence can be increased dependent on the complexity of the associated operation or the underlying data structure. In addition, if a single operation is added (e.g., an increase from twenty operations to twenty-one operations), an additional forty-one combinations may have to be considered for the transformation along with the proof of convergence for each operation. Due to the large number of operations, in some cases, the OT can be prone to errors (e.g., implementation errors). 
       FIG. 2  is a block diagram of a generic platform  200  for a collaborative modeling system that handles maintenance of graph structures. For example, the platform  200  is a client-server architecture that includes clients  202 ,  204  and server  206 . The server  206  can be independent from the application running on the clients  202 ,  204 . First client  202  can include an application specific component  208  that includes editor  208   a  and editor operations  208   b  built on top of a graph structure  210  for a software model  210   b  that includes primitive operations. Similarly, second client  204  can include an application specific component  212  that includes editor  212   a  and editor operations  212   b  built on top of a graph structure  214  for a software model  214   b  that includes primitive operations  214   a . For first client  202 , operations in the application specific component (e.g., editor operations  208   b ) and the primitive operations (e.g., primitive operations  210   a ) can be combined into application specific complex operations. Similarly, for second client  204 , operations in the application specific component (e.g., editor operations  212   b ) and the primitive operations (e.g., primitive operations  214   a ) can be combined into application specific complex operations. The server  206 , the client  210  and the client  214  can perform operational transformations (e.g., OT  216  and OT  218 ) at the level of the primitive operations  210   a ,  214   a , respectively. 
     The example collaborative modeling system shown in  FIG. 2  can provide for the synchronization of a graphical editor and its operations (e.g., editor  208   a  and editor operations  208   b ) with an underlying document or data structure (e.g., the model  210   b ). Primitive operations  210   a  can be used to manipulate the data structure (e.g., the model  210   b ). A model (e.g., model  210   b ) can include of a set of objects (e.g., nodes in a graph) and references between objects (e.g., named edges on the graph). In some implementations, the model is classless as it does not refer to any class or type information. In some implementations, the model can include class information by introducing objects as tuples consisting of a unique object identifier and an identifier of the most specific class to which the object adheres in order to achieve a more operations framework approach to the modeling. In addition, reference assignments can be functional relations that map objects and reference names to lists of objects where sequences, for example, may be restricted to ordered sets. Objects can have attributes, which are functions mapping an object to a value of a primitive type (e.g., a string, an integer, a real, or a Boolean). 
     The following is an example of a definition of a model (e.g., model  210   b , model  214   b ). Let id={obj 1 , obj 2 , . . . } be an infinite set of object identifiers, let T={String, Integer, String, Boolean} be the set of primitive types and I(·) their usual interpretation, where I(Boolean)={true, false}, I(Integer)=Z, I(Real)=R and I(String) are possibly empty sequences over some characters. Let
 
Value= I (Boolean)∪ I (Integer)∪ I (Real)∪ I (String)∪{⊥}
 
be the set of values assignable to attributes including ⊥ which denotes an unassigned value. Let Name be an infinite set of names that identify an object&#39;s attributes or references, r.
 
     A model M is a tuple (O, A, R), with the following relations: O ⊂ id is the set of objects in the model, A: id×Name→Value is the total function that maps objects and attribute names to value assignments where A(o, a)=v such that o ∈ O   v ∈ Value. For example, v is the value of the attribute a of object o. If no value is assigned, ⊥ (an unassigned value) is returned. In addition, R: id×Name→(id× . . . ×id) is the set of reference assignments where R(o, r)=ō and ō=o1, . . . , on (n≧0). For example, ō is the list of objects referred to from object o by reference 
     The following notational conventions can be used in the subsequent description. Non-italicized characters are used to denote constants and names, and variables are italicized. In formal expressions covering a number of objects, the italicized characters: m, n, o, p and q will be used to denote objects. The use of ō (  m,  and  n ) can represent sequences of objects o 1 , . . . , o n  and o ∈ ō if o is an element in sequence ō. Similarly, u, v, w, x can represent values. Switching can occur between functional and relational notation for attribute assignments and references (e.g., (o, r, ō) ∈ R in place of R(o, r)=ō or vice versa, depending on what is more convenient). 
       FIG. 3  is a block diagram of an example model data structure  300 . The model data structure  300  can be represented using the model tuple (O, A, R) as described in  FIG. 2 .
     O={obj 1 , obj 2 , obj 3 , obj 4 , obj 5 }   A={(obj 1 , type, “PlainStartEvent”), (obj 2 , type, “SequenceFlow”), (obj 3 , type, “Activity”), (obj 4 , type, “SequenceFlow”), (obj 5 , type, “PlainEndEvent”), (obj 2 , name, “A”)}   R={(obj 4 , src, (obj 1 )), (obj 4 , tgt, (obj 2 )), (obj 1 , srcOf, (obj 4 )), (obj 2 , tgtOf, (obj 4 )), (obj 5 , src, (obj 2 )), (obj 5 , tgt, (obj 3 )), (obj 2 , srcOf, (obj 5 )), (obj 3 , tgtOf, (obj 5 ))}   

     Based on the definition of a model, a set of primitive operations can be defined to manipulate the different components of the model. The primitive operations can enable a user to add objects to and delete objects from the model. In addition, the primitive operations can allow the user to manipulate references between objects in the model. The primitive operations can allow the user to set new values for attributes. 
     For example, manipulating a reference between objects in the model can involve different semantics based on the cardinality of the reference. For example, if the cardinality of the reference is one, the reference may behave more like an attribute, where setting a new value replaces a previous value. References with a cardinality of one can be manipulated using the function: setRef( ). In another example, if the cardinality of the reference is many, adding a referenced object inserts the object into a sequence, and does not replace another object in the sequence. References with a cardinality of many are manipulated using the functions: addRef( ) or delRef( ) to add a referenced object into a sequence or delete a referenced object from a sequence, respectively. 
     In some implementations, in order to reduce the complexity of primitive operations, an object may be deleted from a model if there are n o references from the object and to the object, and all attributes for the object are set to ⊥ (the attributes have no assigned value). In some implementations, primitive operations performed on models can be defined in terms of their pre-conditions and their post-conditions. 
     For example, the function ω is a primitive operation, such that ω(M)=M′ with M=(O, A, R) and M′=(O′, A′, R′). Examples of primitive operations can include, but are not limited to, the following operations. 
     The primitive operation addObj(o) adds a new object o to model M. For each object, a universal unique identifier can be chosen in order to guarantee that different objects created by different participants do not happen to have the same object identifier. 
     pre: o∉O 
     post: O′=O∪{o} R′=R A′=A 
     The primitive operation delObj(o) removes an object o from model M. This operation can be used if there are no references from and to o and all of o&#39;s attributes are set to ⊥. 
     pre: o∈O   (o,r,ō)∈I R     (p,r,ō)∈R:o∈ō) (∀(o,a,v)∈A:v=⊥) 
     post: O′=O\{o} R′=R A′=A 
     The primitive operation addRef (o, r, p, i) adds a reference r from o top to the model M. This operation can be used if o and p are part of the model, p is not already referenced by r from o and index i is within the bounds. 
     pre: o,p∈O p∉ō=R(o,r) ō=o 1 , . . . o n   1≦i≦n+1 
     post: O′=O R′=R\{(o,r,ō)}∪{(o,r,(o 1 , . . . , o i− ,p,o i , . . . , o n ))} A′=A 
     The primitive operation delRef (o, r, p, i) deletes a reference r from o to p from the model M. This operation can be used if p is referenced by r from o at index i and r′s cardinality is many. 
     pre: o,p∈O R(o,r)=ō=o 1 , . . . , o i−1 ,p,o i+1 , . . . , o n    
     post: O′=O R′=(R\{(o,r,ō)}) ∪{(o,r,(o 1 , . . . , o i−1 , o i+1 , . . . , o n ))} A′=A 
     The primitive operation setRef(o, r, p, q) sets a unary reference r from o to q replacing p. This operation can be used if o currently references p by r, q is part of the model and r has cardinality of one. 
     pre: o,p,q∈O R(o,r)=p 
     post: O′=O R′=(R\{(o,r,p)}) ∪{(o, r, q)} A′=A 
     The primitive operation upd(o, a, v, w) replaces the attribute value v assigned to a of object o with the new value w. This operation can be used if o&#39;s attribute a is currently assigned to v. 
     pre: o∈O A(o,a)=v 
     post: O′=O A′=(A\{(o,a,v)})∪{(o,a,w)} R′=R 
     id( ) is the identical operation, which does nothing. 
     pre: true 
     post: O′=O A′=A R′=R 
     In some implementations, primitive operations may include one or more additional parameters used for performing the operation. For example, when setting a new attribute value, the old attribute value may not be known. The parameters can ensure that the set of primitive operations is closed under the inverse. For example, the addition of a new object to a sequence can be inversed by deleting the object from the sequence and the deletion of an object from a sequence can be, inversed by adding the object back into the sequence. In another example, the addition of a new reference can be inversed by deleting the reference and the deletion of a reference can be inversed by adding the reference back. For example, updating attributes or setting references can be inversed by swapping the new values with the old values. In addition, the identity operation can be its own inverse. The ability to define the inverse of an operation can prove beneficial when undoing changes made to a model in order to handle exclusive transformations. 
     For example, let ω be a primitive operation, then  ω  is its inverse such that  ω ∘ω=ω∘  ω =id. Examples of inverse operations can include, but are not limited to, the following operations. 
       addObj (o) =delObj (o) 
       delObj (o) =addObj (o) 
       addRef (o,r,p,i) =delRef (o, r, p, i) 
       delRef (o,r,p,i) =addRef (o, r, p, i) 
       setRef (o,r,p,q) =setRef (o, r, q, p) 
       upd(o,a,v,w) =upd(o, a, w, v) 
       id(□) =id( ) 
     Referring to  FIG. 2 , when manipulating a model (e.g., model  210   b ) through a graphical editor (e.g., editor  208   a ), one or more primitive operations can be performed on the model in sequence. For example, when adding a new activity a, a new object is created and its type attribute is set to “Activity”, its name attribute is set to “new Activity” and a reference pointing from the model m to the activity a is created. For example,
 
addAct( a,m )=addRef( m ,elements, a, 0)∘upd( a ,name,⊥,“newActivity”)∘upd( a ,type,⊥,“Activity”)∘addObj( a ).
 
     The sequence of primitive operations can form a complex operation that can be dependent on the actual domain used for the model (e.g., BPMN, UML). A complex operation, Ω, is a sequence of primitive operations ω 1 , . . . , ω n  where Ω=ω n ∘ . . . ∘ω 1 . For notational convenience, we can represent the complex operation as: Ω=ω 1 , . . . , ω n . 
     The inverse of a complex operation is the inverse of the sequence of primitive operations that formed the complex operation performed in reverse order. For the complex operation Ω=ω 1 , . . . , ω n , the inverse of the complex operation,  Ω , can be  Ω =  ωn , . . . ,  ω1  such that  Ω ∘Ω=id( ). 
     In some implementations, complex operations can group together one or more primitive operations. In some implementations, one or more states of a model can be reached when using a graphical editor running stand-alone (without collaboration). A sequence of complex operations can characterize the one or more states where additional in-between states may not be reached. The sequence of complex operations can encode model constraints or semantics and are exposed to the user as a single operation. Therefore, it may be desirable to ensure that the primitive operations of two concurrent complex operations do not interact in such a way that a state of the model can be reached which may not otherwise be produced by performing complex operations locally, without interference. 
     As described with reference to  FIG. 1 , operations of other participants may be seen in the light of one&#39;s own changes. A participant can transform another participant&#39;s operations against his or her own operations. For example, a collaborative modeling system (as shown in  FIG. 2 ) can use one of two types of operational transformations, either an inclusive transformation (IT) or an exclusive transformation (ET). An inclusive transformation can transform two operations, ω a , ω b , such that the resulting operation, ω′, includes the effects of both ω a  and ω b . For example,  FIG. 1  describes an inclusive transformation. When using an inclusive transformation, the resulting document includes all of the concurrently inserted characters. The inclusive transformation may not exclude one character in favor of another character. For an inclusive transformation to produce converging documents, the order in which the operations are transformed and applied are noted. As a notational convention, ω′ denotes the transformed version of ω. 
     For example, an inclusive transformation is a function IT(ω a , ω b )=ω′ where ω a  is translated against ω b  resulting in ω′ a . In addition, for all ω a , ω b , ω′ b ∘ω a =ω′ a ∘ω b  where ω′ a =IT (ω a , ω b ), and ω′ b =IT (ω b , ω a ). 
     In some implementation, an inclusive transformation may not be feasible. In some implementations, an exclusive transformation can be performed where the effects of one operation are excluded by another operation. For example, referring to  FIG. 2 , consider two concurrent operations, ω 1  and ω 2 , performed by a first client and a second client, respectively. The first operation, ω 1 , moves Activity A in one direction and the second operation, ω 2 , moves the Activity A to a different position. In this example, transforming one operation against another, at the same time, may not preserve the intention of each client  202 ,  204 . Therefore, the models in both clients (e.g., model  210   b  and model  214   b ) may diverge. In some implementations, additional efforts may bring the models (e.g., model  210   b  and model  214   b ) into synchronization. In some cases, an exclusive transformation may not produce any transformed operation. If performing the two concurrent operations does not pose a conflict, an exclusive transformation can perform in a similar manner as an inclusive transformation. In case there is a conflict, the transformation returns ⊥, and in doing so it can be symmetric, such that if ω a  is in conflict with ω b  then ω b  is in conflict with ω a  and both cases can result in ⊥. 
     For example, an exclusive transformation is a function ET(∩ a , ω b )=ω′ a , where ω a  is translated against ω b  resulting in ω′ a . In addition, for all ω a , ω b  either ω′ b ∘ω a =ω′ a ∘ω b  if and only if ω′ a ≠⊥ ω′ b ≠⊥, or ω′ a =⊥ if and only if ω′ b =⊥, where ω′ a =ET(ω a , ω b ), and ω′ b =ET(o)ω b , ω a ). In some implementation, an inclusive transformation can also be an exclusive transformation (e.g., a transformation that may not return ⊥) but not vice versa. 
     As described, a set of sequential primitive operations can define operational transformations for models. For example, referring to Table 1, an operational transformation T(ω a , ω b )=ω′ a  is defined, where ω a  is transformed against ω b . In Table 1, ω a  are listed on the left hand side, and ω b  are listed at the top. There can be a number of non-obvious considerations in the definition of the operational transformation shown in the transformation matrix of Table 1. In one example, a consistency property, ω′ b ∘ω a =ω′ a ∘ω b , may be guaranteed for cases that do not result in ⊥ (an unassigned value). For cases where there are conflicts, which can be symmetric, the problem of the conflict may be escalated and dealt with using a control algorithm, which will be described with reference to  FIGS. 4 ,  5 , and  6 . In another example, the operational transformation may not be completely inclusive or completely exclusive but a combination of both. 
     In some implementations, the operational transformation can be simple and directly included in a table. For example, the cells in the table that include X i  may be subject to operational transformations that are more complex. If an operational transformation is not possible, ⊥ (an unassigned value) is returned. For example, this may occur when the addition of a reference between two objects is transformed against the deletion of one of the objects participating in the reference. In order to delete an object, there may not be any references from the object or to the object, and all attribute values are set to ⊥. Therefore, translating the deletion of an object against updating its attribute value to anything other than ⊥ may fail. Alternatively, id( ) is returned if, for example, the addition of an object is transformed against the addition of the very same object, since an object can be added once. 
     
       
         
           
               
               
               
               
               
               
               
             
               
                 TABLE 1 
               
               
                   
               
               
                   
                 addObj(o) 
                 delObj(p) 
                 addRef(o,r,q,i) 
                 delRef(o,r,q,i) 
                 setRef(o,r,., i) 
                 upd(o,a,u,v) 
               
               
                   
               
             
            
               
                 addObj(p) 
                 id( ), if p=o 
                 ⊥, if p=o 
                 addObj(p) 
                 addObj(p) 
                 addObj(p) 
                 addObj(p) 
               
               
                   
                 addObj(p) 
                 addObj(p) 
                   
                   
                   
                   
               
               
                 delObj(p) 
                 ⊥, if p=o 
                 id( ), if p=o 
                 ⊥, if p=o V 
                 delObj(p) 
                 ⊥, if (p=o     
                 ⊥, if p=o     
               
               
                   
                 delObj(p) 
                 delObj(p) 
                 p=q 
                   
                 q≠⊥)Vp=q 
                 ν≠⊥) 
               
               
                   
                   
                   
                 delObj(p) 
                   
                 delObj(p) 
                 delObj(p) 
               
               
                 addRef(p,s,n,j) 
                 addRef(p,s,n,j) 
                 ⊥, if p=o V 
                 X 1   
                 X 2   
                 addRef(p,s,n,j) 
                 addRef(p,s,n,j) 
               
               
                   
                   
                 n=o 
                   
                   
                   
                   
               
               
                   
                   
                 addRef(p,s,n,j) 
                   
                   
                   
                   
               
               
                 delRef(p,s,n,j) 
                 delRef(p,s,n,j) 
                 id( ), if p=o 
                 X 3   
                 X 4   
                 delRef(p,s,n,j) 
                 delRef(p,s,n,j) 
               
               
                   
                   
                 delRef(p,s,n,j) 
                   
                   
                   
                   
               
               
                 setRef(p,s,m,n) 
                 setRef(p,s,m,n) 
                 ⊥, if (p=o     
                 setRef(p,s,m,n) 
                 setRef(p,s,m,n) 
                 X 5   
                 setRef(p,s,m,n) 
               
               
                   
                   
                 n≠⊥)Vn=o 
                   
                   
                   
                   
               
               
                   
                   
                 id( ),if (p=o     
                   
                   
                   
                   
               
               
                   
                   
                 n=⊥) 
                   
                   
                   
                   
               
               
                   
                   
                 setRef(p,s,m,n) 
                   
                   
                   
                   
               
               
                 upd(p,b,w,x) 
                 upd(p,b,w,x) 
                 ⊥, if p=o     
                 upd(p,b,w,x) 
                 upd(p,b,w,x) 
                 upd(p,b,w,x) 
                 X 6   
               
               
                   
                   
                 x≠⊥ 
                   
                   
                   
                   
               
               
                   
                   
                 id( ), if p=o     
                   
                   
                   
                   
               
               
                   
                   
                 x=⊥ 
                   
                   
                   
                   
               
               
                   
                   
                 upd(p,b,w,x) 
               
               
                   
               
            
           
         
       
     
     In some implementations, the transformation of operations that manipulate references can be a complex task. Similar to the example described in  FIG. 1 , the position at which an object is referenced is subject to transformation. For example, referring to Table 1, when transforming the addition of a reference against another addition of a reference (addRef( ) operation against addRef( )operation) different cases can be considered and are shown in the equation for X 1  below. For example, if all parameters of both operations are the same, id( ) is returned, as the reference has already been added and can be added once. For example, if all parameters of both operations are the same, but the index where to insert the object is different, ⊥ is returned as this constitutes a collision. However, if the requirement for the references to be sets is dropped, a collision would not occur and the referenced object could be added at different positions. In some cases, another way to remove the collision conflict is to change the semantics of addRef( ) in such a way that allows a referenced object to be moved to another index if it was added twice. For example, if different objects are inserted into the same reference, and the index of the first operation is greater than the index of the second operation, the first operation is returned with an incremented index. For example, if different objects are inserted into the same reference and the indexes are the same and object n is greater than object q (with respect to some total order), then the index of the first operation is incremented. In another example, the first operation is returned which covers the cases where the index of the first operation is less than the index of the second operation. 
     
       
         
           
             
               
                 
                   
                     X 
                     1 
                   
                   = 
                     
                   ⁢ 
                   
                     T 
                     ⁡ 
                     
                       ( 
                       
                         
                           addRef 
                           ⁡ 
                           
                             ( 
                             
                               p 
                               , 
                               s 
                               , 
                               n 
                               , 
                               j 
                             
                             ) 
                           
                         
                         , 
                         
                           addRef 
                           ⁡ 
                           
                             ( 
                             
                               o 
                               , 
                               τ 
                               , 
                               q 
                               , 
                               i 
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     { 
                     
                       
                         
                           
                             id 
                             ( 
                             ) 
                           
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               p 
                             
                             = 
                             
                               
                                 o 
                                 ⋀ 
                                 s 
                               
                               = 
                               
                                 
                                   r 
                                   ⋀ 
                                   n 
                                 
                                 = 
                                 
                                   
                                     q 
                                     ⋀ 
                                     j 
                                   
                                   = 
                                   i 
                                 
                               
                             
                           
                         
                       
                       
                         
                           ⊥ 
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               p 
                             
                             = 
                             
                               
                                 o 
                                 ⋀ 
                                 s 
                               
                               = 
                               
                                 
                                   r 
                                   ⋀ 
                                   n 
                                 
                                 = 
                                 
                                   
                                     q 
                                     ⋀ 
                                     j 
                                   
                                   ≠ 
                                   i 
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             addRef 
                             ⁡ 
                             
                               ( 
                               
                                 p 
                                 , 
                                 s 
                                 , 
                                 n 
                                 , 
                                 
                                   j 
                                   + 
                                   1 
                                 
                               
                               ) 
                             
                           
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               p 
                             
                             = 
                             
                               
                                 o 
                                 ⋀ 
                                 s 
                               
                               = 
                               
                                 
                                   r 
                                   ⋀ 
                                   n 
                                 
                                 ≠ 
                                 
                                   q 
                                   ⋀ 
                                   j 
                                 
                                 &gt; 
                                 i 
                               
                             
                           
                         
                       
                       
                         
                           
                             addRef 
                             ⁡ 
                             
                               ( 
                               
                                 p 
                                 , 
                                 s 
                                 , 
                                 n 
                                 , 
                                 
                                   j 
                                   + 
                                   1 
                                 
                               
                               ) 
                             
                           
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               p 
                             
                             = 
                             
                               
                                 o 
                                 ⋀ 
                                 s 
                               
                               = 
                               
                                 
                                   
                                     r 
                                     ⋀ 
                                     n 
                                   
                                   ≠ 
                                   
                                     q 
                                     ⋀ 
                                     j 
                                   
                                 
                                 = 
                                 
                                   
                                     i 
                                     ⋀ 
                                     
                                        
                                       n 
                                        
                                     
                                   
                                   &gt; 
                                   
                                      
                                     q 
                                      
                                   
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             addRef 
                             ⁡ 
                             
                               ( 
                               
                                 p 
                                 , 
                                 s 
                                 , 
                                 n 
                                 , 
                                 j 
                               
                               ) 
                             
                           
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
             
           
         
       
     
     For example, referring to Table 1, when transforming the addition of a reference against the deletion of a reference (addRef( ) operation against delRef( ) operation) different cases can be considered and are shown in the equations for X 2  and X 3  below. For example, indexes can be adjusted if objects from the same reference are manipulated. For example, referring to Table 1, when transforming the addition of a reference against another addition of a reference (addRef( ) operation against addRef( )operation) different cases can be considered and are shown in the equation for X 1  below. For example, if a referenced object is removed at an index before the index at which a referenced object is to be inserted, the index of the insertion can be decremented. In another example, if a referenced object is removed at an index after the index at which a referenced object is to be inserted, the first operation (addRef( )) is returned without any changes. For example, if the same object is deleted and added at the same time, a conflict can occur. This example may not occur as one of the operations would violate its precondition. For example, the reference can be removed if it was previously added, and it can be added if it is not already there. 
     
       
         
           
             
               
                 
                   
                     X 
                     2 
                   
                   = 
                     
                   ⁢ 
                   
                     T 
                     ⁡ 
                     
                       ( 
                       
                         
                           addRef 
                           ⁡ 
                           
                             ( 
                             
                               p 
                               , 
                               s 
                               , 
                               n 
                               , 
                               j 
                             
                             ) 
                           
                         
                         , 
                         
                           delRef 
                           ⁡ 
                           
                             ( 
                             
                               o 
                               , 
                               r 
                               , 
                               q 
                               , 
                               i 
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     { 
                     
                       
                         
                           
                             addRef 
                             ⁡ 
                             
                               ( 
                               
                                 p 
                                 , 
                                 s 
                                 , 
                                 n 
                                 , 
                                 
                                   j 
                                   - 
                                   1 
                                 
                               
                               ) 
                             
                           
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               p 
                             
                             = 
                             
                               
                                 o 
                                 ⋀ 
                                 s 
                               
                               = 
                               
                                 
                                   r 
                                   ⋀ 
                                   n 
                                 
                                 ≠ 
                                 
                                   q 
                                   ⋀ 
                                   j 
                                 
                                 &gt; 
                                 i 
                               
                             
                           
                         
                       
                       
                         
                           ⊥ 
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               p 
                             
                             = 
                             
                               
                                 o 
                                 ⋀ 
                                 s 
                               
                               = 
                               
                                 
                                   r 
                                   ⋀ 
                                   n 
                                 
                                 = 
                                 q 
                               
                             
                           
                         
                       
                       
                         
                           
                             addRef 
                             ⁡ 
                             
                               ( 
                               
                                 q 
                                 , 
                                 s 
                                 , 
                                 n 
                                 , 
                                 j 
                               
                               ) 
                             
                           
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
               
                 
                   
                     X 
                     3 
                   
                   = 
                     
                   ⁢ 
                   
                     T 
                     ⁡ 
                     
                       ( 
                       
                         
                           delRef 
                           ⁡ 
                           
                             ( 
                             
                               p 
                               , 
                               s 
                               , 
                               n 
                               , 
                               j 
                             
                             ) 
                           
                         
                         , 
                         
                           addRef 
                           ⁡ 
                           
                             ( 
                             
                               o 
                               , 
                               r 
                               , 
                               q 
                               , 
                               i 
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     { 
                     
                       
                         
                           
                             delRef 
                             ⁡ 
                             
                               ( 
                               
                                 p 
                                 , 
                                 s 
                                 , 
                                 n 
                                 , 
                                 
                                   j 
                                   + 
                                   1 
                                 
                               
                               ) 
                             
                           
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               p 
                             
                             = 
                             
                               
                                 o 
                                 ⋀ 
                                 s 
                               
                               = 
                               
                                 
                                   r 
                                   ⋀ 
                                   n 
                                 
                                 ≠ 
                                 
                                   q 
                                   ⋀ 
                                   j 
                                 
                                 ≥ 
                                 i 
                               
                             
                           
                         
                       
                       
                         
                           ⊥ 
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               p 
                             
                             = 
                             
                               
                                 o 
                                 ⋀ 
                                 s 
                               
                               = 
                               
                                 
                                   r 
                                   ⋀ 
                                   n 
                                 
                                 = 
                                 q 
                               
                             
                           
                         
                       
                       
                         
                           
                             delRef 
                             ⁡ 
                             
                               ( 
                               
                                 p 
                                 , 
                                 s 
                                 , 
                                 n 
                                 , 
                                 j 
                               
                               ) 
                             
                           
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
             
           
         
       
     
     For example, referring to Table 1, when transforming the deletion of a reference against the deletion of a reference (delRef( ) operation against delRef( ) operation) different cases can be considered and are shown in the equation for X 4  below. For example, if the same reference is manipulated, indexes can be adjusted. In another example, if the parameters of both operations are the same, the identical operation id( ) is returned, as a reference can be removed just once. For all other cases, the original operation is returned. 
     
       
         
           
             
               
                 
                   
                     X 
                     4 
                   
                   = 
                     
                   ⁢ 
                   
                     T 
                     ⁡ 
                     
                       ( 
                       
                         
                           delRef 
                           ⁡ 
                           
                             ( 
                             
                               p 
                               , 
                               s 
                               , 
                               n 
                               , 
                               j 
                             
                             ) 
                           
                         
                         , 
                         
                           delRef 
                           ⁡ 
                           
                             ( 
                             
                               o 
                               , 
                               r 
                               , 
                               q 
                               , 
                               i 
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     { 
                     
                       
                         
                           
                             delRef 
                             ⁡ 
                             
                               ( 
                               
                                 p 
                                 , 
                                 s 
                                 , 
                                 n 
                                 , 
                                 
                                   j 
                                   - 
                                   1 
                                 
                               
                               ) 
                             
                           
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               p 
                             
                             = 
                             
                               
                                 o 
                                 ⋀ 
                                 s 
                               
                               = 
                               
                                 
                                   r 
                                   ⋀ 
                                   n 
                                 
                                 ≠ 
                                 
                                   q 
                                   ⋀ 
                                   j 
                                 
                                 &gt; 
                                 i 
                               
                             
                           
                         
                       
                       
                         
                           
                             id 
                             ( 
                             ) 
                           
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               p 
                             
                             = 
                             
                               
                                 o 
                                 ⋀ 
                                 s 
                               
                               = 
                               
                                 
                                   r 
                                   ⋀ 
                                   n 
                                 
                                 = 
                                 q 
                               
                             
                           
                         
                       
                       
                         
                           
                             delRef 
                             ⁡ 
                             
                               ( 
                               
                                 q 
                                 , 
                                 s 
                                 , 
                                 n 
                                 , 
                                 j 
                               
                               ) 
                             
                           
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
             
           
         
       
     
     Unary references and attributes can behave in a similar. For example, if both operations set the same values of the same object&#39;s attribute, id( ) is returned, as the values of the object&#39;s attribute can be set just once. In another example, if the operations set the same attribute or reference to different values or objects, a collision occurs and ⊥ (an unassigned value) is returned. Therefore, once a complex operation is applied, all attributes and references are set as specified. If the setting of all attributes and references as specified is not a concern, then one value can override another value. In some cases, the overriding value can be selected based on a total order defined by values and object identifiers (ids), such that the greater value (or object) overrides the lower (or vice versa). In another example, if different attributes or references are set on different objects, no transformation may be performed and the same operation is returned. The different cases considered for the unary reference operation (e.g., setRef( )) and the attributes (e.g., upd( )) are shown in the equations for X 5  and X 6  below, respectively. 
     
       
         
           
             
               
                 
                   
                     X 
                     5 
                   
                   = 
                     
                   ⁢ 
                   
                     T 
                     ⁡ 
                     
                       ( 
                       
                         
                           setRef 
                           ⁡ 
                           
                             ( 
                             
                               p 
                               , 
                               s 
                               , 
                               m 
                               , 
                               n 
                             
                             ) 
                           
                         
                         , 
                         
                           setRef 
                           ⁡ 
                           
                             ( 
                             
                               o 
                               , 
                               r 
                               , 
                               
                                 · 
                                 
                                   , 
                                   q 
                                 
                               
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     { 
                     
                       
                         
                           
                             id 
                             ( 
                             ) 
                           
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               p 
                             
                             = 
                             
                               
                                 o 
                                 ⋀ 
                                 s 
                               
                               = 
                               
                                 
                                   r 
                                   ⋀ 
                                   n 
                                 
                                 = 
                                 q 
                               
                             
                           
                         
                       
                       
                         
                           ⊥ 
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               p 
                             
                             = 
                             
                               
                                 o 
                                 ⋀ 
                                 s 
                               
                               = 
                               
                                 
                                   r 
                                   ⋀ 
                                   n 
                                 
                                 ≠ 
                                 q 
                               
                             
                           
                         
                       
                       
                         
                           
                             setRef 
                             ⁡ 
                             
                               ( 
                               
                                 p 
                                 , 
                                 s 
                                 , 
                                 m 
                                 , 
                                 n 
                               
                               ) 
                             
                           
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
               
                 
                   
                     X 
                     6 
                   
                   = 
                     
                   ⁢ 
                   
                     T 
                     ⁡ 
                     
                       ( 
                       
                         
                           upd 
                           ⁡ 
                           
                             ( 
                             
                               p 
                               , 
                               b 
                               , 
                               w 
                               , 
                               x 
                             
                             ) 
                           
                         
                         , 
                         
                           upd 
                           ⁡ 
                           
                             ( 
                             
                               o 
                               , 
                               a 
                               , 
                               u 
                               , 
                               v 
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                   ⁢ 
                   
                     { 
                     
                       
                         
                           
                             id 
                             ( 
                             ) 
                           
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               p 
                             
                             = 
                             
                               
                                 o 
                                 ⋀ 
                                 b 
                               
                               = 
                               
                                 
                                   a 
                                   ⋀ 
                                   x 
                                 
                                 = 
                                 v 
                               
                             
                           
                         
                       
                       
                         
                           ⊥ 
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               p 
                             
                             = 
                             
                               
                                 o 
                                 ⋀ 
                                 b 
                               
                               = 
                               
                                 
                                   a 
                                   ⋀ 
                                   x 
                                 
                                 ≠ 
                                 v 
                               
                             
                           
                         
                       
                       
                         
                           
                             upd 
                             ⁡ 
                             
                               ( 
                               
                                 p 
                                 , 
                                 b 
                                 , 
                                 w 
                                 , 
                                 x 
                               
                               ) 
                             
                           
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
             
           
         
       
     
     In some implementations, referring to  FIG. 2 , the graphical editor (e.g., editor  208   a ) of a client (e.g., client  202 ) can perform a sequence of primitive operations, which the user can perceive as a single operation. For example, a user may push a button to add a new business process model (e.g., BPMN) activity to his model (e.g., model  210   b ). The client can create a new object, where several of the object&#39;s properties can be set and the object can be added to the business process model pool. The complex operations can preserve the intention of the user to maintain collaboration. The complex operations are applied in their entirety or, in some cases, may not be applied at all. 
     For example, two concurrent changes are performed on a document. A first change introduces a sequence flow between activities A and B. A second change deletes activity A. Since sequence flow connectors are objects themselves, introducing a sequence flow between two activities results in three primitive operations: one operation for creating the sequence flow object and the other two operations for setting the source and target references. The sequence flow cannot be connected to activity A as activity A is deleted. This can result in a dangling sequence flow connector, where a dangling sequence flow connector is different from a dangling reference (a reference to a non-existing object) as dangling references may not occur. This is ensured by the way the primitive operations and their transformation are constructed. The graphical editor may not provide the ability to construct dangling connectors by way of applying complex operations locally. Therefore, the operation that creates the sequence flow can be rejected. 
     In some implementations, a control algorithm chooses which operations are concurrent and as such are transformed. Note that the operations are bound (their parameters are bound to specific values or object identifiers). 
     A context-based operational transformation (COT) control algorithm can be used with complex operations. For example, causal relationships between operations can be used to determine which operations to transform (a causal theory). In some implementations, causality may not be sufficient in order to make operational transformations work correctly in all cases. For example, control algorithms can produce inconsistent models. In some implementations, the context of an operation can replace causality used in operational transformations. In some implementations, the basic ideas of COT can be adjusted to work with complex operations. 
     The context of an operation is the model to which the operation is applied. A model can be sufficiently characterized by the operations applied in order to create it. Therefore, the context of an operation ω applied to model M is the set of original (i.e., non-transformed) primitive operations that produced the model: C(ω)={ω 1 , . . . , ω n }≡M. 
       FIG. 4  is a diagram showing a history of a model. The model includes operations and their contexts. Primitive operations (e.g., operations ω 1 , ω 2 , ω 5 , ω 6 ) can be used to create the model M C1 . Primitive operations (e.g., operations (ω 1 , ω 2 , ω 3 , ω 4 ) can be used to create the model M C2 . 
       FIG. 5  is a diagram showing transforming the complex operation Ω 3  to be executed on model M C1 . For example, consider operation ω 4  in  FIG. 5  with the context: C(ω 4 )={ω 3 ,ω 2 ,ω 1 }. The context of a transformed operation is: C(ω′)=C(ω)∪{org(ω x )} where ω′=IT(ω, ω x ) and org(ω x ) denotes the original (non-transformed) operation of ω x . The context of a transformed operation ω′ is the context of the non-transformed operation ω plus the original operation of ω x . 
     In line with the context of operations, the history H(M) of a model M can be the set of original operations that lead to its current state. For example, model M C1  in  FIG. 5  can be characterized by {ω 1 ,ω 2 ,ω 5 ,ω 6 }=H(M C1 ). In some implementations, the context of a complex operation C(Ω) is equivalent to the context of its first primitive operation C(Ω)=C(ω 1 ) where Ω=ω 1 , . . . , ω n . The primitive operations of a complex operation can be consecutive without the interleaving of other operations for all primitive operations ω i (2≦i≦|Ω|) of a complex operation Ω: C(ω i )={ω i−1 }∪C(ω i−1 ). This ensures that complex operations are concurrent, or are either before or after another complex operation, and not intertwined. For example, ω 3 , ω 4  in  FIG. 5  may form a complex operation, and ω2, ω3, and ω4 may not. In addition, ensuring that complex operations are concurrent, or are either before or after another complex operation, and not intertwined can be applied on the inverse of complex operations. Given Ω=ω 1 , . . . , ω n , then Ω=ω n , . . . , ω 1  is its inverse with C(ω n )={ω n }∪C(ω n ) and C(ω n−1 )={ω n }∪C(ω n ). 
     Operations may meet a number of conditions in order for the operations to be transformed against each other. For example, a context condition C1 can be defined where given an original operation ω and a model M, where ω∉H(M), ω can be transformed for execution on M if C(ω ⊂ H(M). For example, referring to  FIG. 5 , ω 3  can be transformed for execution on M C1  since C(ω 3 )={ω 1 ,ω 2 } ⊂ H(M C1 )={ω 1 ,ω 2 ,ω 5 ,ω 6 }. Operation ω 4  cannot be transformed to be executed on M C2  without transforming and executing operation ω 3  first. 
     For example, a context condition C2 can be defined where given an original operation ω and a model M, where ω∉H(M) and C(ω)  ⊂ H(M), H(M)−C(ω) is the set of operations that ω can be transformed against before it can be applied to M. For example, referring to  FIG. 5 , in order to apply ω 3  to M C2 , ω 3  can be transformed against ω 5  and ω 6 . 
     For example, a context condition C3 can be defined where given an original operation ω and a model M, ω can only be applied to M if C(ω)=H(M). For example, referring to  FIG. 5 , ω 7  with context C(ω 7 )={ω 1 ,ω 2 ,ω 5 ,ω 6 }=H(M C1 ) can be executed on M C1 . 
     For example, a context condition C4 can be defined where given an original operation ω x , a (possibly transformed) operation ω and a model M, where ω x ∈C(ω), ω x  can be transformed to the context of ω only if C(ω x ) ⊂ C(ω). For example, referring to  FIG. 5 , ω 3  can be transformed to the context of ω 6  as C(ω 3 )={ω 1 ,ω 2 } ⊂ C(ω 6 )={ω 1 ,ω 2 ,ω 5 }. 
     For example, a context condition C5 can be defined where given an original operation ω x , a (possibly transformed) operation ω, where ω x ∈C(ω) and C(ω x ) ⊂ C(ω), C(ω)−C(ω x ) is the set of operations that ω x  can be transformed against before it can be IT transformed against ω. For example, referring to  FIG. 5 , ω 3  can be transformed to the context of ω 6  by transforming it against C(ω 3 )−C(ω 6 )={ω 5 }. 
     For example, a context condition C6 can be defined where any two operations ω a  and ω b  can be IT-transformed against each other (IT(ω a , ω b ) or IT(ω b ,ω a ) if C(ω a )=C(ω b ). For example, referring to  FIG. 5 , ω 3  can be transformed against ω 5 . 
     The context conditions C1-C6 can lead to the formulation of the context-based operational transformation (COT) shown in Algorithms 1, 2 and 3. For example, Algorithm 1 transforms and applies a primitive operation ω to a model M. Specifically, Algorithm 1 uses the context condition C2 to determine a set of operations against which the primitive operation ω can be transformed (line 2). Algorithm 1 applies the transformed operation ω′ to the model M(line 3). Algorithm 1 adds the original primitive operation ω to the model history H(M) (line 4). 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 1: 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
            
               
                   
                 Require: C(ω) ⊂ H(M), i.e. context condition C1 holds. 
               
               
                   
                 Ensure: ω∈H(M) and ω applied to model M. 
               
               
                   
                 1: procedure primitiveCOT(ω,M) begin 
               
               
                   
                 2: ω′ := transform(ω,H(M) − C(ω)) 
               
               
                   
                 3: Add ω to H(M) 
               
               
                   
                 4: M :=ω′(M) 
               
               
                   
                 5: end procedure 
               
               
                   
                   
               
            
           
         
       
     
     For example, Algorithm 2 transforms a primitive operation co against a set of primitive operations CD. Referring to Algorithm 2, transform(ω, CD) can take the primitive operation ω and transform the operation ω against all operations ω x  in CD (line 4) using context condition C5. As the primitive operation ω is transformed, the context of the primitive operation can be “upgraded” step by step (line 9) so that the primitive operation can be T-transformed (line 5) under context condition C6 and then applied to the model M (in the function primitive COT( )). The case where T( ) returns ⊥ (an unassigned value) can be ignored. 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 2: 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
            
               
                   
                 Require: ω ∉  H(M)     (∀ω x ∈CD : C(ω) ⊂ C(ω x )) 
               
               
                   
                 Ensure: C(ω) ⊂ C(ω′) where ω′ = transform(ω,CD) 
               
            
           
           
               
               
               
            
               
                   
                  1: 
                 function transform (ω,CD) begin 
               
               
                   
                  2: 
                 while CD is not empty do 
               
            
           
           
               
               
               
            
               
                   
                  3: 
                 Select and remove ω x from CD where C(ω x ) ⊂ C(ω) 
               
               
                   
                  4: 
                 ω′ x :=transform(ω x , C(ω) − C(ω x )) 
               
               
                   
                  5: 
                 ω′ := T(ω, ω′ x ) 
               
               
                   
                  6: 
                 if ω′ = ⊥ then 
               
            
           
           
               
               
               
            
               
                   
                  7: 
                 Collision with operation ω′ x . Terminate all 
               
               
                   
                   
                 transform procedures. 
               
            
           
           
               
               
               
            
               
                   
                  8: 
                 end if 
               
               
                   
                  9: 
                 C(ω′) := C(ω′) ∪{org(ω′ x )} 
               
               
                   
                 10: 
                 ω := ω′ 
               
            
           
           
               
               
               
            
               
                   
                 11: 
                 end while 
               
               
                   
                 12: 
                 return ω 
               
               
                   
                 13: 
                 end function 
               
               
                   
                   
               
            
           
         
       
     
       FIG. 6  is a diagram showing the transforming of the complex operation Ω 4  to be executed on model M C1 . For example, consider the transformation of primitive operations ω 3  and ω 4  to be applicable to model M C1 . Below is an execution log that includes line numbers for the respective procedures or functions. 
     primitiveCOT (ω 3 , M C1 ) 
     2: ω′ 3 :=transform(ω 3 , {ω 5 , ω 6 })
         3: ω x =ω 5      4: ω y :=transform (ω 5 , { })=ω 5      5: ω′ 3 :=T(ω 3 ,ω 5 )   9: C(ω′ 3 ):={ω 1 , ω 2 }∪{ω 5 }   3: ω x :=ω 6      4: ω y :=transform(ω 6 , { })=ω 6      5: ω″ 3 :=T(ω′ 3 , ω 6 )   9: C(ω″ 3 ):={ω 1 , ω 2 ,ω 5 }∪{ω 6 }       

     3: H(M C1 )={(ω 1 , ω 2 , ω 5 ,ω 6 }∪{ω 3 } 
     4: M C1 :=ω″ 3 (M C1 ) 
     In the next step, operation ω 4  is transformed. The recursion in line 14 (ω′ 6 :=T(ω 6 , ω 3 )) is executed to account for the transformation of operation ω 3  against operation ω 5  and operation ω 6 . The recursion demonstrates the possible difference between COT and algorithms based on the causal theory, which would omit the recursive step. 
     primitiveCOT (ω 4 , M C1 ) 
     2: ω″ 4 :=transform(ω 4 , {ω 5 , ω 6 })
         3: ω x =ω 5      4: ω y :=transform (ω 5 , {ω 3 })=ω′ 5  
           3: ω x :=ω 3      4: ω y :=transform (ω 3 , { })=ω 3      5: ω′ 5 :=T(ω 5 , ω 3 )   9: C(ω′ 5 ):={ω 1 , ω 2 }∪{ω 3 }   
           5: ω′ 4 :=T(ω 4 , ω′ 5 )   6: C(ω′ 4 ):={ω 1 , ω 2 , ω 3 }∪{ω 5 }   3: ω x =ω 6      4: ω y :=transform (ω 6 , {ω 3 })=ω′ 6  
           3: ω x :=ω 3      4: ω y :=transform (ω 3 , { })=ω 3      5: ω′ 6 :=T(ω 6 , ω 3 )   9: C(ω′ 6 ):={ω 1 , ω 2 ,ω 5 }∪{ω 3 }   
           5: ω′ 4 :=T(ω′ 4 , ω′ 6 )   9: C(ω″ 4 ):={ω 1 , ω 2 , ω3, ω5}∪{ω 6 }       

     9: H(M C1 )={ω 1 , ω 2 , ω 5 , ω 6 , ω 3 }∪{ω 4 } 
     4: M C1 :=ω″ 4 (M C1 ) 
     Algorithm 3 transforms and applies a complex operation Ω to a model M. Algorithm 3 demonstrates that the transforming and applying of complex operations to a model can occur in a way similar as the transforming and applying of primitive operations to a model. For example, a difference between the transforming and applying of the complex operations verses the transforming and applying of primitive operations can be that primitive operations may not be applied to the model directly after the transformation (line 4). In addition, the complex operations can be collected resulting in a complex operation Ω′ (line 7). The collection of complex operations, complex operation Ω′, can be applied to the model once the primitive operations are transformed (line 10). Applying the complex operation Ω′ to the model once the primitive operations are transformed can ensure that the complex operation Ω′ is transformed either entirely or not at all. If a collision occurs due to T( ) returning ⊥, the algorithm 3 is exited (line 5). 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 3: 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
            
               
                   
                 Require: Ω  ∉  H(M)    C(Ω)  ⊂ H(M) 
               
               
                   
                 Ensure:Ω is either entirely transformed and applied or not 
               
               
                   
                 transformed at all. 
               
            
           
           
               
               
               
            
               
                   
                  1: 
                 procedure complexCOT(Ω, M) begin 
               
            
           
           
               
               
               
            
               
                   
                  2: 
                 temp :=H(M) 
               
               
                   
                  3: 
                 for ω 1  to ω n  in Ω do 
               
            
           
           
               
               
               
            
               
                   
                  4: 
                 ω i  = transform(ω i , H(M) − C(ω)) 
               
               
                   
                  5: 
                 if collision occurred in transform then exit 
               
               
                   
                  6: 
                 Add ω i  to temp 
               
               
                   
                  7: 
                 Append ω′ I  to Ω′ 
               
            
           
           
               
               
               
            
               
                   
                  8: 
                 end for 
               
               
                   
                  9: 
                 Add temp to H(M) 
               
               
                   
                 10: 
                 end procedure 
               
               
                   
                   
               
            
           
         
       
     
       FIG. 7  is a block diagram of an example for handling conflicting operations in a business process model. In the example of  FIG. 7 , complex operation Ω 1  and complex operation Ω 2  are in conflict. Inclusive transformations can use algorithms 1, 2 and 3. Extensions can be made to algorithms 1, 2, and 3 to enable exclusive transformations to use algorithms 1, 2, and 3 where the exclusive transformation may return ⊥ (i.e., an unassigned value) when a conflict occurs. For example, the generic platform  200  shown in  FIG. 2  can be used for the collaborative modeling system for the complex operations. 
     Referring to  FIG. 7 , a server  706  and clients  702 ,  704  have a synchronized business process model (BPMN model) that includes activities  708   a ,  708   b  in pool  708 . Client  702  deletes activity  708   a  by executing complex operation Ω 1 =delObj(A). Meanwhile, client  704  creates a sequence flow connecting activity  708   a  and activity  708   b  by executing complex operation Ω 2 =addObj(SF), setRef (SF, src, ⊥, A), setRef (SF, tgt, ⊥, B). A user of client  702  (a participant) sends the complex operation Ω 1  to the server  706  (arrow  710 ). A user of client  704  (another participant) sends the complex operation Ω 2  to the server  706  (arrow  716 ) after the user of client  702  sends the complex operation Ω 1  to the server  706  (arrow  710 ). While the user of client  702  is waiting for a response from the server  706  (Ack as shown by arrow  714 ), client  704  performs another change to the activities  708   a ,  708   b , changing the name of activity  708   b  to X by executing complex operation Ω 3 =upd(B, name, B, X). The client  704  may not send the complex operation Ω 3  to the server  706  at this time because the client  704  has to wait for the response from the server  706  to the sending of the complex operation Ω 2  to the server  706 . 
     Client  704  receives complex operation Ω 1  from the server  706  (arrow  712 ), which tells the user of client  704  to delete activity  708   a . In addition, the client  704  receives no acknowledgement (NAck as shown by arrow  718 ) from the server  706  for the complex operation Ω 2  (the server does not acknowledge complex operation Ω 2 ). The execution of the complex operation Ω 1  is incompatible with the creation of the sequence flow connecting A and B (complex operation Ω 2  executed by client  704 ), since the exclusive operational transformation (as shown in Table 1) returns ⊥ for T (setRef (SF, src, ⊥, A), delObj(A)). The operation sent by the server  706  takes precedence over operation executed by the client  704  (complex operation Ω 2 ) as the operation sent by the server  706  has already been acknowledge to the originator (Ack as shown by arrow  714  to client  702 ) and, in addition, may have been already broadcasted to other clients (not shown). As such, client  704  can undo some of the user&#39;s local changes (e.g., undo or perform the inverse of complex operation Ω 2 ) in order to be able to apply complex operation Ω 1 . In addition, client  704  may retain and execute additional non-conflicting operations (e.g., complex operation Ω 3 ). After the reconciliation procedure, the model of client  704  reflects the application of complex model Ω′ 1  and complex model Ω′ 3  (not shown), which is a transformed version of complex model Ω 3  to account for the absence of the execution of complex model Ω 2 . 
     As described with reference to  FIG. 7 , if a conflicting operation is encountered in the local history of the model on the client, the conflicting operation can be undone in order to be able to apply the incoming operation from the server. In some implementations, the goal is to remove as few operations as possible. The client can determine the operations to remove by rolling back the conflicting operation and all other subsequently applied operations, reconciling the removed operations, and reapplying the reconciled operations. The client can repeat these steps until all collisions are removed and the complex operation Ω is applied to the model M successfully. 
     Algorithm 4 removes a complex operation from a client&#39;s local history where the server does not acknowledge the local history. If a collision occurs, the client rolls back the conflicting operation (line 5), reconciles the removed operation (line 6), and reapplies the reconciled operation (line 7). The client performs these steps until all operations are removed. 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 4: 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
            
               
                 Require: Complex operation Ω and model M such that Ω  ∉  H(M)and 
               
               
                 complex operation Ω is not acknowledged by the server 
               
               
                 Ensure: Ω ∈  H(M), complex operation Ω applied to model M 
               
            
           
           
               
               
            
               
                  1: 
                 procedure ecot(Ω, M) begin 
               
               
                  2: 
                 loop 
               
            
           
           
               
               
            
               
                  3: 
                 complexCOT(Ω, H(M) − C(Ω)) 
               
               
                  4: 
                 if collision with complex operation Ω c  occurs then 
               
            
           
           
               
               
            
               
                  5: 
                 R :=rollback(Ω c , M) 
               
               
                  6: 
                 R′ := reconcile(R, Ω c ) 
               
               
                  7: 
                 reapply(R′, M) 
               
            
           
           
               
               
            
               
                  8: 
                 else 
               
            
           
           
               
               
            
               
                  9: 
                 exit 
               
            
           
           
               
               
            
               
                 10: 
                 end if 
               
            
           
           
               
               
            
               
                 11: 
                 end loop 
               
               
                 12: 
                 end procedure 
               
               
                   
               
            
           
         
       
     
     Algorithm 5 removes a complex operation from a client&#39;s local history where the server did not acknowledge the complex operation by rolling back the conflicting operation. The client can roll back complex operations by applying the inverse of each operation included in the complex operations in reverse order, subsequently removing the operations from the model history. The client can access the execution log of the model (log L(M)=Ω n , . . . , Ω 1 ) and compare it to the local model history. As compared to the model history, the execution log includes the transformed operations in the sequence of their application. Going through the execution log in reverse order, the most recently applied operation is removed (line 3) and its inverse is applied to the model (line 4) and removed from the model history (line 5). For subsequent processing, a list of removed original operations is kept (line 9) in the reverse order of their removal (i.e. the order of the original application). These steps are repeated until the conflicting complex operation Ω is entirely removed (line 6). Algorithm 5 can terminate as it iterates over the (finite) execution log, and removes the last operation until the conflicting operation Ω is reached. 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 5: 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
            
               
                 Require: Complex operation Ω and model M such that Ω ∈  L(M)and 
               
               
                 complex operation Ω is not acknowledged by the server 
               
               
                 Ensure: all effects of the complex operation Q and subsequent operations 
               
               
                 are removed from the model M and the originals returned 
               
            
           
           
               
               
            
               
                  1: 
                 function rollback(Ω, M) begin 
               
               
                  2: 
                 loop 
               
            
           
           
               
               
            
               
                  3: 
                 Remove the last complex operation Ω x in L(M) 
               
               
                  4: 
                 M :=   Ω     x  (M) 
               
               
                  5: 
                 Remove orig(Ω x )from H(M) 
               
               
                  6: 
                 if Ω x  = Ω then 
               
            
           
           
               
               
            
               
                  7: 
                 return R 
               
            
           
           
               
               
            
               
                  8: 
                 end if 
               
               
                  9: 
                 Prepend org(Ω x ) to R 
               
            
           
           
               
               
            
               
                 10: 
                 end loop 
               
               
                 11: 
                 end function 
               
               
                   
               
            
           
         
       
     
     Algorithm 6 reconciles a sequence of operations with the removal of complex operation Ω. The steps performed by algorithm 6 reconcile the retained original operations by removing the conflicting operation. As such, all operations that have the conflicting operation in their context are of interest. These operations were generated after the application of the conflicting operation and therefore can be transformed to account for the absence of the conflicting operation, which is to be removed. 
     As previously described, an operation followed by its inverse has no net effect. Therefore, removing the conflicting operation from the context of the other operations by executing its inverse can result in no net effect. Therefore, the client can create the inverse of the conflicting operation such that it directly follows the original conflicting operation. The process of determining an inverse operation for each conflicting operation can effectively remove all effects of the conflicting operation. Any additional operations with the conflicting operation in their context can also be transformed against the inverse of the conflicting operation. All operations can have the conflicting operation directly followed by its inverse operation in their context. Since an operation followed by its inverse has no net effect, the pair can be safely removed from the contexts of all other operations. 
       FIGS. 8A-C  are diagrams showing the removal of conflicting operation L 1 . In the example of  FIGS. 8A-C , L denotes local operations on a client that are not acknowledged by a server. R denotes remote operations sent by the server to the client. As shown in  FIG. 8A , arrow  802  indicates that an operation O 1  is in the context of local operation L 1 . First, the local client executes the operation O 1 , common to all participants. Second, the local client executes a local operation L 1 . Concurrently, a remote client executes remote operation R 1 , which is then received by the local client. Upon the local client receiving remote operation R 1 , the client executes local operation L 2  and local operation L 3 . Subsequent to executing local operation L 2  and local operation L 3 , the client receives remote operation R 2 , which is in conflict with local operation L 1 . The server has not acknowledged any of the local operations (local operations L 1 , L 2  and L 3 ). In addition, the Operation O 1  may not be in conflict with any other operation as it has already been acknowledged by the server, which is implied by operation O 1  being in the context of remote operation R 1 . 
     In order for the client to apply remote operation R 2 , local operation L 1  has to be undone. The client can undo the application of local operation L 1  without losing the results of the application of the local operation L 2  and the local operation L 3 . In addition, the client can undo the application of local operation L 1  without losing the results of the application of any remote operations (e.g., remote operation R 1 ). 
     The following procedure leverages the fact that an operation followed by its inverse has no net result (  Ω ∘Ω=id( )). In order to undo application of local operation L 1 , the client can insert the inverse of the local operation L 1  (local operation  L 1   ) right after the local operation L 1 . In addition, the client can transform all other local operations (e.g., local operations L 2  and L 3 ) against the local operation  L 1   , such that they have local operation  L 1    in their context as shown in  FIG. 8B . Since an operation followed by its inverse has no effect on the model, the local operation pair L 1 ,  L 1    can be removed from the contexts of the other local operations (e.g., local operations L 2  and L 3 ) as shown in  FIG. 8C . Note, that the remote operation R 1  and remote operation R 2  are not affected by the removal of the local operation pair L 1 ,  L 1    as they do not depend on local operation L 1 . 
     In some implementations, other additional local operations may depend on local operation L 1  in such a way that they cannot be transformed against the inverse of the local operation L 1  (local operation  L 1   ). For example, this situation can occur when the local operation L 1  creates objects, which are then manipulated by other subsequent local operations. In this example, one or more subsequent local operations can also be removed by recursively applying the same procedure used to remove local operation L 1 . 
     Algorithm 6 reconciles a sequence of operations with the removal of the conflicting operation Ω. Algorithm 6 takes the conflicting operation Ω, which is to be removed, as input, as well as the sequence of removed operations R, returned by Algorithm 5. Algorithm 6 goes through the operations in the sequence of removed operations R (line 3). If the current operation Ω x  is in the context of the conflicting operation Ω (line 4), the current operation is transformed against {Ω,  Ω } (line 5). 
     In some implementations, the transformation may not be possible. For example, if the current operation Ω x  cannot be transformed against the conflicting operation Ω because the current operation Ω x  changes an attribute of an object created by the conflicting operation Ω, the current operation Ω x  can be excluded from the sequence of removed operations R. The procedure in Algorithm 6 is then recursively called (line 7). 
     In some implementations, if the transformation succeeds, the transformation can be permanent and the transformed operation Ω′ x  becomes its one original operation (line 9) and {Ω,  Ω } are both removed from context of the current operation Ω x , just as if the application of the conflicting operation Ω never occurred. The transformed operation Ω′ x  is added to the sequence of removed transformed operations R′. For example, if the current operation Ω x  is not in the context of the conflicting operation Ω, the current operation Ω x  may not be transformed and can be added to the sequence of removed transformed operations R′ without any changes (line 14). 
     The algorithm 6 iterates over the sequence of removed operations R and removes the first operation in the sequence. Should a collision occur, the recursion is invoked by passing the sequence of removed operations R without the offending operation that caused the collision. The sequence of removed operations R is reduced by at least one operation (the operation that caused the collision). In addition, new operations may not be added to the sequence of removed operations R. In a worst case scenario, the sequence of removed operations R includes operations that cause collisions. For example, assume the sequence of removed operations R consists of a sequence of complex operations each of which adds a new object and manipulates the object created by the previous. Removing the first operation in such a sequence can ripple through the entire chain of operations and cause the other operations to be removed as well. Therefore, the sequence of removed operations R is continuously reduced in size and subsequently the length of R can bind the recursive calls resulting in the eventual termination of Algorithm 6. 
     In some implementations, if it is not important to retain the local operations with a potential for further conflicts, Algorithm 6 can be simplified to return current operations Ω x  which do not have the conflicting operation Ω in their context. For example, this simplification results in the removal of lines 5 through 12 in Algorithm 6. 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 6: 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
            
               
                 Require: Complex operation Ω and model M such that Ω ∈  H(M)and 
               
               
                 complex operation Ω is not acknowledged by the server 
               
               
                 Ensure: ∀Ω x ∈R′ :Ω x   ∉  C(Ω x ) 
               
            
           
           
               
               
            
               
                  1: 
                 function reconcile (Ω, R) begin 
               
               
                  2: 
                 while R is not empty do 
               
            
           
           
               
               
            
               
                  3: 
                 Remove the first operation Ω x  in R 
               
               
                  4: 
                 if Ω ∈C(orig(Ω x ))then 
               
            
           
           
               
               
            
               
                  5: 
                 Ω′ x  :=transform(Ω x , {Ω,   Ω   }) 
               
               
                  6: 
                 if collision occurs then 
               
            
           
           
               
               
            
               
                  7: 
                 R :=reconcile(Ω x , R) 
               
            
           
           
               
               
            
               
                  9: 
                 else 
               
            
           
           
               
               
            
               
                 10: 
                 org(Ω′ x ) := Ω′ x   
               
               
                 11: 
                 C(Ω′ x ) := C(Ω′ x ) − {Ω,   Ω   } 
               
               
                 12: 
                 Append Ω′ x  to R′ 
               
            
           
           
               
               
            
               
                 13: 
                 end if 
               
            
           
           
               
               
            
               
                 14: 
                 else 
               
            
           
           
               
               
            
               
                 15: 
                 Append Ω x  to R′ 
               
            
           
           
               
               
            
               
                 16: 
                 end while 
               
               
                 17: 
                 return R′ 
               
               
                 18: 
                 end function 
               
               
                   
               
            
           
         
       
     
     Algorithm 7 reapplies the reconciled sequence of removed operations to the model M. For example, the reconciled operations are kept in the same order as they are removed, although some of the reconciled operations may have been transformed or removed. Algorithm 6 removed the conflicting operation from any subsequent operation&#39;s context. Therefore, the subsequent operation can be transformed (recall that the sequence of removed operations R can also include original remote operations) and applied to the model. 
     
       
         
           
               
             
               
                   
               
               
                 Algorithm 7: 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
            
               
                   
                 Require: 
               
               
                   
                 Ensure: 
               
               
                   
                 1: procedure reapply(R, M) begin 
               
               
                   
                 2: for Ω 1  to Ω n  in R do 
               
            
           
           
               
               
               
            
               
                   
                 3: 
                 R :=complexCOT(Ω i , M) 
               
            
           
           
               
               
            
               
                   
                 4: end for 
               
               
                   
                 5: end 
               
               
                   
                   
               
            
           
         
       
     
     Algorithms 5, 6, and 7 that implement rollback, reconcile and reapply can terminate after a finite number of steps. In addition, Algorithm 4 repeats the steps of rollback, reconcile and reapply until an operation Ω can be successfully applied to the model. In some implementations, if Algorithm 4 encounters a conflict with an existing operation, the offending operation to the existing operation is removed (through rollback, reconcile, and reapply) and a new attempt to apply the existing operation is performed. In some implementations, should the attempt to apply the existing operation fail again, the additional offending operation is also removed and the process is repeated. With each such iteration, the number of potentially conflicting operations (the operations not in the context of the existing operation Ω) is reduced by one and will eventually be zero (in the worst case where all operations conflict with the existing operation). The existing operation Ω is then guaranteed to be applicable and the algorithm terminates. 
     In order to achieve consistency, copies of the model (e.g., models on multiple clients) should converge to one set of equivalent models. For example, in order to produce a consistent model, the consistency property (exclusive transformation) should hold for the primitive operations. In addition, conflict resolution enables the models to converge in the cases where the transformation may not be possible. 
     The algorithms described in this document may be complex at runtime. For example, caching can be used to reduce runtime complexity. An exponential complexity at runtime can be based on the number of operations used by the transform function of the COT algorithm to recursively compute the same transformations. Caching the results of a transformation may lead to a reduction in runtime complexity. 
     For example, referring to Algorithm 2, line 4, the transform function upgrades operation ω x  to the context of operation ω. The original version of operation ω x  (org(ω x )) and the context of operation ω can uniquely identify the version produced by the transform. By caching the result, the transform function need not be performed again in the case where operation ω x  has to be upgraded again to the context of operation ω. The cache can include an original operation identifying a group of the operation&#39;s transformed versions. Within this group, operation ω identifies the version of interest, which has the same context as operation ω. 
     Continuing to refer to Algorithm 2, a cache is filled after line 5 with the operation version ω′, the result of the transformation T, which is then added to the group of org(ω′). For further optimization, an operation ω″=T(ω′ x ,ω) can also be added to the cache. Referring to  FIGS. 6 and 7 , the caching of ω″=T(ω′ x ,ω) can be beneficial. First, the cached operation ω″ can be used when transforming operation ω 3 , as ω 3  is transformed against ω 5 . In addition, the cached operation ω″ can be used when transforming operation ω 4 , as ω 5  is transformed against ω 3 . 
     A cache strategy can reduce an exponential runtime complexity to a quadratic complexity at the cost of a quadratic space complexity for storing multiple different versions of operations. In some implementations, many of the versions of the cached operations may not be used. In some implementations, when the version of the operation is used out of the cache, the version of the operation may be used once and then superseded by a newer version of the operation. In some implementations, there may be a group of versions of operations that are used more than once. These operation versions may be reused first. In some cases, an older version of an operation may not be used, a newer version may be used once and then superseded by yet another newer version. In order to manage the cache in a productive manner, the cache will store the most recently created version of an operation (deleting all older versions of the operation from the cache). In addition, the cache will permanently store the version of the operation that gets re-used first. This cache management strategy can work independent of the number of parallel operation streams (active participants at any one time) and can reduce the runtime to quadratic complexity and space complexity down to a linear complexity. 
     Transformation operations can be optimized by efficiently representing context. For example, let ω ij  be the j-th operation performed by client i. If C(ω) includes ω ij  it can also include ω ij-1 ,ω ij-2 , . . . , ω i1 . Therefore, the largest sequence number of the operation generated by the client can characterize the context of an operation. A vector CV(ω)=(s 1 , . . . , s n ) can be used to identify operations across a number of clients, where s i  is the largest sequence number generated by client i (1≦i&lt;n) and n is the number of different clients. CV(ω)[i] can refer to the sequence number of client i in the context of ω. 
     Similar to the context vector, a time stamp vector of an operation ω can be defined as T(ω)=(s 1 , . . . , s n ) where T(ω)[j]=CV(ω)[j]+1 for client j and T(ω)[i]=CV(ω)[i] for i≠j. Assuming client  1  generated operation ω 1  with CV(ω)=(0, 0), its time stamp is T(ω 1 )=(1, 0). 
     Referring to  FIG. 5  and Table 2 below, the following relations on vectors a=(a 1 , . . . , a n ) and b=(b 1 , . . . , bn) are introduced. If ai≦bi for (i=1, . . . , n), then a≦b for all components ai. Similarly, a&lt;b, if there is (at least) one pair aj, bj such that aj&lt;bj and for all other pairs ai≦bi. If neither a≦b nor b≦a, then a∥b. 
     Based on the vector representation of the contexts, it can also be decided whether the context of ω a  is a subset of the context of ω b , by checking whether the components of CV(ω a ) are less than or equal to the corresponding component of CV ω b ):
 
 C (ω a ) ⊂   C (ω b )   CV (ω a )≦ CV (ω b ).
 
     For example, assume CV(ω 3 )=(1, 1) and CV(ω 4 )=(1, 2), then C(ω 3 ) ⊂ C(ω 4 ). In addition, C(ω 4 ) ⊂ C(ω 3 ). For CV(ω 4 )=(1, 2) and CV(ω 6 )=(2, 1), C(ω 4 ) is not a subset of C(ω 6 ) and vice versa. Using the vector representation, it can also be decided whether an operation ω a  is part of the context C(ω 4 ). This is the case if the components of the time stamp T(ω a ) are less than or equal to the corresponding components of the context vector CV(Ω b ):
 
ω a   ∈C (ω b )   T (ω a )≦ CV (ω b )
 
     For example, ω 3  with T(ω 3 )=(1, 2) is in the context of ω 3  with CV(ω 4 )=(1, 2), and is not in the context of ω 5  with CV(ω 5 )=(1, 1), where the context of ω 3  is a subset of the context of ω 5 . Adding an operation ω b  to the context of ω 1 , where C(ω a )=C(ω b ) can be achieved by setting T(ω b ) and CV(ω a )results in:
 
 C (ω′ a ):= C (ω a )∪{ω b   }     C (ω a )= C (ω b )   CV (ω′ a ):= T (ω b )
 
This effectively ensures that T(ω b )≦CV(ω′ a ) and therefore ω b ∈C(ω′ a ).
 
     For example, when transforming ω 3  against ω 5 , C(ω′ 3 )=C(ω 3 )∪{ω 5 } because CV(ω 3 )=(1, 1) and T(ω 5 )=(2, 1) and therefore CV(ω 3 )=(2, 1). 
     The last operation that is performed as part of the ecot algorithm (e.g., see Algorithm 4) is subtracting the context of an operation from the context of another operation. This can be achieved by utilizing some of the expressions above, such as:
 
 C (ω a )− C (ω b )={ω|ω∈ C (ω a ) ω∉ C (ω b )}={ω| T (ω)≦ CV (ω a )   T (ω)≮ CV (ω b )}
 
Similarly, for subtracting a context from the model history:
 
 H ( M )− C (ω)={ω x |ω x   ∈H ( M ) ω x   ∉C (ω)}={ω x   |T (ω x )≦ T ( M )   T (ω x )≮ CV (ω)}
 
     The COT algorithm can compute the context difference frequently. An implementation of the COT algorithm that includes iterating over the model history and checking if each operation falls into the context difference can be computationally expensive. 
     
       
         
           
               
               
               
             
               
                 TABLE 2 
               
               
                   
               
               
                 Operation 
                 CV(ω i ) = 
                 T(ω i ) = 
               
               
                   
               
             
            
               
                 ω 1   
                 (0,0) 
                 (1,0) 
               
               
                 ω 2   
                 (1,0) 
                 (1,1) 
               
               
                 ω 3   
                 (1,1) 
                 (1,2) 
               
               
                 ω 4   
                 (1,2) 
                 (1,3) 
               
               
                 ω 5   
                 (1,1) 
                 (2,1) 
               
               
                 ω 6   
                 (2,1) 
                 (3,1) 
               
               
                   
               
            
           
         
       
     
     The history H of a model M can be interpreted as a set of sequences or lists each of which holds the sequential operations of a different client, using the context vectors or time stamp vectors as indices into the lists that mark the range of operations to include in the difference. In some implementations, the difference can be computed in constant time (assuming the number of clients is constant). The supremum and infimum controlling the difference can be defined as
 
inf( C (ω a )− C (ω b ))= CV (ω b )
 
sup( C (ω a )− C (ω b ))=(max CV (ω a )[ i],CV (ω b )[ i]   i=1, . . . ,n  
 
inf( C (ω a )− C (ω b ))&lt; T (ω d )≦sup( C (ω a )− C (ω b ))
 
     There are a number of optimizations that can reduce the complexity from an exponential level down to sub-linear level. Bypass recursive transformations are based on two observations. Firstly, the transformation matrix in Table 1 includes transformations which unconditionally return the original operation (e.g. T(addObj(p), addRef(o,r,q,i)), i.e. no actual transformation is performed. Secondly, the type of an operation stays the same or is changed into an identical operation (the operation that does nothing). The transforming and the addObj( ) operation can result in an addObj( ) or id( ) operation, and not in adelRef( )operation. Both observations taken together can be used to bypass an entire recursive decent in Algorithm 2. If ω and ω x  fall into the previously described category (i.e. an actual transformation is not performed), the recursion in line 4 can be bypassed by assigning ω x  to ω′ x . 
     Another worthwhile observation is that operations can be transformed against each other if they manipulate the same objects (leapfrog). For example, when transforming delObj(p) against addRef(o, r, q, i), an actual transformation can be performed if p=o or p=q. If not, delObj(p) is returned. This observation can be extrapolated to a whole set of operations. If an operation to be transformed against a whole set of operations manipulates different objects than the set of operations, the operation can leapfrog the entire set, as the transformation would yield the original operation. This observation can be applied in Algorithm 2 to bypass the entire while loop (lines 2 through to 11). 
     Algorithm 2 can perform computing a set difference multiple times. If implemented naively, this operation can be computationally expensive, as it has to check every operation in one set if it is also contained in the other set and therefore can be excluded from the result. An alternative method of computing differences can be based on context vectors. To perform set differences in constant time, the history H of a model M (the set of all operations applied to the model) is interpreted as a set of sequences as opposed to a plain set. The set of sequences includes one operation sequence per participant. Each sequence contains the operations issued by the respective participant in the same order in which they were issued. As such, context vectors can be used as pointers into these operation sequences as each component in the context vector represents the number of operations issued from the corresponding client that were included in the context. 
     The difference C(o 1 )−C(o 2 ) of two operation contexts of o 1 , o 2  can be sufficiently characterized by the two operations&#39; context vectors CV(o 1 ) and CV(o 2 ). The difference then includes all operations with sequence numbers less than CV(o 1 ) and greater then CV(o 2 ). Using the above outlined structure of the history, the context vectors can be used as pointers in to the sequences of operations. The operation difference does not have to be materialized and can be sorted with pointers only. It can also be enumerated without materializing. This reduces the time for computing differences and for selecting and removing operations with sub-contexts (line 3 in Algorithm 2) to constant time. 
       FIG. 9  is a flow chart of an example process  900  for handling and removal of conflicting operations in a business process model. A data structure for a model is received ( 902 ). Referring to  FIG. 3 , an example model data structure (e.g., model data structure  300 ) can include of a set of objects (e.g., nodes in a graph) and references between objects (e.g., named edges on the graph). First user input indicating a set of first changes for the model is received ( 904 ). For example, referring to  FIG. 7 , a user of client  702  sends the complex operation Ω 1  (a set of first changes) to the server  706  for a model that includes activities  708   a ,  708   b  in pool  708 . The set of first changes is applied to the model to provide a first modified model ( 906 ). For example, client  702  deletes activity  708   a  by executing the complex operation Ω 1 =delObj(A). Second user input is received indicating a set of second changes ( 908 ). For example, a user of client  704  sends the complex operation Ω 2  (a second set of changes) to the server  706  after the user of client  702  sends the complex operation Ω 1  to the server  706 . The set of first changes is compared to the set of second changes to identify a conflict ( 910 ). For example, an execution log for a model can include transformed operations (the first set of changes) in the sequence of their application to the model (e.g., complex operation Ω 1 ). A model history can include the second set of changes (e.g., complex operation Ω 2 ). The execution log for the model can be compared to the model history for the model to identify a conflicting operation. For example, referring to  FIG. 7 , the execution of the complex operation Ω 1  is incompatible with the execution of complex operation Ω 2 . 
     Inverse operations are applied to the first modified model to provide a second modified model with one or more changes occurring after the conflicting operation ( 912 ). The conflicting operation is removed from the set of first changes ( 914 ). A subset of first changes is defined ( 916 ). One or more changes in the subset of first changes is reconciled to provide a reconciled subset of first changes ( 918 ). An updated model is defined ( 920 ). The updated model is stored ( 922 ). 
     For example, Algorithm 5 can perform rollback. The conflicting operation is identified. The execution log is traversed in reverse order where the most recently applied operation listed in the execution log is removed from the log and inverse of the removed operation is applied to the model. The execution log continues to be traversed until the conflicting operation is reached. For subsequent processing, a list of removed original operations is kept in the reverse order of their removal (i.e. the order of the original application). These steps are repeated until the conflicting operation is entirely removed. 
     For example, Algorithm 6 can perform reconciliation. Algorithm 6 takes the conflicting operation and the sequence of removed operations and goes through the operations in the sequence of removed operations. If the current operation is in the context of the conflicting operation, the current operation is transformed against the conflicting operation. If the transformation is not possible, the current operation is excluded from the sequence of removed operations. 
     The present disclosure also provides a computer-readable storage medium coupled to one or more processors and having instructions stored thereon which, when executed by the one or more processors, cause the one or more processors to perform operations in accordance with implementations of the methods provided herein. 
     The present disclosure further provides a system for implementing the methods provided herein. The system includes one or more processors, and a computer-readable storage medium coupled to the one or more processors having instructions stored thereon which, when executed by the one or more processors, cause the one or more processors to perform operations in accordance with implementations of the methods provided herein. 
     It is appreciated that methods in accordance with the present disclosure can include any combination of the aspects and features described herein. That is to say, methods in accordance with the present disclosure are not limited to the combinations of aspects and features specifically described herein, but also include any combination of the aspects and features provided. 
     Referring now to  FIG. 10 , a schematic diagram of an example computing system  1000  is provided. The system  1000  can be used for the operations described in association with the implementations described herein. For example, the system  1000  may be included in any or all of the server components discussed herein. The system  1000  includes a processor  1010 , a memory  1020 , a storage device  1030 , and an input/output device  1040 . Each of the components  1010 ,  1020 ,  1030 , and  1040  are interconnected using a system bus  1050 . The processor  1010  is capable of processing instructions for execution within the system  1000 . In one implementation, the processor  1010  is a single-threaded processor. In another implementation, the processor  1010  is a multi-threaded processor. The processor  1010  is capable of processing instructions stored in the memory  1020  or on the storage device  1030  to display graphical information for a user interface on the input/output device  1040 . 
     The memory  1020  stores information within the system  1000 . In one implementation, the memory  1020  is a computer-readable medium. In one implementation, the memory  1020  is a volatile memory unit. In another implementation, the memory  1020  is a non-volatile memory unit. The storage device  1030  is capable of providing mass storage for the system  1000 . In one implementation, the storage device  1030  is a computer-readable medium. In various different implementations, the storage device  1030  may be a floppy disk device, a hard disk device, an optical disk device, or a tape device. The input/output device  1040  provides input/output operations for the system  1000 . In one implementation, the input/output device  1040  includes a keyboard and/or pointing device. In another implementation, the input/output device  1040  includes a display unit for displaying graphical user interfaces. 
     The features described can be implemented in digital electronic circuitry, or in computer hardware, firmware, software, or in combinations of them. The apparatus can be implemented in a computer program product tangibly embodied in an information carrier, e.g., in a machine-readable storage device, for execution by a programmable processor; and method steps can be performed by a programmable processor executing a program of instructions to perform functions of the described implementations by operating on input data and generating output. The described features can be implemented advantageously in one or more computer programs that are executable on a programmable system including at least one programmable processor coupled to receive data and instructions from, and to transmit data and instructions to, a data storage system, at least one input device, and at least one output device. A computer program is a set of instructions that can be used, directly or indirectly, in a computer to perform a certain activity or bring about a certain result. A computer program can be written in any form of programming language, including compiled or interpreted languages, and it can be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. 
     Suitable processors for the execution of a program of instructions include, by way of example, both general and special purpose microprocessors, and the sole processor or one of multiple processors of any kind of computer. Generally, a processor will receive instructions and data from a read-only memory or a random access memory or both. The essential elements of a computer are a processor for executing instructions and one or more memories for storing instructions and data. Generally, a computer will also include, or be operatively coupled to communicate with, one or more mass storage devices for storing data files; such devices include magnetic disks, such as internal hard disks and removable disks; magneto-optical disks; and optical disks. Storage devices suitable for tangibly embodying computer program instructions and data include all forms of non-volatile memory, including by way of example semiconductor memory devices, such as Erasable Programmable Read Only Memory (EPROM), Electrically Erasable Programmable Read Only Memory (EEPROM), and flash memory devices; magnetic disks such as internal hard disks and removable disks; magneto-optical disks; and CD-ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, ASICs (application-specific integrated circuits). 
     To provide for interaction with a user, the features can be implemented on a computer having a display device such as a CRT (cathode ray tube) or LCD (liquid crystal display) monitor for displaying information to the user and a keyboard and a pointing device such as a mouse or a trackball by which the user can provide input to the computer. 
     The features can be implemented in a computer system that includes a back-end component, such as a data server, or that includes a middleware component, such as an application server or an Internet server, or that includes a front-end component, such as a client computer having a graphical user interface or an Internet browser, or any combination of them. The components of the system can be connected by any form or medium of digital data communication such as a communication network. Examples of communication networks include, e.g., a LAN, a WAN, and the computers and networks forming the Internet. 
     The computer system can include clients and servers. A client and server are generally remote from each other and typically interact through a network, such as the described one. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other. 
     In addition, the logic flows depicted in the figures do not require the particular order shown, or sequential order, to achieve desirable results. In addition, other steps may be provided, or steps may be eliminated, from the described flows, and other components may be added to, or removed from, the described systems. Accordingly, other implementations are within the scope of the following claims. 
     A number of implementations of the present disclosure have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the present disclosure. Accordingly, other implementations are within the scope of the following claims.