Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems

ABSTRACT

Real-time cooperative editing systems allow multiple users to view and edit the same text/graphic/image/multimedia document at the same time for multiple sites connected by communication networks. Consistency maintenance is one of the most significant challenges in designing and implementing real-time cooperative editing systems. In this article, a consistency model, with properties of convergence, causality preservation, and intention preservation, is proposed as a framework for consistency maintenance in real-time cooperative editing systems. Moreover, an integrated set of schemes and algorithms, which support the proposed consistency model, are devised and discussed in detail. In particular, we have contributed (1) a novel generic operation transformation control algorithm for achieving intention preservation in combination with schemes for achieving convergence and causality preservation and (2) a pair of reversible inclusion and exclusion transformation algorithms for stringwise operations for text editing. An Internet-based prototype system has been built to test the feasibility of the proposed schemes and algorithms

REFERENCES

• 1: Philip A. Bernstein , Vassco Hadzilacos , Nathan Goodman, Concurrency control and recovery in database systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 2: 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]
• 3: DOURISH, P. 1995. The parting of the ways: Divergence, data management and collaborative work. In Proceedings of the 4th European Conference on Computer-Supported Cooperative Work (Sept.). 215-230.
• 4: 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]
• 5: C. A. Ellis , S. J. Gibbs, Concurrency control in groupware systems, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.399-407, June 1989, Portland, Oregon, United States
• 6: 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]
• 7: FIDGE, C. 1988. Timestamps in message-passing systems that preserve the partial ordering. In Proceedings of the 11th Australian Computer Science Conference. 56-66.
• 8: 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]
• 9: Charles McLaughlin Hymes , Gary M. Olson, Unblocking brainstorming through the use of a simple group editor, Proceedings of the 1992 ACM conference on Computer-supported cooperative work, p.99-106, November 01-04, 1992, Toronto, Ontario, Canada [doi>10.1145/143457.143467]
• 10: KARSENTY, A. AND BEAUDOUIN-LAFON, M. 1993. An algorithm for distributed groupware applications. In Proceedings of the 13th International Conference on Distributed Computing Systems (May). 195-202.
• 11: KNISTER, M. AND PRAKASH, A. 1993. Issues in the design of a toolkit for supporting multiple group editors. J. Usenix Assoc. 6, 2, 135-166.
• 12: 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]
• 13: MCGUFFIN, L. AND OLSON, G. 1992. ShrEdit: A shared electronic workspace. CSMIL Tech. Rep. 45, The University of Michigan.
• 14: 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, 24-36. International (UK).
• 15: Sape J. Mullender , Guido van Rossum , Andrew S. Tanenbaum , Robbert van Renesse , Hans van Staveren, Amoeba: A Distributed Operating System for the 1990s, Computer, v.23 n.5, p.44-53, May 1990 [doi>10.1109/2.53354]
• 16: Judith S. Olson , Gary M. Olson , Marianne Storrøsten , Mark Carter, How a group-editor changes the character of a design meeting as well as its outcome, Proceedings of the 1992 ACM conference on Computer-supported cooperative work, p.91-98, November 01-04, 1992, Toronto, Ontario, Canada [doi>10.1145/143457.143466]
• 17: Atul Prakash , Michael J. Knister, A framework for undoing actions in collaborative systems, ACM Transactions on Computer-Human Interaction (TOCHI), v.1 n.4, p.295-330, Dec. 1994 [doi>10.1145/198425.198427]
• 18: 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]
• 19: Matthias Ressel , Doris Nitsche-Ruhland , Rul Gunzenhäuser, An integrating, transformation-oriented approach to concurrency control and undo in group editors, Proceedings of the 1996 ACM conference on Computer supported cooperative work, p.288-297, November 16-20, 1996, Boston, Massachusetts, United States [doi>10.1145/240080.240305]
• 20: Chengzheng Sun , P. Maheshwari, An efficient distributed single-phase protocol for total and causal ordering of group operations, Proceedings of the Third International Conference on High-Performance Computing (HiPC '96), p.295, December 19-22, 1996
• 21: SUN, C., CHEN, D., AND JIA, X. 1998. Reversible inclusion and exclusion transformation for string-wise operations in cooperative editing systems. In Proceedings of the 21st Australasian Computer Science Conference (Perth, Australia, Feb.) 441-452.
• 22: Chengzheng Sun , Xiahua Jia , Yun Yang , Yanchun Zhang, REDUCE: A Prototypical Cooperative Editing System, Proceedings of the Seventh International Conference on Human-Computer Interaction-Volume 1, p.89-92, August 24-29, 1997
• 23: Chengzheng Sun , Yanchun Zhang , Xiahua Jia , Yun Yang, A generic operation transformation scheme for consistency maintenance in real-time cooperative editing systems, Proceedings of the international ACM SIGGROUP conference on Supporting group work: the integration challenge, p.425-434, November 16-19, 1997, Phoenix, Arizona, United States [doi>10.1145/266838.267366]
• 24: SUN, C., YANG, Y., ZHANG, Y., AND CHEN, D. 1996a. A consistency model and supporting schemes for real-time cooperative editing systems. In Proceedings of the 19th Australian Computer Science Conference (Melbourne, Jan.). 582-591.
• 25: Chengzheng Sun , Yun Yang , Yanchun Zhang , David Chen, Distributed Concurrency Control in Real-time Cooperative Editing Systems, Proceedings of the Second Asian Computing Science Conference on Concurrency and Parallelism, Programming, Networking, and Security, p.84-95, December 02-05, 1996
• 26: VALDES, R. 1993. Text editors: Algorithms and architectures, not much theory, but a lot of practice. Dr. Dobb's J., 38-43.
• 27: Yanchun Zhang , Yun Yang, On operation synchronisation in cooperative editing environments, Proceedings of the IFIP TC8 Open Conference on Business Process Re-engineering: Information Systems Opportunities and Challenges, p.635-644, May 08-11, 1994

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.3 Group and Organization Interfaces
          Subjects: Synchronous interaction

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

  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

General Terms:
Algorithms, Design, Human Factors

Keywords:
REDUCE, causality preservation, computer-supported cooperative work, consistency maintenance, convergence, cooperative editing, groupware systems, intention preservation, operational transformation