Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2021, Vol. 15 Issue (5) : 155209    https://doi.org/10.1007/s11704-020-9518-x
RESEARCH ARTICLE
A semi-transparent selective undo algorithm for multi-user collaborative editors
Weiwei CAI1, Fazhi HE1(), Xiao LV2, Yuan CHENG3
1. School of Computer Science, Wuhan University,Wuhan 430072, China
2. Department of Computer Engineering, Naval University of Engineering,Wuhan 430072, China
3. School of InformationManagement,Wuhan University,Wuhan 430072, China
 Download: PDF(936 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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     
Corresponding Author(s): Fazhi HE   
Just Accepted Date: 11 June 2020   Issue Date: 07 June 2021
 Cite this article:   
Weiwei CAI,Fazhi HE,Xiao LV, et al. A semi-transparent selective undo algorithm for multi-user collaborative editors[J]. Front. Comput. Sci., 2021, 15(5): 155209.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-020-9518-x
https://academic.hep.com.cn/fcs/EN/Y2021/V15/I5/155209
1 B Cho, C Z Sun, A Ng. Issues and experiences in building heterogeneous co-editing systems. Proceedings of the ACM on Human-Computer Interaction, 2019, 3(GROUP): 1–28
https://doi.org/10.1145/3361126
2 H F Fan, K Li, X Z Li, T Y Song, W Z Zhang, Y Shi. CoVSCode: a novel real-time collaborative programming environment for lightweight IDE. Applied Sciences, 2019, 9(21): 4642
https://doi.org/10.3390/app9214642
3 S Mirri, M Roccetti, P Salomoni. Collaborative design of software applications: the role of users. Human-centric Computing and Information Sciences, 2018, 8(1): 1–20
https://doi.org/10.1186/s13673-018-0129-6
4 Y Q Liang, F Z He, X T Zeng. 3D mesh simplification with feature preservation based on whale optimization algorithm and differential evolution. Integrated Computer-Aided Engineering, 2020, 27(4): 417–435
https://doi.org/10.3233/ICA-200641
5 A Touhafi, A Braeken, A Tahiri, M Zbakh. Coderlabs: a cloud-based platform for real-time online labs with user collaboration. Concurrency and Computation: Practice and Experience, 2018, 30(12): e4377
https://doi.org/10.1002/cpe.4377
6 L P Gao, D F Gao, N X Xiong, C Lee. CoWebDraw: a real-time collaborative graphical editing system supporting multi-clients based on HTML5. Multimedia Tools and Applications, 2018, 77(4): 5067–5082
https://doi.org/10.1007/s11042-017-5242-4
7 C L Ignat, L André, G Oster. Enhancing rich content wikis with real-time collaboration. Concurrency and Computation: Practice and Experience, 2021, 33(8): e4110
https://doi.org/10.1002/cpe.4110
8 H F Fan, H M Zhu, Q Liu, Y Shi, C Z Sun. A novel DAL scheme with shared-locking for semantic conflict prevention in unconstrained realtime collaborative programming. IEEE Access, 2017, 5: 22566–22583
https://doi.org/10.1109/ACCESS.2017.2760914
9 A Ng, C Z Sun. 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
https://doi.org/10.1145/2957276.2957278
10 S Junuzovic, P Dewan. Towards self-optimizing collaborative systems. In: Proceedings of ACM Conference on Computer Supported Cooperative Work. 2012, 1421–1430
https://doi.org/10.1145/2145204.2145414
11 J W Bartel, P Dewan. Towards multi-domain collaborative toolkits. In: Proceedings of ACM Conference on Computer Supported Cooperative Work. 2012, 1297–1306
https://doi.org/10.1145/2145204.2145398
12 G Li, H Y Zhu, T Lu, X H Ding, N Gu. 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
https://doi.org/10.1145/2675133.2675155
13 J S Olson, D K Wang, G M Olson, J W Zhang. 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
https://doi.org/10.1145/3038919
14 D K Wang, H D Tan, T Lu. 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
https://doi.org/10.1145/3134742
15 W W Cai, A Ng, C Z Sun. 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
https://doi.org/10.1007/978-3-030-00560-3_6
16 C Z Sun, D Chen, X H Jia, Y C Zhang, Y Yang. Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems. ACM Transactions on Computer-Human Interaction, 1998, 5(1): 63–108
https://doi.org/10.1145/274444.274447
17 A Ng, F Liu, S Xia, H F Shen, C Z Sun. 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 C Z Sun, S Xia, D Sun, D Chen, H F Shen, W T Cai. Transparent adaptation of single-user applications for multi-user real-time collaboration. ACM Transactions on Computer-Human Interaction, 2006, 13(4): 531–582
https://doi.org/10.1145/1188816.1188821
19 B M Xu, Q Gao, C Y Li. Reusing single-user applications to create collaborative multi-member applications. Advances in Engineering Software, 2009, 40(8): 618–622
https://doi.org/10.1016/j.advengsoft.2008.11.002
20 H F Fan, C Z Sun, H F Shen. 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
https://doi.org/10.1145/2389176.2389194
21 A Prakash, M J Knister. A framework for undoing actions in collaborative systems. ACM Transactions on Computer-Human Interaction, 1994, 1(4): 295–330
https://doi.org/10.1145/198425.198427
22 R Choudhary, P Dewan. A general multi-user undo/redo model. In: Proceedings of European Conference on Computer-Supported Cooperative Work. 1995, 231–246
https://doi.org/10.1007/978-94-011-0349-7_15
23 C Z Sun. Undo as concurrent inverse in group editors. ACM Transactions on Computer-Human Interaction, 2002, 9(4): 309–361
https://doi.org/10.1145/586081.586085
24 J Ferrié, N Vidot, M Cart. 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
https://doi.org/10.1007/978-3-540-30468-5_12
25 S Weiss, P Urso, P Molli. An undo framework for P2P collaborative editing. In: Proceedings of EAI International Conference on Collaborative Computing. 2009, 529–544
https://doi.org/10.1007/978-3-642-03354-4_40
26 S Weiss, P Urso, P Molli. A flexible undo framework for collaborative editing. INRIA Research Report, 2008, RR–6516
27 D Sun, C Z Sun. Context-based operational transformation in distributed collaborative editing systems. IEEE Transactions on Parallel and Distributed Systems, 2009, 20(10): 1454–1470
https://doi.org/10.1109/TPDS.2008.240
28 B Shao, D Li, N Gu. An algorithm for selective undo of any operation in collaborative applications. In: Proceedings of ACM International Conference on Supporting Group Work. 2010, 131–140
https://doi.org/10.1145/1880071.1880093
29 Y S Yoon, B A Myers. Supporting selective undo in a code editor. In: Proceedings of International Conference on Software Engineering. 2015, 223–233
https://doi.org/10.1109/ICSE.2015.43
30 A Cherif, A Imine. Using CSP for coordinating undo-based collaborative applications. In: Proceedings of ACM Symposium on Applied Computing. 2016, 1928–1935
https://doi.org/10.1145/2851613.2851753
31 M Ressel, D Nitsche-Ruhland, R Gunzenhaeuser. 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
https://doi.org/10.1145/240080.240305
32 R Li, D Li, C Z Sun. 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 Y Xu, C Z Sun. Conditions and patterns for achieving convergence in OTbased co-editors. IEEE Transactions on Parallel and Distributed Systems, 2016, 27(3): 695–709
https://doi.org/10.1109/TPDS.2015.2412938
34 L Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 1978, 21(7): 558–565
https://doi.org/10.1145/359545.359563
35 D Li, R Li. Preserving operation effects relation in group editors. In: Proceedings of ACMConference on Computer Supported Cooperative Work. 2004, 457–466
https://doi.org/10.1145/1031607.1031683
36 G Oster, P Molli, P Urso, A Imine. Tombstone transformation functions for ensuring consistency in collaborative editing systems. In: Proceedings of EAI International Conference on Collaborative Computing. 2006, 1–10
https://doi.org/10.1109/COLCOM.2006.361867
37 R Li, D Li. A new operational transformation framework for real-time group editors. IEEE Transactions on Parallel and Distributed Systems, 2007, 18(3): 307–319
https://doi.org/10.1109/TPDS.2007.35
38 A Imine. Flexible concurrency control for real-time collaborative editors. In: Proceedings of IEEE International Conference on Distributed Computing Systems. 2008, 423–428
https://doi.org/10.1109/ICDCS.Workshops.2008.91
39 D Li, R Li. An admissibility-based operational transformation framework for collaborative editing systems. Computer Supported Cooperative Work, 2010, 19(1): 1–43
https://doi.org/10.1007/s10606-009-9103-1
40 N Gu, J M Yang, Q W Zhang. Consistency maintenance based on the mark & retrace technique in groupware systems. In: Proceedings of ACM International Conference on Supporting Group Work. 2005, 264–273
https://doi.org/10.1145/1099203.1099250
41 B Shao, D Li, N Gu. A fast operational transformation algorithm for mobile and asynchronous collaboration. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(12): 1707–1720
https://doi.org/10.1109/TPDS.2010.64
42 C Z Sun, D Sun, A Ng, WW Cai, B Cho. 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
https://doi.org/10.1145/3375186
43 D Sun, C Z Sun, A Ng, W W Cai. 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
https://doi.org/10.1145/3392825
44 D Sun, C Z Sun, A Ng, WW Cai. Real differences between OT and CRDT in building co-editing systems and real world applications. 2020, arXiv preprint arXiv:1905.01517
45 G Oster, P Urso, P Molli, A Imine. Data consistency for P2P collaborative editing. In: Proceedings of ACM Conference on Computer Supported Cooperative Work. 2006, 259–268
https://doi.org/10.1145/1180875.1180916
46 M Shapiro, N Preguiça, C Baquero, M Zawirski. Conflict-free replicated data types. INRIA Research Report, 2011, RR–7687
https://doi.org/10.1007/978-3-642-24550-3_29
47 S Weiss, P Urso, P Molli. Logoot-Undo: distributed collaborative editing system on P2P networks. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(8): 1162–1174
https://doi.org/10.1109/TPDS.2009.173
48 W H Yu. 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
https://doi.org/10.1145/2660398.2660401
49 D Li, R Li. A performance study of group editing algorithms. In: Proceedings of IEEE International Conference on Parallel and Distributed Systems. 2006, 300–307
https://doi.org/10.1109/ICPADS.2006.18
50 Y Lim, S Ahn. Architecture for mobile group communication in campus environment. Frontiers of Computer Science, 2013, 7(4): 505–513
https://doi.org/10.1007/s11704-013-1306-4
51 L P Gao, F Y Yu, Q K Chen, N X Xiong. Consistency maintenance of do and undo/redo operations in real-time collaborative bitmap editing systems. Cluster Computing, 2016, 19(1): 255–267
https://doi.org/10.1007/s10586-015-0499-8
52 H R Li, F Z He, Y Q Liang, Q Quan. A dividing-based many-objective evolutionary algorithm for large-scale feature selection. Soft Computing, 2020, 24(9): 6851–6870
https://doi.org/10.1007/s00500-019-04324-5
53 S D Zhang, F Z He. DRCDN: learning deep residual convolutional dehazing networks. The Visual Computer, 2020, 36(9): 1797–1808
https://doi.org/10.1007/s00371-019-01774-8
54 Z Y Cui, Y Liu, W Zhao. 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.
https://doi.org/10.1109/CSCWD.2019.8791883
55 Q Quan, F Z He, H R Li. A multi-phase blending method with incremental intensity for training detection networks. The Visual Computer, 2021, 37(2): 245–259
https://doi.org/10.1007/s00371-020-01796-7
56 H P Yu, F Z He, Y T Pan. A scalable region-based level set method using adaptive bilateral filter for noisy image segmentation. Multimedia Tools and Applications, 2020, 79: 5743–5765
https://doi.org/10.1007/s11042-019-08493-1
57 M Gao, B Ling, L Yang, J H Wen, Q Y Xiong, S Li. From similarity perspective: a robust collaborative filtering approach for service recommendations. Frontiers of Computer Science, 2019, 13(2): 231–246
https://doi.org/10.1007/s11704-017-6566-y
58 Y L Chen, F Z He, H R Li, D J Zhang, Y Q Wu. A full migration BBO algorithm with enhanced population quality bounds for multimodal biomedical image registration. Applied Soft Computing, 2020, 93: 106335
https://doi.org/10.1016/j.asoc.2020.106335
59 K Su, G P Yang, L Yang, P Su, Y L Yin. Non-negative locality-constrained vocabulary tree for finger vein image retrieval. Frontiers of Computer Science, 2019, 13(2): 318–332
https://doi.org/10.1007/s11704-017-6583-x
60 J S Yong, F Z He, H R Li, W Q Zhou. 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
https://doi.org/10.1007/s11766-019-3714-1
61 C X Wu, L F Li, CW Peng, Y Wu, N X Xiong, C Lee. Design and analysis of an effective graphics collaborative editing system. Eurasip Journal on Image and Video Processing, 2019, 1: 50
https://doi.org/10.1186/s13640-019-0427-6
62 J Zhang, F Z He, Y L Chen. A new haze removal approach for sky/river alike scenes based on external and internal clues. Multimedia Tools and Applications, 2020, 79: 2085–2107
https://doi.org/10.1007/s11042-019-08399-y
63 T Wang, Q P Zhang, Z Liu, W L Liu, D Wen. On social computing research collaboration patterns: a social network perspective. Frontiers of Computer Science, 2012, 6(1): 122–130
64 Y T Pan, F Z He, H P Yu. Learning social representations with deep autoencoder for recommender system. World Wide Web, 2020, 23(4): 2259–2279
https://doi.org/10.1007/s11280-020-00793-z
65 X H Shi, H T Lu. Community detection in scientific collaborative network with bayesian matrix learning. Frontiers of Computer Science, 2019, 13(1): 212–214
https://doi.org/10.1007/s11704-018-8124-7
66 Y T Pan, F Z He, H P Yu. A correlative denoising autoencoder to model social influence for top-n recommender system. Frontiers of Computer Science, 2020, 14(3): 143301
https://doi.org/10.1007/s11704-019-8123-3
67 G Zhang, Y M Li, Y H Shi. Distributed learning particle swarm optimizer for global optimization of multimodal problems. Frontiers of Computer Science, 2018, 12(1): 122–134
https://doi.org/10.1007/s11704-016-5373-1
68 J K Luo, F Z He, J S Yong. An efficient and robust bat algorithm with fusion of opposition-based learning and whale optimization algorithm. Intelligent Data Analysis, 2020, 24(3): 581–606
https://doi.org/10.3233/IDA-194641
69 W Zhao, H H Shen, F Zhang, H Z Tan. 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
https://doi.org/10.1109/CSCWD.2019.8791501
70 J K Luo, F Z He, H R, Z X T Li, Y Q Liang. A novel whale optimization algorithm with filtering disturbance and non-linear step. International Journal of Bio-Inspired Computation, 2020, 16: 137–148
71 N Hou, F Z He, Y Zhou, Y L Chen. An efficient GPU-based parallel tabu search algorithm for hardware/software co-design. Frontiers of Computer Science, 2020, 14(5): 145316
https://doi.org/10.1007/s11704-019-8184-3
72 S Q Zhang, Z Qin, Y H Yang, L Shen, Z Y Wang. Transparent partial page migration between CPU and GPU. Frontiers of Computer Science, 2020, 14(3): 143101
https://doi.org/10.1007/s11704-018-7386-4
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed