Item

Consistency Maintenance Based on the Mark & Retrace Technique in Groupware Systems

Thumbnail Image

Fulltext URI

Document type

Additional Information

Date

2005

Authors

Journal Title

Journal ISSN

Volume Title

Source

Proceedings of the 2005 ACM International Conference on Supporting Group Work

Publisher

Association for Computing Machinery

Abstract

Replicated architecture is widely used for concealing network delay. However, consistency maintenance in fully replicated architecture is a major technical challenge. In this paper, we report a Mark & Retrace based method in replicated groupware systems. Compared with the Operation Transformation technique, it does not adjust the operation's position but retraces the document's address space to the state at the time of the operation's generation. Then the operation can be executed directly in this address space. Mark & Retrace method can not only achieve the same goal of consistency maintenance but also provide a better support for Undo. This paper provides the proof of the algorithm's correctness of consistency maintenance, in which both the orders of character nodes and marks of each node at all sites are kept consistent. Furthermore, the amortized efficiency can reach O(log n).

Description

Gu, Ning; Yang, Jiangming; Zhang, Qiwei (2005): Consistency Maintenance Based on the Mark & Retrace Technique in Groupware Systems. Proceedings of the 2005 ACM International Conference on Supporting Group Work. DOI: 10.1145/1099203.1099250. New York, NY, USA: Association for Computing Machinery. pp. 264–273. Sanibel Island, Florida, USA

Keywords

address space transformation, CSCW, concurrency control, undo, group editors, mark &amp, retrace, consistency

Citation

DOI

10.1145/1099203.1099250

URI

URI

https://dl.eusset.eu/handle/20.500.12015/4830

Collections

GROUP 2005

Endorsement

Review

Supplemented By

Referenced By

Number of citations to item: 43

  • Liping Gao, Tun Lu, Ning Gu (2010): CLAF: Solving intention violation of step-wise operations in CAD groupware, In: Advanced Engineering Informatics 2(24), doi:10.1016/j.aei.2009.07.003
  • Sizheng Zhu, Shanshan Wang, Dan Wang, Liping Gao (2017): Research on Consistency Maintenance of Flowchart Design, In: Proceedings of the 12th Chinese Conference on Computer Supported Cooperative Work and Social Computing, doi:10.1145/3127404.3127462
  • Liping Gao, Fangyu Yu, Qingkui Chen, Naixue Xiong (2015): Consistency maintenance of Do and Undo/Redo operations in real-time collaborative bitmap editing systems, In: Cluster Computing 1(19), doi:10.1007/s10586-015-0499-8
  • G/l=e'/rald Oster, Pascal Molli, Pascal Urso, Abdessamad Imine (2006): Tombstone Transformation Functions for Ensuring Consistency in Collaborative Editing Systems, In: 2006 International Conference on Collaborative Computing: Networking, Applications and Worksharing, doi:10.1109/colcom.2006.361867
  • Chengzheng Sun, Yi Xu, Agustina Ng (2017): Exhaustive Search and Resolution of Puzzles in OT Systems Supporting String-Wise Operations, In: Proceedings of the 2017 ACM Conference on Computer Supported Cooperative Work and Social Computing, doi:10.1145/2998181.2998252
  • Te Jiang, Tun Lu, Ning Gu (2019): Themis: An AST-Based Lock-Free Routes Synchronizing and Sharing System for Self-Driving in Edge Computing Environments, In: IEEE Access, doi:10.1109/access.2019.2948021
  • Chengzheng Sun (2017): Reflections on collaborative editing research: From academic curiosity to real-world application, In: 2017 IEEE 21st International Conference on Computer Supported Cooperative Work in Design (CSCWD), doi:10.1109/cscwd.2017.8066663
  • Dan Wang, Sizheng Zhu, Liping Gao, Shanshan Wang, Xiaofang Xu, Changqing Tao (2018): MCPS2: Intention Maintenance of Structure Document Based MCPS Under Mobile Platform, In: Communications in Computer and Information Science, doi:10.1007/978-981-13-3044-5_2
  • Liping Gao, Bin Shao, Ning Gu (2007): Separating Data and View: Support View-wandering Between Different Trades during Engineering Design, In: 2007 11th International Conference on Computer Supported Cooperative Work in Design, doi:10.1109/cscwd.2007.4281406
  • Hansu Gu, Qiwei Zhang, Bin Shao (2007): Making AutoCAD Collaborative: Implementation and Application of CoAutoCAD, In: 2007 2nd International Conference on Pervasive Computing and Applications, doi:10.1109/icpca.2007.4365433
  • Chengzheng Sun, David Sun, Agustina Ng, Weiwei Cai, Bryden Cho (2020): Real Differences between OT and CRDT under a General Transformation Framework for Consistency Maintenance in Co-Editors, In: Proceedings of the ACM on Human-Computer Interaction GROUP(4), doi:10.1145/3375186
  • Hongfei Fan, Jiayao Gao, Hongming Zhu, Qin Liu, Yang Shi, Chengzheng Sun (2017): Balancing Conflict Prevention and Concurrent Work in Real-Time Collaborative Programming, In: Proceedings of the 12th Chinese Conference on Computer Supported Cooperative Work and Social Computing, doi:10.1145/3127404.3127447
  • Chengzheng Sun, Yi Xu, Agustina Agustina (2014): Exhaustive search of puzzles in operational transformation, In: Proceedings of the 17th ACM conference on Computer supported cooperative work & social computing, doi:10.1145/2531602.2531630
  • Yi Xu, Chengzheng Sun (2016): Conditions and Patterns for Achieving Convergence in OT-Based Co-Editors, In: IEEE Transactions on Parallel and Distributed Systems 3(27), doi:10.1109/tpds.2015.2412938
  • Weiwei Cai, Fazhi He, Shangxu Yang, Xiao Lv, Yuan Cheng (2022): Self‐compressing object sequence for consistency maintenance in co‐editors, In: Software: Practice and Experience 8(52), doi:10.1002/spe.3090
  • Jon A Preston, Sushil K Prasad (2015): A hierarchical peer-to-peer reduction and merging framework for efficient operational transformations in collaborative editing, In: 2015 International Conference on Collaboration Technologies and Systems (CTS), doi:10.1109/cts.2015.7210432
  • Liping Gao, Tun Lu (2010): Layered document model transformation and operation adaptation of two dimensional CAD environments, In: The 2010 14th International Conference on Computer Supported Cooperative Work in Design, doi:10.1109/cscwd.2010.5471922
  • Xiao Lv, Jiacun Yuan, Fazhi He, Yuan Cheng, Weiwei Cai (2021): Cloud-Based Lightweight Collaborative Editing Algorithm for Mobile Devices, In: 2021 IEEE 24th International Conference on Computer Supported Cooperative Work in Design (CSCWD), doi:10.1109/cscwd49262.2021.9437719
  • Xiantao Cai, Fazhi He, Shaofen Wang, Huajun Liu (2007): A Hierarchical Consistency Model for Graphics Media in Flexible Collaboration-Transparent Systems, In: 2007 11th International Conference on Computer Supported Cooperative Work in Design, doi:10.1109/cscwd.2007.4281432
  • Jiangming Yang, Qiwei Zhang, Ning Gu (2006): A Consistency Maintenance Approach in Replicated Services, In: The Sixth IEEE International Conference on Computer and Information Technology (CIT'06), doi:10.1109/cit.2006.4
  • Dan Wang, Sizheng Zhu, Liping Gao (2017): Conflict Resolution of Structured Document Collaborative Editing based on the Partial Replication Architecture in Cloud Platform, In: Proceedings of the 12th Chinese Conference on Computer Supported Cooperative Work and Social Computing, doi:10.1145/3127404.3127448
  • Weiwei Cai, Fazhi He, Xiao Lv (2022): Multi-core accelerated CRDT for large-scale and dynamic collaboration, In: The Journal of Supercomputing 8(78), doi:10.1007/s11227-022-04308-7
  • Zheng Xu, Chaofan Liu, Sitong Wang, Peng Zhang, Tun Lu, Ning Gu (2022): An AST-based consistency maintenance scheme for cross-chain digital assets, In: CCF Transactions on Pervasive Computing and Interaction 2(4), doi:10.1007/s42486-022-00096-4
  • Gérald Oster, Pascal Urso, Pascal Molli, Abdessamad Imine (2006): Data consistency for P2P collaborative editing, In: Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work, doi:10.1145/1180875.1180916
  • Hongfei Fan, Hongming Zhu, Qin Liu, Yang Shi, Chengzheng Sun (2017): A Novel DAL Scheme With Shared-Locking for Semantic Conflict Prevention in Unconstrained Real-Time Collaborative Programming, In: IEEE Access, doi:10.1109/access.2017.2760914
  • Liping Gao, Ning Gu (2007): Preserving Consistency Based on Wall-Time Precedence in P2P DVEs, In: 7th IEEE International Conference on Computer and Information Technology (CIT 2007), doi:10.1109/cit.2007.11
  • Weiwei Cai, Fazhi He, Xiao Lv, Yuan Cheng (2021): A semi-transparent selective undo algorithm for multi-user collaborative editors, In: Frontiers of Computer Science 5(15), doi:10.1007/s11704-020-9518-x
  • David Sun, Chengzheng Sun (2006): Operation context and context-based operational transformation, In: Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work, doi:10.1145/1180875.1180918
  • Zheng Xu, Rui Jiang, Peng Zhang, Tun Lu, Ning Gu (2022): TxChain: Scaling Sharded Decentralized Ledger via Chained Transaction Sequences, In: Lecture Notes in Computer Science, doi:10.1007/978-3-031-00123-9_27
  • Dayi Yang, Tun Lu, Huanhuan Xia, Bin Shao, Ning Gu (2016): Making itinerary planning collaborative: An AST-based approach, In: 2016 IEEE 20th International Conference on Computer Supported Cooperative Work in Design (CSCWD), doi:10.1109/cscwd.2016.7565998
  • Li Ping Gao, Yue Wei Ding (2010): Combining AST and Lock Techniques to Maintain Consistency of Multiple Objects in Replicated CAD Environments, In: Advanced Materials Research, doi:10.4028/www.scientific.net/amr.97-101.3314
  • Huanhuan Xia, Tun Lu, Bin Shao, Guo Li, Xianghua Ding, Ning Gu (2014): A partial replication approach for anywhere anytime mobile commenting, In: Proceedings of the 17th ACM conference on Computer supported cooperative work & social computing, doi:10.1145/2531602.2531609
  • Jiangming Yang, Haixun Wang, Ning Gu, Yiming Liu, Chunsong Wang, Qiwei Zhang (2008): Lock-free consistency control for web 2.0 applications, In: Proceedings of the 17th international conference on World Wide Web, doi:10.1145/1367497.1367595
  • Jianhao Zhang, Tun Lu, Huanhuan Xia, Bin Shao, Ning Gu (2017): ASTS: A string-wise address space transformation algorithm for real-time collaborative editing, In: 2017 IEEE 21st International Conference on Computer Supported Cooperative Work in Design (CSCWD), doi:10.1109/cscwd.2017.8066688
  • Jon A. Preston, Sushil K. Prasad (2006): An Efficient Synchronous Collaborative Editing System Employing Dynamic Locking of Varying Granularity in Generalized Document Trees, In: 2006 International Conference on Collaborative Computing: Networking, Applications and Worksharing, doi:10.1109/colcom.2006.361858
  • Joseph Gentle, Martin Kleppmann (2025): Collaborative Text Editing with Eg-walker: Better, Faster, Smaller, In: Proceedings of the Twentieth European Conference on Computer Systems, doi:10.1145/3689031.3696076
  • Jon A. Preston, Sushil K. Prasad (2000): P2P Document Tree Management in a Real-Time Collaborative Editing System, In: Lecture Notes in Computer Science, doi:10.1007/978-3-540-77220-0_39
  • Xinyue Yu, Tun Lu (2023): An AST-Based Collaborative Discussion Tool for the MOOC Environment, In: Communications in Computer and Information Science, doi:10.1007/978-981-99-2356-4_23
  • D. Sun, Chengzheng Sun (2009): Context-Based Operational Transformation in Distributed Collaborative Editing Systems, In: IEEE Transactions on Parallel and Distributed Systems 10(20), doi:10.1109/tpds.2008.240
  • Fangyu Yu, Peng Zhang, Xianghua Ding, Tun Lu, Ning Gu (2022): Exploring How Workspace Awareness Cues Affect Distributed Meeting Outcome, In: International Journal of Human–Computer Interaction 8(39), doi:10.1080/10447318.2022.2064063
  • Bin Shao, Du Li, Ning Gu (2010): A sequence transformation algorithm for supporting cooperative work on mobile devices, In: Proceedings of the 2010 ACM conference on Computer supported cooperative work, doi:10.1145/1718918.1718949
  • Liping Gao, Tun Lu, Ning Gu (2009): Supporting semantic maintenance of complex Undo operations in replicated Co-AutoCAD environments, In: 2009 13th International Conference on Computer Supported Cooperative Work in Design, doi:10.1109/cscwd.2009.4968039
  • Jiangming Yang, Qiwei Zhang, Ning Gu, Genxing Yang, Zhenyu Liu (2005): The Multi-version and Single-display Strategy in Undo Scheme, In: The Fifth International Conference on Computer and Information Technology (CIT'05), doi:10.1109/cit.2005.189
Please note: Providing information about citations is only possible thanks to to the open metadata APIs provided by crossref.org and opencitations.net. These lists may be incomplete due to unavailable citation data.source: opencitations.net, crossref.org