Research alerts

IX.3 May 2002
Page: 11
Digital Citation

Consistency maintenance in real-time collaborative graphics editing systems


Authors:


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 effect—none 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 effect—the 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 G–G1 and G2–will 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) convergence—all replicas of the same document are identical after executing the same group of operations, and (2) intention preservation—the 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.

Authors

Chengzheng Sun and David Chen, Griffith University, Brisbane, Queensland 4111, Australia

Figures

F1Figure 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 XY. 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.

 

Post Comment


No Comments Found