A distributed algorithm for graphic objects replication in real-time group editors.
Real-time collaborative editing systems are groupware systems that allow multiple users to edit the same document at the same time from multiple sites. A specific type of collaborative editing system is the object-based collaborative graphics editing system. One of the major challenge in building such systems is to solve the concurrency control problems. This paper addresses the concurrency control problem of how to preserve the intentions of concurrently generated operations whose effects are conflicting. An object replication strategy is proposed to preserve the intentions of all operations. The effects of conflicting operations are applied to different replicas of the same object, while non-conflicting operations are applied to the same object. An object identification scheme is proposed to uniquely and consistently identify non-replicated and replicated objects. Lastly, an object replication algorithm is proposed to produce consistent replication effects at all sites.
Introduction
People collaborate to solve problems which would otherwise
be difficult or impossible for individuals. However,
group work can become unproductive and expensive [8]. For
these reasons, many researchers have been conducting studies
on how to effectively support group work [3]. Computer-Supported
Cooperative Work (CSCW) [2, 4] or computer-based
groupware systems assist groups of people working simultaneously
on a common task by providing an interface
To appear in Proc. of ACM International Conference on Supporting
Group Work, Nov 14-17, 1999, Phoenix, Arizona, USA
for a shared environment [2]. Groupware systems range from
asynchronous or non-real-time tools such as electronic mail,
to highly interactive synchronous systems such as Real-time
Collaborative Editing Systems (CESs) [1, 5, 13, 16, 14]. CESs
allow multiple users to edit the same document simultaneously

A particular type of CES are the collaborative graphics
editing systems. Collaborative graphics editing systems can
be further divided into two types, object-based and bitmap-
based. This paper examines the concurrency control problem
associated with object-based collaborative graphics editing
systems (OCESs).
In OCESs, objects such as line, rectangle, circle, etc., can
be created. Each object is represented by attributes such
as type, size, position, color, group, etc. Create operations
are used to create objects. After an object has been created,
operations can be applied to change attributes of that object.
For example, a move operation changes the position attribute
of the object it is applied to.
A concurrency control problem arises when concurrent operations
are generated from different sites to change the same
attribute of the same object. These operations are called
conflicting operations. For example, two concurrent move
operations are conflicting if both move the same object to
different positions. The execution of conflicting operations
may result in inconsistency of the shared document amongst
editing sites.
A. Existing work
The existing approaches to resolving the problem of conflict
in OCESs can be classified into two types: locking and
serialization. With the locking approach, a lock is placed on
the object being edited so no other user can edit that object
at the same time. Examples of such systems include: Aspects
[17], Ensemble [12], GroupDraw [5] and GroupGraph-
ics [13].
For locking to work, there has to be a coordinating process
which keeps track of which object(s) has been locked so
it can grant/deny permission for requests to locks. This process
may reside in a central server or in one of the editing
sites. The problem with this is that when an editing operation
is generated, it has to wait for the round trip time of a
message sent to the coordinating process and back, before it
can be executed (if it is allowed) at the local site. Due to this
unpredictable network delay, it may be a long time between
when an operation is generated and when it is executed at
the local site. This results in slow response time. Ensemble
and GroupDraw tried to overcome this problem. In Ensem-
ble, operations guaranteed not to cause conflict are applied
directly without waiting for approval. While in GroupDraw,
locally generated operations are executed right away and a
message is sent to the coordinating process. If the coordinating
process does not approve of the operation, then the effect
of that operation is undone.
With the serialization approach, operations can be executed
as soon as they are generated. When applying an
operation, that operation has to be compared for conflicting
with executed operations. When a conflict is detected, a
total (serial) order between operations is used to determine
which operation's effect will appear. Since the information
needed to determine the total ordering are attached to the
operations, a site can determine the total ordering without
extra communication with other sites. Examples of such systems
are: GroupDesign [10] and LICRA [9]. A key to this
approach is defining the conditions for when two operations
conflict. To define when operations conflict, their commutative
and masking relationships are first defined. Two operations
conflict if they neither commute nor mask with each
other.
Many CES researchers (including Grudin [6], Haake [7] and
advocate the philosophy that a CES should be
a natural extension of a single user editor. It should perform
like a single user editor with additional functions to support
real-time collaboration. A fundamental property of single
user editors is whenever an operation is generated, its effect is
persistent until another operation is generated to specifically
overwrite or undo that effect. Sun and co-authors [14, 15, 16]
proposed an intention preservation effect to preserve this fundamental
property in CESs. In CESs concurrent operations
are not generated to overwrite each other's effect, therefore,
concurrent operations should not change each other's effect.
Even though GroupDraw, GroupDesign and LICRA provide
quick response time, they do not guarantee intention preser-
vation. In these systems, the effect of an operation may be
changed by other concurrently generated operations.
B. GRACE
GRAphic Collaborative Editing system (GRACE) is the
name of the OCES being developed by our group. GRACE
has a distributed replicated architecture. Users of the system
may be located in geographically-separated sites. All
sites are connected via the Internet. Each site runs a copy
of the GRACE software and has a copy of the shared document
being edited. GRACE maintains the consistency of the
shared document at all sites.
GRACE does not use any form of locking for concurrency
control. When an operation is generated, it is executed immediately
at the local site. Then it is sent directly (without
going through a central coordinator) to all remote sites. The
response time of GRACE is as short as any single user ed-
itor. Also, the propagation delay is as fast as the network
would allow. There is no editing restriction placed on the
users. Like a singe user editor, a user can edit any part of
the shared document at any time.
In GRACE, the effects of operations are not serialized.
After an operation is generated, it will be executed at all sites.
The effect of an operation cannot be changed or overwritten
by other concurrently generated operations. The intentions
of all operations are preserved.
In the next section, some definitions and notations will be
introduced. Section III discusses how to preserve the intention
of operations by using the method of object replication.
This section is divided into five subsections. Section III-A
presents the replication effect for any combination of conflicting
and non-conflicting operations. Section III-B discusses
how to uniquely and consistently identify non-replicated and
replicated objects. In section III-C, some definitions are revised
to address the situation where operations may be generated
to edit replicated objects. Section III-D presents the
object replication algorithm to execute operations and provide
consistent replication effects. Section III-E uses an example
to illustrate how a replication effect is produced by
applying the described techniques. Lastly, section IV does
further comparison of GRACE with other approaches and
finishes with a conclusion.
II. Definitions and notations
GRACE adopts the consistency model of the REDUCE
system [15, 16]. There are three consistency properties in
this consistency model: causality preservation, convergence
and intention preservation. The definition of these properties
relies on the causal ordering and dependency relationship
amongst operations.
Definition 1: Causal ordering "!" and dependency relationship

ffl Given two operations Oa and Ob , generated at sites i
and j, then Oa ! Ob , iff: (1) and the generation
of Oa happened before the generation of Ob , or (2) i
and the execution of Oa at site j happened before the
generation of Ob , or (3) there exists an operation Ox ,
such that Oa ! Ox and Ox ! Ob .
ffl Given any two operations Oa and Ob . (1) Ob is said to
be dependent on Oa iff Oa ! Ob . (2) Oa and Ob are said
to be independent (or concurrent) iff neither Oa ! Ob ,
nor which is expressed as Oa jjOb .
A state vector is a logical vector clock. Each site maintains
a state vector. Whenever an operation is generated at a site,
it is time-stamped with the state vector value of that site. By
comparing the state vector values between two operations,
their dependency relationship can be determined [16].
This paper focus on one consistency property, intention
preservation. The intention of an operation and the intention
preservation property are described in Definitions 2 and 3.
Definition 2: Intention of an operation
Given an operation O, the intention of O is the execution
effect which can be achieved by applying O on the document
state from which O was generated.
Definition 3: Intention preservation property
For any operation O, the effects of executing O at all sites
are the same as the intention of O, and the effect of executing
O does not change the effect of independent operations.
The intention of a create operation will always be pre-
served, since create operations create new objects and will
not be affected by other operations. The discussion of intention
preservation applies to all simple modification operations
with the following properties:
ffl A simple modification operation targets one object and
its effect is limited to only that object;
ffl A simple modification operation changes only one attribute
of its target object.
Examples of such modification operations are: move, resize,
fill, etc.
Some notations are introduced to facilitate discussions.
Let C be any create operation. Let O be any simple modification
operation. Att:type(O) denotes the attribute O is
modifying, e.g. position, size or color. Att:val(O) denotes
the attribute value O is changing to, e.g. the new position
for the object. G denotes any graphic object in the shared
document. It is assumed all operations are executed in their
causal orders.
III. Object replication
In GRACE system, if all operations are generated causally
after each other, then simply executing the operations in accordance
to their causal ordering will preserve the intentions
of all operations. However, operations may be generated in-
dependently. The intention of an operation will be preserved
if its effect is not changed by independent operations. The
effect of an operation will not be changed by another independent
operation if they are editing different objects.
For operations editing the same object, they will not
change each other's effect if they edit different attributes. Independent
operations editing the same attribute of the same
object will not change each other's effect if they change the
same attribute into the same value. Only when independent
operations change the same attribute of the same object to
different values, intention violation occurs. Operations with
this type of relationship are called conflicting operations. For
all the operations mentioned in the rest of this section, they
will be assumed to have targeted the same object when they
were generated (unless stated otherwise).
By direct comparison between two operations, Oa and Ob ,
a conflict relationship between them can be determined if
Oa and Ob are independent, targeting the same object, and
changing the same attribute to different values. This type of
relationship is called conflict.
Definition 4: Conflict relation
Given two operations Oa and Ob targeting the same object,
Oa and Ob have the conflicting relation, denoted by
Oa\Omega
ffl Oa jjOb ,
Apparently, the effects of conflicting operations cannot co-exist
in the same object. If
Oa\Omega Ob , and both operations
target object G, then applying both operations to G will result
in intention violation. The only way to preserve the
intentions of both operations is to make two replica objects
from the original object, and then apply the two conflicting
operations to the two replicas separately. This method is
called the object replication. The resulting effect is that
no conflicting operations are applied to the same replica. To
preserve the intentions of Oa and Ob , replicas Ga and Gb
will be made from G, for the application of Oa and Ob re-
spectively. Since the replicas represent the original object, G
will be replaced by Ga and Gb . These two replicas are distinguished
by unique identifiers assigned during replication
so new operations can be generated to edit specific replicas
(how to determine object identifiers will be discussed later).
In contrast to the conflicting relationship, operations which
are not conflicting have a compatible relationship. If operations
Oa and Ob are not conflicting, then they are compatible,
denoted by Oa fiOb . The effects of compatible operations can
be applied to the same object without causing intention violation

Conflicting/compatible relationships between two or more
operations can be expressed by compatibility expressions in
which\Omega and fi are the operators and operations are the
operands. Brackets are used to indicate the scope of the
operators. For example, the expression of
means Oa and Ob conflict and Oc is compatible with both
Oa and Ob .
A. Replication effect
Based on the idea of making replica objects to preserve the
intentions of conflicting operations, this section will present a
specification detailing the replication effect which should be
produced. The replication effect of a simple modification operation
O depends on the conflicting/compatible relationship
between O and the operations applied to O's target object.
The notion of a compatible group (set) will be introduced.
A compatible group of an object G, denoted by CG(G), is
the set of simple modification operations applied to G. All
operations in the same compatible group must be
compatible.
Suppose operation O targets object G. Applying O to G is
equivalent to applying O to the compatible group of G. Let
Apply(O; CG(G)) denote the effect of applying O to CG(G).
This effect contains one or more compatible groups. If O
is compatible with all operations in CG(G), then applying
O to CG(G) results in Apply(O; fOg.
The result is a compatible group containing operations in
CG(G) and O. If a sub-group of CG(G), CF , is conflicting
with O, then applying O to CG(G) results in two compatible
groups, Apply(O; fOg.
The first group or replica contains all operations in CG(G).
The second group or replica contains O and the operations
in CG(G) which are compatible with O.
Example 1: There are three operations with the compatibility
expression of Oa fi
(Ob\Omega Oc ). All three operations
target object G where g.
(a) Application in the order of Oa ;
Ocg.
(b) Application in the order of
for replicas Gb and Gc respectively;
Oag.
Example 1(a) shows the replication effect of applying Oc to
a compatible group containing both conflicting and compatible
operations. The underlined compatible groups are the
final effects produced. Example 1(b) shows in order to produce
the same effect as Example 1(a), Oa needs to be applied
to both Gb and Gc which are replicas of G. From this, it is
observed that for any operation O, if the target object of O
has been replicated, then O needs to be applied to replicas
of G. The term candidate objects will be used to describe
the objects needed to be considered when applying an op-
eration. The candidate objects of operation O is either the
target object G of O, or the replicas made from G. O should
be applied to a set of compatible groups corresponding to the
set of candidate objects. This set is called the candidate set.
it follows that the replication effect of O is the compatible
groups produced by applying O to its candidate set.
Definition 5: Candidate set of O
For any operation O, the candidate set of O, denoted by
CS(O), is a set of candidate objects' compatible groups for
O.
Definition Replication effect
The replication effect of operation O is the compatible groups
produced by applying O to its candidate set, denoted by
Apply(O; CS(O)).
When a replica is made for Oc , it contains all compatible
operations applied to the original object, as shown in Example
1(a). To produce a consistent effect, Oa is applied to
all replicas which contain operations compatible with Oc , as
shown in Example 1(b). The result is that, for any operation
O, if operation Ox belongs to a compatible
group in CS(O), and Ox is compatible with O, then
there must be a compatible group in the replication
effect of O which contains both O and Ox . The final
effect of Example 1 is such that, Oa fi Ob is reflected in Gb
and Oa fi Oc is reflected in Gc .
Replication is required only when there are conflicting
operations. Conflicting operations are applied to different
replicas of the original object. Since all candidate objects
are replicated from the same original object, for any pair
of compatible groups CGx and CGy in CS(O), there are
operations Ox in CGx and Oy in CGy such that Ox conflicts
with Oy . When applying operation O to its candidate
set, if O can be incorporated into existing compatible groups
in CS(O), then no new replica should be made. This is
shown by the application of Oa in Example 1(b). Therefore,
the compatible groups in the replication effect of O,
is such that for
any pair of compatible groups CG i and CG j , where
must be an operation in CG i
which conflicts with an operation in CG j .
Compatibility expression Replication effect
1.
Oa\Omega
2.
Oa\Omega (Ob fi Oc) fOag, fOb ; Ocg
3. (Oa fi
4.
5.
6.
In summary, three conditions have been presented which
determine the replication effect. It can be shown that given a
group of operations, there is only one valid replication effect.
The table above shows the replication effects for six different
combinations of conflicting/compatible relationships. It can
be observed that, for expressions 1, 2, and 3, the resulting
compatible groups are the groups of operations on either side
of
the\Omega symbol. This is to be expected since conflict is the
only reason replicas are made. In expressions 4 and 5 there is
an operation, Oc , whose compatible scope spans across two
or more groups of operations with conflicting relationships.
If Oc is distributed to each group separated
by\Omega , then the
replication effect is the groups of operations separated
by\Omega .
Expression 6 is an extension of expression 4, where there are
two groups of conflicting operations separated by fi. Distribution
is done for each operation in one group with each
operation in the other group. For each compatibility expression
in the table, the replication effect presented is the only
valid replication effect for that expression.
B. Object identification
An object identifier is needed for each object to ensure that
for any operation O generated to edit object G, the same G
or replicas of G can be identified at all sites. When O was
generated, the target object field of O, denoted by Obj(O),
is assigned the object identifier of G. When O is received at
remote site i, Obj(O) is used to search for G at site i. If G
has been replicated at site i, then the replicas of G need to
be identified. For this scheme to work, three properties need
to be maintained:
1. uniqueness - every object at the same site need to have
an unique identifier.
2. traceability - by using the identifier of any object G, the
replicas made from G can be determined.
3. consistency - the same object at different sites have the
same identifier.
The object identifiers utilize the unique identification properties
of operations' identifiers. Each operation O can be
uniquely identified by an Operation Identifier (Oid), denoted
by Oid(O), composed of a pair (sid; lc), where sid is the identifier
of the site from which O was generated, and lc is the
sum of elements of the state vector associated with O.
For any object G, the Graphics-object Identifier (Gid) for
G, denoted by Gid(G), is composed of a set of operation
identifiers:
The identifier of an operation O is included in the
identifier of object G if either (1) O is the create
operation which created G, or (2) O has been applied
to G and O conflicts with an operation Ox .
Applying an operation O to an object G may change
the identifier of G. Therefore, object's identifier will be included
as part of the effect. The effect of applying O to G,
Apply(O; CG(G)), is one or more pairs of (CG, Gid). The
first component in the pair is the compatible group of the
resulting object. The second component is a set of operations
those identifiers are in the resulting object's identifier
set. If C is a create operation, then applying C will result in
(f
Example 2: There are four operations. Three compatibility
expressions are required to express their relationships:
Oa fi
Ob)\Omega Od and Oc fi Od 1 . All four
operations target object G. Initially and
created G. Assuming Oa ; has
already been applied, i.e. Apply(Oa ; f fCg). The
rest of the operations are applied in the order of:
(a) i. Apply(Ob ;
O c is required to make this example valid.
({Oa, Oc}, {C, Oc, Oa}) ({Oc, Od}, {C, Oc, Od})
({ }, {C})
Apply Oa
Apply
Apply Od
Apply Oc
Apply Od
Fig. 1. The execution of operations in Example 2(a)
(b) i. Apply(Od ;
The application of an operation O to its candidate objects
may change identifiers of the resulting candidate objects. After
applying O to CS(O), if O is in CG(G), then the identifier
of G may be changed as follows:
1. O is compatible with all operations in CS(O), then
Oid(G) is not added to Gid(G). This is shown by the
application of Ob in Example 2(a)(i).
2. O caused the replication of G from G 0 , then
fOid(O)g. This is shown by the application
of Oc in Example 2(a)(ii) where Oc caused fOa ; Ocg to
be replicated.
3. O did not cause replication, but O conflicted with some
operation in other candidate objects, then
CG(G)+fOid(O)g. This is shown by the application of
in Example 2(b)ii. Ob did not cause the replication
of fOa ; Obg, however, Ob conflicted with Od .
After applying O to CS(O), for any candidate object G 00
of O, if O is not in CG(G 00 ), then there must be an operation
Ox in CG(G 00 ) which conflicts with O. The identifier of G 00
is changed as follows:
1. G 00 is a replica made from G 0 , then Gid(G 00
)g. This is shown by the addition
of Oid(Ob) in Example 2(a)ii. After applying Oc
to CS(Oc ), Oid(Ob) is added into the identifier for
2. G 00 is not a new replica, then Gid(G 00
Oid(Ox ). This is shown by the addition of Oid(Oa ) in
Example 2(a)iii. After applying Od to CS(Od ), Oid(Oa)
is added into the identifier for fOa ; Obg.
If object G is created by operation C, then
fOid(C)g. A create operation only creates one object.
Therefore, a non-replicated object is uniquely identified by
the identifier of its create operation. A replica's identifier
will contain the identifier of the operation which created the
original object and the conflicting operations in its compatible
group. This is because conflicting operations are applied
to different replicas. Therefore, replicas are uniquely identified
by the identifiers of conflicting operations. For exam-
ple, after the execution of two operations, Oa and Ob , where
Oa\Omega Ob and
Gb are produced with
)g.
Any replica made from G would have Oid(C) in its identification
set. Suppose Oa is the cause of replication for Ga .
Any operation targeting Ga must be causally after Oa and
hence compatible with Oa . Therefore, any replica made from
Ga would contain Oid(C) and Oid(Oa ). For any three objects
G, G 0 and G 00 , where G 0 is a replica of G and G 00 is a
replica of G 0 , Gid(G) is a subset of Gid(G 0 ) and Gid(G 0 ) is
a subset of Gid(G 00 ), or Gid(G) ae Gid(G 0
ensures traceability.
If operation Oa is found to be conflicting with Ob at a site,
then Oa and Ob must be conflicting at all sites. For any combination
of conflicting/compatible relationships there is only
one valid replication effect. To achieve the same replication
effect at all sites, the same operations must be applied to the
same object. The identifier of an object is determined by the
operations applied to that object and their conflicting rela-
tionships. Since both of these are the same at all sites, so
object identifiers are consistent for objects at all sites.
C. Revised conflict definition
The definition for conflict in Definition 4 requires two operations
to target the same object or
definition is based on operations targeting non-replicated ob-
jects. After replication, two operations may conflict eventhough
their target object identifiers are not equal. Consider
the situation where
Oa\Omega Ob and
fOid(C)g. The execution effects of Oa and Ob are:
Operation Oc is generated
after the replication, i.e. Oc is dependent on Oa and
targets the replica made for Ob , i.e. Obj(Oc
Oid(Ob)g. Operation Od is independent of the
other three operations and Obj(Od fOid(C)g. Od is compatible
with Oa and Ob . Both Od and Oc should be applied to
However, it is possible that
Att:type(Od) and Att:val(Oc) 6= Att:val(Od ). Since Od and
Oc are independent, applying them to the same object would
result in intention violation. The desirable result is that conflict
between Oc and Od is detected and a replica is made for
each operation, as shown in Figure 2.
Two independent operations need to be compared
for conflict if one operation targets an object which
is a candidate object of the other. If the target object
of Oa is a candidate of the target object of Ob , then either
The direct conflict
relation definition is a revised original conflict definition
to include conflicting checking for operations those target objects
are equal or subset of each other.
({Ob, Od},{C, Ob, Od})
({Oa},{C, Oa})
({Oa, Od}, {C, Oa, Od}) ({Ob, Oc},{C, Ob, Oc})
({ }, {C})
({Ob, Oc},{C, Ob})
Apply Oa
Apply Oc
Apply
Apply Od
Fig. 2. Obj(Od ) ae Obj(O c ), however, their conflicting effect results
in replication.
Definition 7: Direct conflict relation
Given two operations Oa and Ob , Oa and Ob have the direct
conflicting relation, denoted by
Oa\Omega D Ob , iff:
ffl Oa jjOb ,
The effect scope of an operation is limited to its candidate
objects, i.e. an operation may only change its candidate ob-
jects. Operations which do not target the same object have
different effect scope. If Obj(Ob ) ae Obj(Oa ), then the scope
of Oa is only a subset of Ob 's scope. If these operations are
applied in different order, then inconsistency may occur. This
is illustrated in Example 3.
Example 3: There are four operations, Oa ;
Operations Oa ; Ob and Od are independent and target object
G where fCg. The compatibility
expression for these three operations are (Oa fi
Od)\Omega D Ob .
Oc is dependent on Oa and Ob , but is independent of Od
and Gid(Oc Obg. Oc is not directly conflicting with
Od . Assume Oa and Ob have been applied to produce the
effect of: (fOag; fC; Oag) and (fObg; fC; Obg). The following
illustrates two different orders of application:
(a) i. Apply(Oc ;
(b) i. Apply(Od ;
In Example 3, operations Oc and Od have different scopes,
CS(Oc) ae CS(Od ). If Oc is applied first then Od can be
applied to fOb ; Ocg since Od fi Oc . This will result in the
replication of fOc ; Odg, as shown in Example 3(a). If Od is
applied first then Od cannot be applied to fObg since
Od\Omega D
. Od is applied to fOag to produce fOa ; Odg. Oc cannot
be applied to fOa ; Odg because it is outside Oc 's scope, as
shown in Example 3(b). Inconsistent results are produced
from these two different orders of execution.
{(Ob),{C, Ob})
({Ob, Oc},{C, Ob, Oc})
({ }, {C})
({Oa, Od}, {C, Oa, Od})
({Oa},{C, Oa})
Apply Oa
Apply Oc
Apply Od
Apply
Fig. 3. The consistent result of Example 3 by detecting indirect
conflict of O c and Od .
Between the two effects in Example 3, effect (b) is the
more desirable effect. This is because Oc is generated to edit
a specific replica of G so its effect should only be limited to
that replica. The result of fOb ; Ocg and fOc ; Odg has the
impression that Oc is applied to more than one replica made
from G, since Obj(Od
Definition 8: Indirect conflict relation
Given two independent operations, Oa and Ob , Oa and Ob
have the indirect conflicting relation, denoted by
Oa\Omega I Ob ,
iff there is an operation Oc and object G such that:
Oc\Omega D Oa ,
The indirect conflict relationship is introduced to solve this
inconsistency problem and to produce the desirable effect.
According to the Definition 8, Od and Oc in Example 3 are
indirectly conflicting. If Od is applied after Oc , all operations
in fOb ; Ocg conflict with Od , so Od cannot be applied to it.
The effect of Example 3 with indirect conflict is as shown in

Figure

3.
Based on direct and indirect conflicts, the conflicting and
compatible relationships are redefined in Definition 9.
Definition 9: Compatibility relationship
Given two operations Oa and Ob , Oa and Ob are:
ffl conflicting, denoted by
Oa\Omega
Oa\Omega D Ob or
Oa\Omega I
ffl compatible, denoted by Oa fi Ob , iff Oa does not conflict
with Ob .
The object identification scheme relies on the definition
of conflict. Due to the changes made to the definition of
conflict, the object identification scheme also needs to be re-
vised. The identifier of a conflicting operation is added to the
object's identifier because conflict causes replication. How-
ever, with the new definition, indirect conflict does not cause
replication. Therefore, for any operation O and object
G where O in CG(G), Oid(O) needs to be in Gid(G) iff
O directly conflicts with an operation Ox .
D. Object replication algorithm
This section presents an algorithm to apply and preserve
the intention of a newly arrived simple modification opera-
tion, Onew . The first step in applying Onew is to determine
Onew 's candidate set. A candidate object of Onew is either:
1. the object G which Onew is targeting, where
2. a replica G 0 made from G, where Obj(Onew
In summary, for any object G, CG(G) is in CS(Onew ) iff:
Obj(Onew
Compatible groups in the candidate set can be classified
into three types. For any compatible group CG i 2
CS(Onew
1. if every operation in CG i conflicts with Onew , then CG i
is said to be fully conflicting with Onew , denoted by
i\Omega Onew .
2. if no operation in CG i conflicts with Onew , then CG i
is said to be fully compatible with Onew , denoted by
3. if CG i contains operations conflicting and compatible
with Onew , then CG i is said to be partially conflicting
with Onew .
All CG i s which are fully conflicting with Onew are put into
a conflicting object set, CF . All CG i s which are fully compatible
with Onew are put into a compatible object set, CP .
Any CG i which is partially conflicting with Onew is partitioned
into two subsets: CG 0
which contains all operations
in CG i which are compatible with Onew and CG 00
which contains
all operations in CG i which are conflicting with Onew .
All CG 00
are added to CF . All CG 0
are put into a replicated
compatible set, RCP . This is shown in step 2 of Algorithm 1.
If operation Ox in any CG i is compatible with Onew
then there has to be a compatible group in replication effect
of Onew which contains both Ox and Onew . This can be
achieved as follows:
ffl for any CG j in CP , add Onew to CG j , and
ffl for any CGk in RCP , add Onew to CGk , where each
CGk correspond to a new replica.
However, with this method of applying Onew , some resulting
compatible groups may not contain any operation which
is conflicting with other resulting compatible groups. This
problem is illustrated in Examples 4 and 5.
Example 4: There are four operations with the compatibility
(Oa\Omega D
Ob\Omega D Onew ) fi Oc . All four operations
are independent and target the same object. Assuming
Oa , Ob and Oc have been applied when Onew arrives. The
candidate set for Onew is ffOa ; Ocg; fOb ; Ocgg.
1. Making replica of fOa ; Ocg produces fOa ; Ocg and
Ocg.
2. Making replica of fOb ; Ocg produces fOb ; Ocg and
Ocg.
2 a compatible group of f g is also fully compatible with Onew
Example 5: There are four operations with the compatibility
(Oa\Omega D (Ob fi Onew )) fi Oc . All four operations
are independent and target the same object. Assuming
Oa , Ob and Oc have been applied when Onew arrives. The
candidate set for Onew is ffOa ; Ocg; fOb ; Ocgg.
1. Making replica of fOa ; Ocg produces fOa ; Ocg and
Ocg.
2. Adding Onew to fOb ; Ocg produces fOb ; Oc ; Onewg.
In Example 4, Onew is partially conflicting with all compatible
groups in CS(Onew ). Applying Onew has produced
two compatible groups which are identical. In Example 5,
Onew is fully compatible with a compatible group and partially
conflicting with the other group in CS(Onew ). Applying
Onew has produced two compatible groups in which one is
the subset of the other. In both examples, the results contain
two compatible groups that are compatible with each other.
Only one compatible group is needed to accommodate the
effects of operations in both groups.
This problem of producing unnecessary replicas can be
avoided by eliminating the unnecessary compatible groups
in RCP . If any CGk in RCP is equal or a subset of any CG j
in CP or RCP , then all operations in CGk are compatible
with all operations in CG j . Therefore, the replica with CGk
does not need to be made, and CGk should be removed from
RCP . This is shown in step 3 of Algorithm 1.
There is a special situation where all compatible groups in
the candidate set are fully conflicting with Onew . When this
happens CP and RCP will both be empty sets. Since no operation
is compatible with Onew , a compatible group/replica
containing fOnewg should be constructed.
Algorithm 1: Object Replication Algorithm
Onew : the new modification operation to be executed.
conflicting object set, initially f g.
object set, initially f g.
replicated compatible set, initially f g.
1. Get candidate set,
2. For each CG i in CS do
if
Onew\Omega CG i then CF := CF
else if Onew fi CG i then
else split CG i into CG 0
i and CG 00
i such that:
Onew fi CG 0
Onew\Omega CG 00
3. Merge compatible subsets or equal sets:
for any pair CG i and CG j in CP or RCP do
if CG i ' CG j then remove CG i .
4. If then
make CGn+1 := fOnewg;
for each CG i in CP do
for each CG i in RCP do
Previously executed operations are kept for conflict check-
ing. These operations are kept in a list called History Buffer
(HB). To avoid the history buffer to become infinitely long,
a garbage collection process is carried out periodically to remove
any operation Ox where all operations independent of
Ox have been applied. Each object G maintains a list of
pointers which point to operations in the history buffer which
have been applied to G. HB(G) denotes the list of operations
applied to G.
Replicas are made from an existing object. Every CG i
in RCP comes from an candidate object, which is the base
object from which replica for CG i will be made. If
candidate object can be the base object
from which fOnewg will be created. For a compatible group
CG i and base object G, replica object is made as follows:
1. make an exact copy of G, call it G
2. undo operations in HB(G 0 ) in the reverse execution
order until all operations in HB(G 0 ) are members in
3. redo any operations in CG i which have been undone
from HB(G 0 ) in step 2.
During the undo process, the operation identifiers for operations
not in CG i are also removed from Gid(G 0 ).
The steps needed to assign object identifiers have been deliberately
separated from the object replication algorithm to
avoid introducing extra complexity into the algorithm. After
Onew has been executed via the object replication algorithm,
if the resulting CF set is f g, then Onew does not conflict with
any operation. Otherwise, the following needs to be done:
1. Construct a set DC which contains Onew and any operation
directly conflicting with Onew .
2. For any operation Ox in DC and object G where Ox in
Compatible groups in CF contain all operations directly or
indirectly conflicting with Onew . So the search for operations
directly conflicting with Onew can be limited to CF . The operations
which are directly conflicting with Onew are limited
to the candidate objects of Onew (the candidate objects now
include the replicas resulted from the application of Onew ).
So the search for the objects whose identifiers need to be
changed can be limited to the candidate objects for Onew .
Various optimizations are possible, but beyond the scope of
this paper.
E. An integrated example
In this section, an example will be presented to illustrate
the object replication algorithm, object identification scheme
and the revised compatibility relationship.
There are six operations, Oa ; Of . Four
operations are independent with each other and with the
compatibility expression: ((Oa fi
Od)\Omega D Ob) fi Oc ). All
four operations target object G created by operation C, i.e.
fOid(C)g. Oe and Of are generated causally after Oa and Ob .
Each Oe and Of targets a replica,
and Obj(Of Oid(Ob)g. Both operations are compatible
with Oc , but conflict with Od ,
Oe\Omega D Od and
Of\Omega I Od .
Initially, g. Two different orders of execution will
be illustrated.
Execution order 1:
After merging:
Execution order 2:
After merging:
To apply an operation, its candidate set is first determined
by using object identifiers. Then those compatible groups are
classified into CF;CP and RCP sets. By using these sets, the
replication effects are produced. For both execution orders,
merging of compatible groups are required to avoid producing
unnecessary replica. This is shown during the execution of
Oe in Execution 1 and Od during Execution 2.
The final results for both execution orders are consistent
and satisfy the conditions for replication effect. This example
is used to illustrate various techniques used to produce
the replication effect. For such a complex combination of
conflicting/compatible operations to occur during editing is
possible but unlikely.
IV. Discussion and conclusion
This paper investigated the problem of operational conflict
in object-based collaborative graphics editing systems.
First our paper described the locking and serialization approaches
to the problem of conflicting operations. Both approaches
have the problem of not preserving the intentions of
all operations. Finally, our paper presented a new replication
approach that preserves all operation intentions.
The locking approach to preventing conflict from occurring
suffers the serious problem of slow response times over wide
area networks. The optimistic operation execution approach
solves this problem by executing operations locally as soon
as they are generated, before sending them to remote sites.
However, with this approach, conflicting operations may be
generated. The existing approach of serializing the conflicting
operations results in intention violation where the execution
of an operation changes the effect of a concurrent operation.
This may lead to confusion. If user 1 generates Oa to move
object G to X and at the same time user 2 generates Ob to
move G to Y and the system decides Ob has a higher priority
(or a serialization order). The end result at all sites will be
consistent, i.e. G will be at Y , but the whole process can be
confusing to the users. Both users will see their operations
executed at the local site, so they will assume the same execution
effect at all sites. However, the effect of Oa will never
appear to user 2. User 1 saw the execution of Oa followed
by Ob , so he/she may think that user 2 saw G at X and still
decided that Y would be a better location. Another possible
source of confusion is that the users may communicate and
find out that user 2 did not see Oa , so they may think there
are some network problems which have led to the mysterious
disappearance of Oa .
The replication approach solves this problem. By applying
Oa and Ob to replicas of G, user 1 will see that user 2 wants G
at Y , and user 2 will see that user 1 wants G at X. This provides
visual display of what each user wants and conveys the
intention of each user. By using this information, users can
compare the solution and decide on the best result. Instead
of the system deciding for the user based on unrelated information
(e.g. the serialization order), the replication approach
lets the users decide on the outcome by providing them with
the required information.
Tivoli [11] is a collaborative editing system that uses object
replication to resolve conflict. However, at the user
level, Tivoli behaves like a bit-map based informal scribbling
medium (i.e. a whiteboard). Hence, the operations
supported by Tivoli are quite different from the ones supported
by object-based graphics editing systems. At the implementation
level, all Tivoli objects are immutable, which
means they can only be created and deleted but not modi-
fied. To apply an operation to an object, that object is first
deleted, then an object with the new attribute values is cre-
ated. When two operations are concurrently applied to the
same object, that object will be deleted, and two new objects
will be created (one for each operation). This method does
not distinguish whether these two operations are compatible
or conflicting. Therefore, it does not allow compatible operations
to be applied to the same object (e.g. concurrent move
and fill operations cannot be applied to the same object).
This causes unnecessary replicas to be made.
With the replication effect of the GRACE system, conflicting
operations are applied to different replicas while compatible
operations targeting the same object are applied to the
same object. A replica is made only for conflicting opera-
tions, so no unnecessary replica is created. An object identification
scheme is introduced to uniquely and consistently
identify non-replicated and replicated objects. The property
of object identifier allows the determination of which replicas
an object is replicated into. This property is utilized by the
object replication algorithm to produce the replication effect.
Replication alone is not a complete solution for resolving
conflicts. Other supporting features should be integrated
into the system to work in conjunction with object replica-
tion. A group awareness mechanism should be devised to
help users preventing conflict. A conflict awareness mechanism
is needed to inform users that a conflict has occurred.
It should provide users with the information about the conflicting
operations, the replicas, and the users who caused the
conflict.
The simple modification operations are the most commonly
used operations in object-based graphics editing sys-
tems. It is expected that some operations, can be implemented
as simple modification operations if additional object
attributes are introduced. For example, a group attribute
can be introduced to indicate the group an object belongs
to. This can be used to implement grouping and ungrouping
operations. Work is underway to investigate several other
types of operations in order to maximize our finding or to be
used in more advanced object-based graphics editing systems.

Acknowledgments

The work reported in this paper has been partially supported
by an ARC (Australia Research Council) Small Grant
and a Large Grant (A49601841).



--R

Concurrency control in groupware sys- tems
Groupware: some issues and experiences.
An assessment of group support systems experiment research: Methodology and results.
Real time groupware as a distributed system: concurrency control and its effect on the inter- face
Issues and experiences designing and implementing two group drawing tools.
Why CSCW applications fail: problems in the design and evaluation of organizational interfaces.
Supporting collaborative writing of hyperdocuments in SEPIA.

LICRA: A replicated-data management algorithm for distributed synchronous groupware application
Groupdesign: shared editing in a heterogeneous environment.
Some design principles of sharing in Tivoli
Implicit locking in the Ensemble concurrent object-oriented graphics editor
GroupGraphics: prototype to product.
Operational transformation in real-time group editors: Issues
A generic operation transformation scheme for consistency maintenance in real-time cooperative editing systems
Achieiving convergence
Groupware grows up.
WSCRAWL 2.0: A shared whiteboard based on X- Windows
--TR
Why CSCW applications fail: problems in the design and evaluation of organization of organizational interfaces
Concurrency control in groupware systems
Groupware: some issues and experiences
Supporting collaborative writing of hyperdocuments in SEPIA
Implicit locking in the ensemble concurrent object-oriented graphics editor
Real time groupware as a distributed system
LICRA
A generic operation transformation scheme for consistency maintenance in real-time cooperative editing systems
Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems
Operational transformation in real-time group editors

--CTR
David Chen , Chengzheng Sun, Optional and responsive locking in collaborative graphics editing systems, ACM SIGGROUP Bulletin, v.20 n.3, p.17-20, December 1999
Liyin Xue , Mehmet Orgun , Kang Zhang, A multi-versioning algorithm for intention preservation in distributed real-time group editors, Proceedings of the twenty-sixth Australasian conference on Computer science: research and practice in information technology, p.19-28, February 01, 2003, Adelaide, Australia
Du Li , Limin Zhou , Richard Muntz, The gods must be crazy: a matter of time in collaborative systems, ACM SIGGROUP Bulletin, v.20 n.3, p.21-25, December 1999
Mihail Ionescu , Ivan Marsic, Tree-Based Concurrency Control inDistributed Groupware, Computer Supported Cooperative Work, v.12 n.3, p.329-350,
David Chen , Chengzheng Sun, Undoing any operation in collaborative graphics editing systems, Proceedings of the 2001 International ACM SIGGROUP Conference on Supporting Group Work, September 30-October 03, 2001, Boulder, Colorado, USA
Operation Propagation in Real-Time Group Editors, IEEE MultiMedia, v.7 n.4, p.55-61, October 2000
Chengzheng Sun , David Chen, Consistency maintenance in real-time collaborative graphics editing systems, ACM Transactions on Computer-Human Interaction (TOCHI), v.9 n.1, p.1-41, March 2002
Nicolas Bouillot , Eric Gressier-Soudan, Consistency models for distributed interactive multimedia applications, ACM SIGOPS Operating Systems Review, v.38 n.4, p.20-32, October 2004
Sandy Citro , Jim McGovern , Caspar Ryan, Conflict management for real-time collaborative editing in mobile replicated architectures, Proceedings of the thirtieth Australasian conference on Computer science, p.115-124, January 30-February 02, 2007, Ballarat, Victoria, Australia
distributed computing;concurrency control;collaborative editing;graphics editing;consistency maintenance