Real-time collaborative graphics editing systems allow a group of users to view and edit the same graphics document concurrently from geographically dispersed sites connected by communication networks. The systems can be used in collaborative computer-aided design (CAD) and computer-aided software engineering (CASE) systems, electronic conferencing/meeting, and collaborative virtual environments.
To effectively support collaborative work, a collaborative editor should be able to respond to a user's local actions as quickly as possible. To achieve high responsiveness in the Internet environment with a long communication latency, shared graphics objects must be replicated at all collaborating sites so that local operations can be immediately performed and then reflected in the local interface. One of the core issues in the design of these types of systems is how to maintain consistency in the multiple replicas of shared documents, given concurrent and potentially conflicting operations. This paper addresses that issue.
Conflict occurs when multiple users are concurrently editing the same object and changing an object attribute to different values. For example, suppose that two users concurrently try to move an object G to different positions. Accommodating their conflicting effects with the same object is impossible. How can we resolve this kind of conflict under the condition that system consistency is maintained?
One possible strategy is to resolve the conflict by achieving a null effectnone of the conflict operations has any final effect on the target object. In this example, the position of G will remain unchanged after the two conflicting operations are executed. Another strategy is to resolve the conflict by achieving a single-operation effectthe effect of only one operation will be retained in the face of conflict. In this example, object G will be moved to the position intended by one of the two users. The problem with these approaches is that whenever a conflict exists, the work concurrently done by multiple users will be completely or partly destroyed, and users are provided with no or incomplete information about what other users intended to do, thus decreasing the users' ability to understand the nature of their conflict and to adjust their actions accordingly.
A new conflict resolution strategy proposed in this paper is to achieve an all-operations effect by means of multiple versioning: two versions of GG1 and G2will be created, with the two conflicting operations being applied to G1 and G2, respectively. In this way, the effects of both operations are accommodated in two separate versions, as illustrated in Figure 1. The multiple-version approach ensures that the work produced by all users is always retained regardless of whether a conflict exists. In case of conflict, users are given a complete picture about what other users intended to do, so they could better assess the situation and react accordingly. In keeping with maintaining consistency, this approach maintains the following two consistency properties: (1) convergenceall replicas of the same document are identical after executing the same group of operations, and (2) intention preservationthe effect of an operation on a remote replica is the same as its effect on the local replica.
In a highly concurrent collaborative editing environment, a group of operations may have rather complex conflict relationships. A major technical challenge in supporting the multiple-version approach is how to determine the correct combined effect, one that is consistent at all sites and that minimizes the number of object versions for conflict resolution, for an arbitrary group of operations. This paper includes detailed discussions on the conflict and compatible relationships among concurrent operations, the unique combined effect derived from the inherent conflict and compatible relationships among operations, a distributed algorithm for incremental creation of multiple object versions for conflict resolution, a consistent object identification scheme for multiple object versions, and a consistent layering scheme for overlapping objects. Moreover, the multiple-version technique is compared with the operational transformation technique (invented in the text editing domain) to show their complementary roles in maintaining consistency in collaborative editing systems. Finally, the implementation of multiple-version algorithms in the Internet-based GRACE (GRAphics Collaborative Editing) system is also discussed in this paper.
Chengzheng Sun and David Chen, Griffith University, Brisbane, Queensland 4111, Australia
Figure 1. A scenario for illustrating the
multiple-version conflict resolution approach. The vertical lines
represent the activities performed by corresponding users, and
arrows represent the propagation of operations. The document
states observable from each user's interface at different stages
are illustrated by rectangular boxes with rounded corners.
Initially, both sites have the same object G, as shown in
boxes 1.0 and 2.0. Then, two concurrent operations are generated:
O1 = Move(G, X) and
O2 = Move(G, Y), where X
≠Y. At the site of User 1, G is moved to
position X after executing O1, resulting
in the document state shown in box 1.1. Next,
O2 arrives and is found to be conflicting with
O1, so a new version of G is created and
O2 is applied on it, as shown in box 1.2. A
similar process occurs at the site of User 2.
©2002 ACM 1072-5220/02/0300 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2002 ACM, Inc.