A distributed algorithm for graphic objects replication in real-time group editors

ABSTRACT

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.

REFERENCES

• 1: 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
• 2: 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]
• 3: J. Fjermestad and S. R. Hiltz. An assessment of group support systems experiment research: Methodology and results. Journal of Management Information Systems, 15(3):7-149, 1999.
• 4: 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]
• 5: S. Greenberg, M. Roseman, and D. Webster. Issues and experiences designing and implementing two group drawing tools. In Prec. of the 25th Annual Hawaii International Conference on the System Sciences, pages 139-250, January 1992.
• 6: Jonathan Grudin, Why CSCW applications fail: problems in the design and evaluation of organization of organizational interfaces, Proceedings of the 1988 ACM conference on Computer-supported cooperative work, p.85-93, September 26-28, 1988, Portland, Oregon, United States [doi>10.1145/62266.62273]
• 7: Jörg M. Haake , Brian Wilson, Supporting collaborative writing of hyperdocuments in SEPIA, Proceedings of the 1992 ACM conference on Computer-supported cooperative work, p.138-146, November 01-04, 1992, Toronto, Ontario, Canada [doi>10.1145/143457.143472]
• 8: J.F. Nunamaker Jr., R. O. Briggs, D. D. Mittleman, and P. B. Balthazard. Lessons from a dozen years of group support systems research: A discussion of lab and field findings. Journal of Management information Systems, 13(3):163-207, 1996-1997.
• 9: 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]
• 10: A. Karsenty, C. Tronche, and M. Beaudouin-Lafon. Groupdesign: shared editing in a heterogeneous environment. Usenix Journal of Computing Systems, 6(2):167-195, 1993.
• 11: T. P. Moran, K. McCall, B. van Melle, E. Ronby Pedersen, and F.G.H. alasz. Some design principles of sharing in Tivoli, a whiteboard meeting support tool. In S. Greenberg, S. Hayne, and R. P~ada, editors, Groupware for Real-time Drawing: A Designer's guide, pages 24-36. McGraw-Hill, 1995.
• 12: 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]
• 13: M. O. Pendergast. GroupGraphics: prototype to product. In S. Greenberg, S. Hayne, and R. Rada, editors, Groupware for Real-time Drawing: A Designer's guide, pages 209-227. McGraw-Hill, 1995.
• 14: 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]
• 15: 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]
• 16: 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]
• 17: yon Biel. Groupware grows up. In MacUser, pages 207-211, June 1991.
• 18: B. Wilson. WSCRAWL 2.0: A shared whiteboard based on X- Windows. In S. Greenberg, S. Hayne, and R. Rada, editors, Groupware for Real-time Drawing: A Designer's guide, pages 129-141. McGraw-Hill, 1995.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Design, Reliability

Keywords:
collaborative editing, concurrency control, consistency maintenance, distributed computing, graphics editing