Chengzheng Sun
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.
- Abowd, G. and Dix, A. 1992. Giving undo attention. Interact. Comput. 4, 3, 317--342. Google Scholar
- Berlage, T. 1994. A selective undo mechanism for graphical user interfaces based on comand objects. ACM Trans. Comput. Hum. Interact. 1, 3 (Sept.), 269--294. Google Scholar
- Birman, K., Schiper, A., and Stephenson, P. 1991. Lightweight causal and atomic group multicast. ACM Trans. Comp. Sys. 9, 3 (Aug.), 272--314. Google Scholar
- Chandy, K. M. and Lamport, L. 1985. Distributed snapshots: determining global states of distributed systems. ACM Trans. Comp. Sys. 3, 1 (Feb.), 63--73. Google Scholar
- Chen, D. and Sun, C. 2001. Undoing any operation in collaborative graphics editing systems. In Proceedings of the ACM Conference on Supporting Group Work. 197--206. Google Scholar
- Choudhary, R. and Dewan, P. 1995. A general multi-user undo/redo model. In Proceedings of European Conference on Computer Supported Work. 231--246. Google Scholar
- Davis, A., Sun, C., and Lu, J. 2002. Generalizing operational transformation to the standard general markup language. In Proceedings of the ACM Conference on Computer Supported Cooperative Work, 58--67. Google Scholar
- Dewan, P., Choudhary, R., and Shen, H. 1994. An editing-based characterization of the design space of collaborative applications. J. Organizat. Comput. 4, 3, 219--240. Google Scholar
- Dix, A., Mancini, R., and Levialdi, S. 1997. The cube-extending systems for undo. In Proceedings of DSVIS'97. Eurographics (Granada, Spain). 473--495.Google Scholar
- Ellis, C. A. and Gibbs, S. J. 1989. Concurrency control in groupware systems. In Proceedings of the ACM SIGMOD Conference on Management of Data. ACM Press, New York, NY, 399--407. Google Scholar
- Ellis, C. A., Gibbs, S. J., and Rein, G. L. 1991. Groupware: some issues and experiences. Commun. ACM 34, 1 (Jan.), 39--58. Google Scholar
- Fidge, C. 1988. Timestamps in message-passing systems that preserve the partial ordering. In Proceedings of the 11th Australian Computer Science Conference. 56--66.Google Scholar
- Gordon, R. Leeman, G., and Lewis, G. 1985. Concepts and implications of undo for interactive recovery. In Proceedings of the ACM Annual Conference. 150--157. Google Scholar
- 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.Google Scholar
- Lamport, L. 1978. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7, 558--565. Google Scholar
- Norman, D. A. and Draper, S. W. 1986. User Centered System Design: New Perspectives on Human-Computer Interaction. Lawrence Erlbaum Associates, Hillsdale, NJ. Google Scholar
- Prakash, A. and Knister, M. 1994. A framework for undoing actions in collaborative systems. ACM Trans. Comput. Hum. Interact. 4, 1 (Dec.), 295--330. Google Scholar
- Ressel, M. and Gunzenhäuser, R. 1999. Reducing the problems of group undo. In Proceedings of the ACM Conference on Supporting Group Work. 131--139. Google Scholar
- Ressel, M., Nitsche-Ruhland, D., and Gunzenhäuser, R. 1996. An integrating, transformation-oriented approach to concurrency control and undo in group editors. In Proceedings of the ACM Conference on Computer Supported Cooperative Work. 288--297. Google Scholar
- Shen, H. and Sun, C. 2002a. Flexible notification in collaborative systems. In Proceedings of the ACM Conference on Computer Supported Cooperative Work, 77--86. Google Scholar
- Shen, H. and Sun, C. 2002b. A log compression algorithm for operation-based version control systems. In Proceedings of the 26th IEEE Annual International Computer Software and Application Conference (COMPSAC 2002), Oxford, England. IEEE Computer Society Press, Los Alamitos, Calif., 867--872. Google Scholar
- Shneiderman, B. 1982. The future of interactive systems and the emergence of direct manipulation. Behav. Inform. Techn. 1, 3, 237--256.Google Scholar
- Sun, C. 2000. Undo any operation at any time in group editors. In Proceedings of the ACM Conference on Computer Supported Cooperative Work. 191--200. Google Scholar
- Sun, C. 2002. Optional and responsive fine-grain locking in Internet-based collaborative systems. IEEE Trans. Parallel Distrib. Syst. 13, 9 (Sept.), 994--1008. Google Scholar
- Sun, C. and Chen, D. 2002. Consistency maintenance in real-time collaborative graphics editing systems. ACM Trans. Comput.-Hum. Interact. 9, 1 (March), 1--41. Google Scholar
- Sun, C. and Ellis, C. A. 1998. Operational transformation in real-time group editors: issues, algorithms, and achievements. In Proceedings of the ACM Conference on Computer Supported Cooperative Work. 59--68. Google Scholar
- Sun, C., Jia, X., Zhang, Y., Yang, Y., and Chen, D. 1998. Achieving convergence, causality-preservation, and intention-preservation in real-time cooperative editing systems. ACM Trans. Comput.-Hum. Interact. 5, 1 (March), 63--108. Google Scholar
- Sun, C., Yang, Y., Zhang, Y., and Chen, D. 1996. Distributed concurrency control in real-time cooperative editing systems. In Proceedings of the 1996 Asian Computing Science Conference. Lecture Notes in Computer Science, vol. 1179. Springer, Bielefeld, Germany, 84--95. Google Scholar
- Thimbleby, H. 1990. User Interface Design. Addison-Wesley, Reading, MA. Google Scholar
- Yang, Y. 1988. A new conceptual model for interactive user recovery and command reuse facilities. In Proceedings of the CHI'88 Conference on Human Factors in Computing Systems. 165--170. Google Scholar
Index Terms
- Undo as concurrent inverse in group editors
Recommendations
Undo any operation at any time in group editors
CSCW '00: Proceedings of the 2000 ACM conference on Computer supported cooperative workThe ability to undo operations is an indispensable feature of real-time group editors, but supporting group undo is a difficult problem. None of the existing solutions for group undo is able to support undoing any operation at any time with guaranteed ...
An integrating, transformation-oriented approach to concurrency control and undo in group editors
CSCW '96: Proceedings of the 1996 ACM conference on Computer supported cooperative workAlternative Correctness Criteria for Concurrent Execution of Transactions in Multilevel Secure Databases
This paper investigates issues related to transaction concurrency control in multilevel secure databases. It demonstrates how the conflicts between the correctness requirements and the secrecy requirements can be reconciled by proposing two different ...
Comments