A semi-transparent selective undo algorithm for multi-user collaborative editors

Abstract

Multi-user collaborative editors are useful computer-aided tools to support human-to-human collaboration. For multi-user collaborative editors, selective undo is an essential utility enabling users to undo any editing operations at any time. Collaborative editors usually adopt operational transformation (OT) to address concurrency and consistency issues. However, it is still a great challenge to design an efficient and correct OT algorithm capable of handling both normal do operations and user-initiated undo operations because these two kinds of operations can interfere with each other in various forms. In this paper, we propose a semi-transparent selective undo algorithm that handles both do and undo in a unified framework, which separates the processing part of do operations from the processing part of undo operations. Formal proofs are provided to prove the proposed algorithm under the well-established criteria. Theoretical analysis and experimental evaluation are conducted to show that the proposed algorithm outperforms the prior OT-based selective undo algorithms.

Keywords

human-centric collaboration / collaborative editing systems / selective undo / concurrency control / replication consistency

References

[1] Cho B, Sun C Z, Ng A. Issues and experiences in building heterogeneous co-editing systems. Proceedings of the ACM on Human-Computer Interaction, 2019, 3(GROUP): 1–28

[2] Fan H F, Li K, Li X Z, Song T Y, Zhang W Z, Shi Y. CoVSCode: a novel real-time collaborative programming environment for lightweight IDE. Applied Sciences, 2019, 9(21): 4642

[3] Mirri S, Roccetti M, Salomoni P. Collaborative design of software applications: the role of users. Human-centric Computing and Information Sciences, 2018, 8(1): 1–20

[4] Liang Y Q, He F Z, Zeng X T. 3D mesh simplification with feature preservation based on whale optimization algorithm and differential evolution. Integrated Computer-Aided Engineering, 2020, 27(4): 417–435

[5] Touhafi A, Braeken A, Tahiri A, Zbakh M. Coderlabs: a cloud-based platform for real-time online labs with user collaboration. Concurrency and Computation: Practice and Experience, 2018, 30(12): e4377

[6] Gao L P, Gao D F, Xiong N X, Lee C. CoWebDraw: a real-time collaborative graphical editing system supporting multi-clients based on HTML5. Multimedia Tools and Applications, 2018, 77(4): 5067–5082

[7] Ignat C L, André L, Oster G. Enhancing rich content wikis with real-time collaboration. Concurrency and Computation: Practice and Experience, 2021, 33(8): e4110

[8] Fan H F, Zhu H M, Liu Q, Shi Y, Sun C Z. A novel DAL scheme with shared-locking for semantic conflict prevention in unconstrained realtime collaborative programming. IEEE Access, 2017, 5: 22566–22583

[9] Ng A, Sun C Z. Operational transformation for real-time synchronization of shared workspace in cloud storage. In: Proceedings of ACM International Conference on Supporting Group Work. 2016, 61–70

[10] Junuzovic S, Dewan P. Towards self-optimizing collaborative systems. In: Proceedings of ACM Conference on Computer Supported Cooperative Work. 2012, 1421–1430

[11] Bartel J W, Dewan P. Towards multi-domain collaborative toolkits. In: Proceedings of ACM Conference on Computer Supported Cooperative Work. 2012, 1297–1306

[12] Li G, Zhu H Y, Lu T, Ding X H, Gu N. Is it good to be like wikipedia?: exploring the trade-offs of introducing collaborative editing model to Q&A sites. In: Proceedings of ACM Conference on Computer Supported Cooperative Work and Social Computing. 2015, 1080–1091

[13] Olson J S, Wang D K, Olson G M, Zhang J W. How people write together now: beginning the investigation with advanced undergraduates in a project course. ACM Transactions on Computer-Human Interaction, 2017, 24(1): 1–40

[14] Wang D K, Tan H D, Lu T. Why users do not want to write together when they are writing together: users’ rationales for today’s collaborative writing practices. Proceedings of the ACM on Human-Computer Interaction, 2017, 1(CSCW): 1–18

[15] Cai W W, Ng A, Sun C Z. Some discoveries from a concurrency benchmark study of major cloud storage systems. In: Proceedings of International Conferenceon on Cooperative Design, Visualization, and Engineering. 2018, 44–48

[16] Sun C Z, Chen D, Jia X H, Zhang Y C, Yang Y. Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems. ACM Transactions on Computer-Human Interaction, 1998, 5(1): 63–108

[17] Ng A, Liu F, Xia S, Shen H F, Sun C Z. CoMaya: incorporating advanced collaboration capabilities into 3D digital media design tools. In: Proceedings of ACM Conference on Computer Supported Cooperative Work. 2008, 5–8

[18] Sun C Z, Xia S, Sun D, Chen D, Shen H F, Cai W T. Transparent adaptation of single-user applications for multi-user real-time collaboration. ACM Transactions on Computer-Human Interaction, 2006, 13(4): 531–582

[19] Xu B M, Gao Q, Li C Y. Reusing single-user applications to create collaborative multi-member applications. Advances in Engineering Software, 2009, 40(8): 618–622

[20] Fan H F, Sun C Z, Shen H F. ATCoPE: any-time collaborative programming environment for seamless integration of real-time and non-real-time teamwork in software development. In: Proceedings of ACM International Conference on Supporting Group Work. 2012, 107–116

[21] Prakash A, Knister M J. A framework for undoing actions in collaborative systems. ACM Transactions on Computer-Human Interaction, 1994, 1(4): 295–330

[22] Choudhary R, Dewan P. A general multi-user undo/redo model. In: Proceedings of European Conference on Computer-Supported Cooperative Work. 1995, 231–246

[23] Sun C Z. Undo as concurrent inverse in group editors. ACM Transactions on Computer-Human Interaction, 2002, 9(4): 309–361

[24] Ferrié J, Vidot N, Cart M. Concurrent undo operations in collaborative environments using operational transformation. In: Proceedings of OTM Confederated International Conference on the Move to Meaningful Internet Systems. 2004, 155–173

[25] Weiss S, Urso P, Molli P. An undo framework for P2P collaborative editing. In: Proceedings of EAI International Conference on Collaborative Computing. 2009, 529–544

[26] Weiss S, Urso P, Molli P. A flexible undo framework for collaborative editing. INRIA Research Report, 2008, RR–6516

[27] Sun D, Sun C Z. Context-based operational transformation in distributed collaborative editing systems. IEEE Transactions on Parallel and Distributed Systems, 2009, 20(10): 1454–1470

[28] Shao B, Li D, Gu N. An algorithm for selective undo of any operation in collaborative applications. In: Proceedings of ACM International Conference on Supporting Group Work. 2010, 131–140

[29] Yoon Y S, Myers B A. Supporting selective undo in a code editor. In: Proceedings of International Conference on Software Engineering. 2015, 223–233

[30] Cherif A, Imine A. Using CSP for coordinating undo-based collaborative applications. In: Proceedings of ACM Symposium on Applied Computing. 2016, 1928–1935

[31] Ressel M, Nitsche-Ruhland D, Gunzenhaeuser R. Integrating, transformation-oriented approach to concurrency control and undo in group editors. In: Proceedings of ACM Conference on Computer Supported Cooperative Work. 1996, 288–297

[32] Li R, Li D, Sun C Z. A time interval based consistency control algorithm for interactive groupware applications. In: Proceedings of IEEE International Conference on Parallel and Distributed Systems. 2004, 429–436

[33] Xu Y, Sun C Z. Conditions and patterns for achieving convergence in OTbased co-editors. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(3): 695–709

[34] Lamport L. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 1978, 21(7): 558–565

[35] Li D, Li R. Preserving operation effects relation in group editors. In: Proceedings of ACMConference on Computer Supported Cooperative Work. 2004, 457–466

[36] Oster G, Molli P, Urso P, Imine A. Tombstone transformation functions for ensuring consistency in collaborative editing systems. In: Proceedings of EAI International Conference on Collaborative Computing. 2006, 1–10

[37] Li R, Li D. A new operational transformation framework for real-time group editors. IEEE Transactions on Parallel and Distributed Systems, 2007, 18(3): 307–319

[38] Imine A. Flexible concurrency control for real-time collaborative editors. In: Proceedings of IEEE International Conference on Distributed Computing Systems. 2008, 423–428

[39] Li D, Li R. An admissibility-based operational transformation framework for collaborative editing systems. Computer Supported Cooperative Work, 2010, 19(1): 1–43

[40] Gu N, Yang J M, Zhang Q W. Consistency maintenance based on the mark & retrace technique in groupware systems. In: Proceedings of ACM International Conference on Supporting Group Work. 2005, 264–273

[41] Shao B, Li D, Gu N. A fast operational transformation algorithm for mobile and asynchronous collaboration. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(12): 1707–1720

[42] Sun C Z, Sun D, Ng A, Cai WW, Cho B. Real differences between OT and CRDT under a general transformation framework for consistency maintenance in co-editors. Proceedings of the ACM on Human-Computer Interaction, 2020, 4(GROUP): 1–26

[43] Sun D, Sun C Z, Ng A, Cai W W. Real differences between OT and CRDT in correctness and complexity for consistency maintenance in coeditors. Proceedings of the ACM on Human-Computer Interaction, 2020, 4(CSCW1): 1–30

[44] Sun D, Sun C Z, Ng A, Cai WW. Real differences between OT and CRDT in building co-editing systems and real world applications. 2020, arXiv preprint arXiv:1905.01517

[45] Oster G, Urso P, Molli P, Imine A. Data consistency for P2P collaborative editing. In: Proceedings of ACM Conference on Computer Supported Cooperative Work. 2006, 259–268

[46] Shapiro M, Preguiça N, Baquero C, Zawirski M. Conflict-free replicated data types. INRIA Research Report, 2011, RR–7687

[47] Weiss S, Urso P, Molli P. Logoot-Undo: distributed collaborative editing system on P2P networks. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(8): 1162–1174

[48] Yu W H. Supporting string-wise operations and selective undo for peerto-peer group editing. In: Proceedings of ACM International Conference on Supporting Group Work. 2014, 226–237

[49] Li D, Li R. A performance study of group editing algorithms. In: Proceedings of IEEE International Conference on Parallel and Distributed Systems. 2006, 300–307

[50] Lim Y, Ahn S. Architecture for mobile group communication in campus environment. Frontiers of Computer Science, 2013, 7(4): 505–513

[51] Gao L P, Yu F Y, Chen Q K, Xiong N X. Consistency maintenance of do and undo/redo operations in real-time collaborative bitmap editing systems. Cluster Computing, 2016, 19(1): 255–267

[52] Li H R, He F Z, Liang Y Q, Quan Q. A dividing-based many-objective evolutionary algorithm for large-scale feature selection. Soft Computing, 2020, 24(9): 6851–6870

[53] Zhang S D, He F Z. DRCDN: learning deep residual convolutional dehazing networks. The Visual Computer, 2020, 36(9): 1797–1808

[54] Cui Z Y, Liu Y, Zhao W. YUN: a fast ground-to-air cloud image recognition framework. In: Proceedings of IEEE International Conference on Computer Supported Cooperative Work in Design. 2019, 290–294.

[55] Quan Q, He F Z, Li H R. A multi-phase blending method with incremental intensity for training detection networks. The Visual Computer, 2021, 37(2): 245–259

[56] Yu H P, He F Z, Pan Y T. A scalable region-based level set method using adaptive bilateral filter for noisy image segmentation. Multimedia Tools and Applications, 2020, 79: 5743–5765

[57] Gao M, Ling B, Yang L, Wen J H, Xiong Q Y, Li S. From similarity perspective: a robust collaborative filtering approach for service recommendations. Frontiers of Computer Science, 2019, 13(2): 231–246

[58] Chen Y L, He F Z, Li H R, Zhang D J, Wu Y Q. A full migration BBO algorithm with enhanced population quality bounds for multimodal biomedical image registration. Applied Soft Computing, 2020, 93: 106335

[59] Su K, Yang G P, Yang L, Su P, Yin Y L. Non-negative locality-constrained vocabulary tree for finger vein image retrieval. Frontiers of Computer Science, 2019, 13(2): 318–332

[60] Yong J S, He F Z, Li H R, Zhou W Q. A novel bat algorithm based on cross boundary learning and uniform explosion strategy. Applied Mathematics—A Journal of Chinese Universities, 2019, 34(4): 482–504

[61] Wu C X, Li L F, Peng CW,Wu Y, Xiong N X, Lee C. Design and analysis of an effective graphics collaborative editing system. Eurasip Journal on Image and Video Processing, 2019, 1: 50

[62] Zhang J, He F Z, Chen Y L. A new haze removal approach for sky/river alike scenes based on external and internal clues. Multimedia Tools and Applications, 2020, 79: 2085–2107

[63] Wang T, Zhang Q P, Liu Z, Liu W L, Wen D. On social computing research collaboration patterns: a social network perspective. Frontiers of Computer Science, 2012, 6(1): 122–130

[64] Pan Y T, He F Z, Yu H P. Learning social representations with deep autoencoder for recommender system. World Wide Web, 2020, 23(4): 2259–2279

[65] Shi X H, Lu H T. Community detection in scientific collaborative network with bayesian matrix learning. Frontiers of Computer Science, 2019, 13(1): 212–214

[66] Pan Y T, He F Z, Yu H P. A correlative denoising autoencoder to model social influence for top-n recommender system. Frontiers of Computer Science, 2020, 14(3): 143301

[67] Zhang G, Li Y M, Shi Y H. Distributed learning particle swarm optimizer for global optimization of multimodal problems. Frontiers of Computer Science, 2018, 12(1): 122–134

[68] Luo J K, He F Z, Yong J S. An efficient and robust bat algorithm with fusion of opposition-based learning and whale optimization algorithm. Intelligent Data Analysis, 2020, 24(3): 581–606

[69] Zhao W, Shen H H, Zhang F, Tan H Z. Adaptive power optimization for mobile traffic based on machine learning. In: Proceedings of IEEE International Conference on Computer Supported Cooperative Work in Design. 2019, 500–505

[70] Luo J K, He F Z, Li H R, Z X T, Liang Y Q. A novel whale optimization algorithm with filtering disturbance and non-linear step. International Journal of Bio-Inspired Computation, 2020, 16: 137–148

[71] Hou N, He F Z, Zhou Y, Chen Y L. An efficient GPU-based parallel tabu search algorithm for hardware/software co-design. Frontiers of Computer Science, 2020, 14(5): 145316

[72] Zhang S Q, Qin Z, Yang Y H, Shen L, Wang Z Y. Transparent partial page migration between CPU and GPU. Frontiers of Computer Science, 2020, 14(3): 143101

RIGHTS & PERMISSIONS

2021 Higher Education Press