Undo as concurrent inverse in group editors

ABSTRACT

As an important mechanism for error recovery and exploration of alternatives in interactive and collaborative applications, an undo facility should have the capability of undoing any operation at any time. However, supporting undo in collaborative applications is technically challenging and none of the existing group undo solutions is able to offer such a capability. In this article, we contribute an undo solution with such a capability for group text editors. The basic idea is to interpret an undo command as a concurrent inverse operation by means of operational transformation. To cope with the high complexity of group undo, a generic undo framework has been adopted to separate undo policy from the undo mechanism and to separate transformation control algorithms from transformation functions. The proposed undo solution consists of a generic transformation control algorithm that is capable of generating, transforming, and representing valid inverse operations in any context, and a set of transformation functions that are capable of preserving undo-related transformation conditions and properties. Formal proofs are provided to show the correctness of the undo transformation control algorithm in achieving the required undo effect, undo property, and consistency properties. Solutions to the known undo puzzles are provided to show soundness of the transformation functions. A Web-based group text editor REDUCE (REal-time Distributed Unconstrained Cooperative Editing) has been implemented to demonstrate the feasibility and usability of the proposed undo and other technical solutions. The proposed undo solution is generally applicable to collaborative applications that support concurrent insertion and deletion on shared documents consisting of one or multiple dimensions of linearly ordered data objects with positional references.

REFERENCES

• 1: Gregory D. Abowd , Alan J. Dix, Giving undo attention, Interacting with Computers, v.4 n.3, p.317-342, Dec. 1992 [doi>10.1016/0953-5438(92)90021-7]
• 2: Thomas Berlage, A selective undo mechanism for graphical user interfaces based on command objects, ACM Transactions on Computer-Human Interaction (TOCHI), v.1 n.3, p.269-294, Sept. 1994 [doi>10.1145/196699.196721]
• 3: 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]
• 4: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• 5: 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]
• 6: Choudhary, R. and Dewan, P. 1995. A general multi-user undo/redo model. In Proceedings of European Conference on Computer Supported Work. 231--246.
• 7: Aguido Horatio Davis , Chengzheng Sun , Junwei Lu, Generalizing operational transformation to the standard general markup language, Proceedings of the 2002 ACM conference on Computer supported cooperative work, November 16-20, 2002, New Orleans, Louisiana, USA [doi>10.1145/587078.587088]
• 8: Prasun Dewan , Rajiv Choudhary , Honghai Shen, An editing-based characterization of the design space of collaborative applications, Journal of Organizational Computing, v.4 n.3, p.219-239, 1994
• 9: Dix, A., Mancini, R., and Levialdi, S. 1997. The cube-extending systems for undo. In Proceedings of DSVIS'97. Eurographics (Granada, Spain). 473--495.
• 10: 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
• 11: 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]
• 12: Fidge, C. 1988. Timestamps in message-passing systems that preserve the partial ordering. In Proceedings of the 11th Australian Computer Science Conference. 56--66.
• 13: Robert F. Gordon , George B. Leeman, Jr. , Clayton H. Lewis, Concepts and implications of undo for interactive recovery, Proceedings of the 1985 ACM annual conference on The range of computing : mid-80's perspective: mid-80's perspective, p.150-157, October 1985, Denver, Colorado, United States [doi>10.1145/320435.320483]
• 14: 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.
• 15: 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]
• 16: Donald A. Norman , Stephen W. Draper, User Centered System Design; New Perspectives on Human-Computer Interaction, Lawrence Erlbaum Associates, Inc., Mahwah, NJ, 1986
• 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: Matthias Ressel , Rul Gunzenhäuser, Reducing the problems of group undo, Proceedings of the international ACM SIGGROUP conference on Supporting group work, p.131-139, November 14-17, 1999, Phoenix, Arizona, United States [doi>10.1145/320297.320312]
• 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: Haifeng Shen , Chengzheng Sun, Flexible notification for collaborative systems, Proceedings of the 2002 ACM conference on Computer supported cooperative work, November 16-20, 2002, New Orleans, Louisiana, USA [doi>10.1145/587078.587090]
• 21: Haifeng Shen , Chengzheng Sun, A Log Compression Algorithm for Operation-based Version Control Systems, Proceedings of the 26th International Computer Software and Applications Conference on Prolonging Software Life: Development and Redevelopment, p.867-872, August 26-19, 2002
• 22: Shneiderman, B. 1982. The future of interactive systems and the emergence of direct manipulation. Behav. Inform. Techn. 1, 3, 237--256.
• 23: 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]
• 24: 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]
• 25: Chengzheng Sun , David Chen, Consistency maintenance in real-time collaborative graphics editing systems, ACM Transactions on Computer-Human Interaction (TOCHI), v.9 n.1, p.1-41, March 2002 [doi>10.1145/505151.505152]
• 26: 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]
• 27: 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]
• 28: 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
• 29: Harold Thimbleby, User interface design, ACM Press, New York, NY, 1990
• 30: Y. Yang, A new conceptual model for interactive user recovery and command reuse facilities, Proceedings of the SIGCHI conference on Human factors in computing systems, p.165-170, May 15-19, 1988, Washington, D.C., United States [doi>10.1145/57167.57195]

INDEX TERMS

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

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.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Theory and methods

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.1 Document and Text Editing

General Terms:
Algorithms, Design, Human Factors, Theory, Verification

Keywords:
Group undo, REDUCE, collaborative applications, computer-supported cooperative work, concurrency control, consistence maintenance, distributed systems, operational transformation