Consistency maintenance in real-time collaborative graphics editing systems

ABSTRACT

Real-time collaborative graphics editing systems allow a group of users to view and edit the same graphics document at the same time from geographically dispersed sites connected by communication networks. Consistency maintenance in the face of concurrent accesses to shared objects is one of the core issues in the design of these types of systems. In this article, we propose an object-level multiversioning approach to consistency maintenance in real-time collaborative graphic editors. This approach is novel in achieving intention preservation and convergence, in preserving the work concurrently produced by multiple users in the face of conflict, and in minimizing the number of object versions for conflict resolution. Major technical contributions of this work include a formal specification of a unique combined effect for an arbitrary group of conflict and compatible operations, a distributed algorithm for incremental creation of multiple object versions, a consistent object identification scheme for multiple object versions, and a convergent layering scheme for overlapping objects. All algorithms and schemes presented in this article have been implemented in an Internet-based GRACE (graphics collaborative editing) system.

REFERENCES

• 1: Ronald M. Baecker, Readings in GroupWare and Computer-Supported Cooperative Work: Assisting Human-Human Collaboration, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1994
• 2: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 3: Krishna A. Bharat , Scott E. Hudson, Supporting distributed, concurrent, one-way constraints in user interface applications, Proceedings of the 8th annual ACM symposium on User interface and software technology, p.121-132, November 15-17, 1995, Pittsburgh, Pennsylvania, United States [doi>10.1145/215585.215708]
• 4: BIEL, V. 1991. Groupware grows up. MacUser, 207-211.
• 5: André Schiper , Kenneth Birman , Pat Stephenson, Lightweight causal and atomic group multicast, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.272-314, Aug. 1991 [doi>10.1145/128738.128742]
• 6: Jeffrey Dennis Campbell , Dirk E. Mahling, Consistency maintenance for real-time collaborative diagram development, 2000
• 7: CHEN, D. 2001. Consistency maintenance in collaborative graphics editing systems. PhD Thesis, School of Computing and Information Technology, Griffith University, Brisbane, Australia.
• 8: David Chen , Chengzheng Sun, A distributed algorithm for graphic objects replication in real-time group editors, Proceedings of the international ACM SIGGROUP conference on Supporting group work, p.121-130, November 14-17, 1999, Phoenix, Arizona, United States [doi>10.1145/320297.320310]
• 9: 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 [doi>10.1145/500286.500316]
• 10: CHESHIRE, S. 1996. Latency and the quest for interactivity. In White Paper commissioned by Volpe Welty Asset Management, L.L.C., for the Synchronous Person-to-Person Interactive Computing Environments Meeting.
• 11: Paul Dourish, Consistency guarantees: exploiting application semantics for consistency management in a collaboration toolkit, Proceedings of the 1996 ACM conference on Computer supported cooperative work, p.268-277, November 16-20, 1996, Boston, Massachusetts, United States [doi>10.1145/240080.240300]
• 12: W. Keith Edwards, Flexible conflict detection and management in collaborative applications, Proceedings of the 10th annual ACM symposium on User interface software and technology, p.139-148, October 14-17, 1997, Banff, Alberta, Canada [doi>10.1145/263407.263533]
• 13: Clarence A. Ellis , Simon J. Gibbs , Gail Rein, Groupware: some issues and experiences, Communications of the ACM, v.34 n.1, p.39-58, Jan. 1991 [doi>10.1145/99977.99987]
• 14: FIDGE, C. 1988. Timestamps in message-passing systems that preserve the partial ordering. In Proceedings of the Eleventh Australian Computer Science Conference, 56-66.
• 15: Saul Greenberg , David Marwood, Real time groupware as a distributed system: concurrency control and its effect on the interface, Proceedings of the 1994 ACM conference on Computer supported cooperative work, p.207-217, October 22-26, 1994, Chapel Hill, North Carolina, United States [doi>10.1145/192844.193011]
• 16: GREENBERG, S., ROSEMAN, R., AND WEBSTER, D. 1992. Issues and experiences designing and implementing two group drawing tools. In Proceedings of the the 25th Annual Hawaii International Conference on the System Science, 139-250.
• 17: Rushed Kanawati, LICRA: a replicated-data management algorithm for distributed synchronous groupware applications, Parallel Computing, v.22 n.13, p.1733-1746, February 28, 1997 [doi>10.1016/S0167-8191(96)00074-9]
• 18: KARSENTY, A. AND BEAUDOUIN-LAFON, M. 1993. An algorithm for distributed groupware applications. In Proceedings of the Thirteenth International Conference on Distributed Computing Systems, 195-202.
• 19: KARSENTY, A., TRONCHE, C., AND BEAUDOUIN-LAFON, M. 1993. Groupdesign: Shared editing in a heterogeneous environment. Usenix J. of Comput. Syst. 6, 2, 167-195.
• 20: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 21: Du Li , Richard R. Muntz, Coca: a framework for modeling and supporting flexible and adaptable synchronous collaborations, 2000
• 22: Richard G. McDaniel , Brad A. Myers, Getting more out of programming-by-demonstration, Proceedings of the SIGCHI conference on Human factors in computing systems: the CHI is the limit, p.442-449, May 15-20, 1999, Pittsburgh, Pennsylvania, United States [doi>10.1145/302979.303127]
• 23: MORAN, T., MCCALL, K., VAN MELLE, B., PEDERSEN, E., AND HALASZ, F. 1995. Some design principles for sharing in Tivoli, a whiteboard meeting-support tool. In Groupware for Real-time Drawings: A Designer's Guide, S. Greenberg, Ed., McGraw-Hill International (UK), 24-36.
• 24: R. E. Newman-Wolfe , M. L. Webb , M. Montes, Implicit locking in the ensemble concurrent object-oriented graphics editor, Proceedings of the 1992 ACM conference on Computer-supported cooperative work, p.265-272, November 01-04, 1992, Toronto, Ontario, Canada [doi>10.1145/143457.143524]
• 25: David A. Nichols , Pavel Curtis , Michael Dixon , John Lamping, High-latency, low-bandwidth windowing in the Jupiter collaboration system, Proceedings of the 8th annual ACM symposium on User interface and software technology, p.111-120, November 15-17, 1995, Pittsburgh, Pennsylvania, United States [doi>10.1145/215585.215706]
• 26: PENDERGAST, M. 1995. Groupgraphics: Prototype to product. In Groupware for Real-time Drawings: A Designer's Guide, S. Greenberg, Ed., McGraw-Hill International(UK), 209-227.
• 27: Michel Raynal , Mukesh Singhal, Logical Time: Capturing Causality in Distributed Systems, Computer, v.29 n.2, p.49-56, February 1996 [doi>10.1109/2.485846]
• 28: Chengzheng Sun, Undo any operation at any time in group editors, Proceedings of the 2000 ACM conference on Computer supported cooperative work, p.191-200, December 2000, Philadelphia, Pennsylvania, United States [doi>10.1145/358916.358990]
• 29: Chengzheng Sun, Optional and Responsive Fine-Grain Locking in Internet-Based Collaborative Systems, IEEE Transactions on Parallel and Distributed Systems, v.13 n.9, p.994-1008, September 2002 [doi>10.1109/TPDS.2002.1036072]
• 30: Chengzheng Sun , Clarence Ellis, Operational transformation in real-time group editors: issues, algorithms, and achievements, Proceedings of the 1998 ACM conference on Computer supported cooperative work, p.59-68, November 14-18, 1998, Seattle, Washington, United States [doi>10.1145/289444.289469]
• 31: Chengzheng Sun , Xiaohua Jia , Yanchun Zhang , Yun Yang , David Chen, Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems, ACM Transactions on Computer-Human Interaction (TOCHI), v.5 n.1, p.63-108, March 1998 [doi>10.1145/274444.274447]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: User interfaces

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human factors
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.3 Group and Organization Interfaces
          Subjects: Theory and models; Synchronous interaction

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Interaction techniques

General Terms:
Algorithms, Design, Human Factors

Keywords:
Collaborative graphics editors, GRACE, computer-supported cooperative work, consistence maintenance, convergence, groupware, intention preservation, multiversioning