skip to main content
10.1145/1099203.1099250acmconferencesArticle/Chapter ViewAbstractPublication PagesgroupConference Proceedingsconference-collections
Article

Consistency maintenance based on the mark & retrace technique in groupware systems

Published: 06 November 2005 Publication History

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).

References

[1]
T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, Boston, Sept 2001.
[2]
C. A. Ellis and S. J. Gibbs. Concurrency control in groupware systems. In Proceedings of the ACM Conference on the Management of Data 1989, pages 399--407, Portland Oregon, May 1989. ACM.
[3]
N. Gu, J. Xu, X. Wu, J. Yang, and W. Ye. Ontology based semantic conflicts resolution in collaborative editing of design documents. International Journal of Advanced Engineering Informatics (IJAEI), Jan 2005. Accepted.
[4]
H. He, Q. Wu, and L. Luo. Document marking scheme for preserving intention of operation in cooperative editing system. Journal of Software, 10(2):160--164, Feb 1999.
[5]
A. Imine, P. Molli, G. Oster, and M. Rusinowitch. Proving correctness of transformation functions in real-time groupware. In European CSCW'03 Proceedings, Sept 2003.
[6]
D. Li and R. Li. Preserving operation effects relation in group editors. In Proceedings of ACM Conference on CSCW 2004, pages 437--446, Chicago, USA, Nov 2004. ACM.
[7]
M. Ressel, D. Nitsche-Ruhland, and R. Gunzenbauser. An integrating, transformation-oriented approach to concurrency control and undo in group editors. In Proceedings of ACM Conference on CSCW 1996, pages 288--297, Nov 1996.
[8]
H. Shen and C. Sun. Flexible notification for collaborative systems. In Proceedings of ACM Conference on CSCW 2002, pages 77--86, Chicago, USA, Nov 2002.
[9]
M. Suleiman, M. Cart, and J. Ferrie. Concurrent operations in a distributed and mobile collaborative environment. In Proceedings of the IEEE Fourteenth International Conference on Data Engineering, pages 36--45, Orlando, USA, Feb 1998.
[10]
C. Sun. Undo any operation at any time in group editors. In Proceedings of ACM Conference on CSCW 2000, pages 191--200, Philadelphia, USA, Dec 2000.
[11]
C. Sun. Undo as concurrent inverse in group editors. ACM Transactions on Computer-Human Interaction, 9(4):309--361, Dec 2002.
[12]
C. Sun. The coword and copowerpoint project. http://reduce.qpsf.edu.au/coword/, 2004.
[13]
C. Sun and D. Chen. Consistency maintenance in real-time collaborative graphics editing systems. ACM Transactions on Computer-Human Interaction, 9(1):1--41, Mar 2002.
[14]
C. Sun and C. A. Ellis. Operation transformation in real-time group editor: issuer, algorithm, and achievement. In Proceedings of ACM Conference on CSCW 1998, pages 59--68, Seattle, USA, Nov 1998.
[15]
C. Sun, X. Jia, Y. Zhang, Y. Yang, and D. Chen. Achieving convergence, causality-preservation, and intention-preservation in real-time cooperative editing systems. ACM Transactions on Computer-Human Interaction, 5(1):63--108, Mar 1998.
[16]
D. Sun, S. Xia, C. Sun, and D. Chen. Operational transformation for collaborative word processing. In Proceedings of ACM Conference on CSCW 2004, pages 437--446, Chicago, USA, Nov 2004.
[17]
N. Vidot, M. Cart, J. Ferrie, and M. Suleiman. Copies convergence in a distributed realtime collaborative environment. In Proceedings of ACM Conference on CSCW 2000, pages 171--180, Philadelphia, USA, Dec 2000.
[18]
X. Wu and N. Gu. A concurrency control method based on document marking. Journal of Computer Research and Development, 39(12):1662--1667, 2002.
[19]
J. Yang, N. Gu, and X. Wu. A document mark based on method supporting group undo. In ACM CSCW'2004 Workshop on Collaborative Editing Systems, Chicago, USA, Nov 2004.
[20]
J. Yang, Q. Zhang, N. Gu, G. Yang, and Z. Liu. The multi-version and single-display strategy in undo scheme. In The 5th International Conference on Computer and Information Technology, Shanghai, China, Sept 2005.

Cited By

View all
  • (2023)An AST-Based Collaborative Discussion Tool for the MOOC EnvironmentComputer Supported Cooperative Work and Social Computing10.1007/978-981-99-2356-4_23(284-294)Online publication date: 13-May-2023
  • (2022)Exploring How Workspace Awareness Cues Affect Distributed Meeting OutcomeInternational Journal of Human–Computer Interaction10.1080/10447318.2022.206406339:8(1606-1625)Online publication date: 24-Apr-2022
  • (2022)An AST-based consistency maintenance scheme for cross-chain digital assetsCCF Transactions on Pervasive Computing and Interaction10.1007/s42486-022-00096-44:2(142-157)Online publication date: 13-Apr-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GROUP '05: Proceedings of the 2005 ACM International Conference on Supporting Group Work
November 2005
368 pages
ISBN:1595932232
DOI:10.1145/1099203
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2005

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. CSCW
  2. address space transformation
  3. concurrency control
  4. consistency
  5. group editors
  6. mark & retrace
  7. undo

Qualifiers

  • Article

Conference

GROUP05
Sponsor:
GROUP05: ACM 2005 International Conference on Supporting Group Work
November 6 - 9, 2005
Florida, Sanibel Island, USA

Acceptance Rates

Overall Acceptance Rate 125 of 405 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2023)An AST-Based Collaborative Discussion Tool for the MOOC EnvironmentComputer Supported Cooperative Work and Social Computing10.1007/978-981-99-2356-4_23(284-294)Online publication date: 13-May-2023
  • (2022)Exploring How Workspace Awareness Cues Affect Distributed Meeting OutcomeInternational Journal of Human–Computer Interaction10.1080/10447318.2022.206406339:8(1606-1625)Online publication date: 24-Apr-2022
  • (2022)An AST-based consistency maintenance scheme for cross-chain digital assetsCCF Transactions on Pervasive Computing and Interaction10.1007/s42486-022-00096-44:2(142-157)Online publication date: 13-Apr-2022
  • (2022)Multi-core accelerated CRDT for large-scale and dynamic collaborationThe Journal of Supercomputing10.1007/s11227-022-04308-778:8(10799-10828)Online publication date: 1-May-2022
  • (2022)TxChain: Scaling Sharded Decentralized Ledger via Chained Transaction SequencesDatabase Systems for Advanced Applications10.1007/978-3-031-00123-9_27(333-340)Online publication date: 11-Apr-2022
  • (2022)Self‐compressing object sequence for consistency maintenance in co‐editorsSoftware: Practice and Experience10.1002/spe.309052:8(1802-1825)Online publication date: 21-Apr-2022
  • (2021)Cloud-Based Lightweight Collaborative Editing Algorithm for Mobile Devices2021 IEEE 24th International Conference on Computer Supported Cooperative Work in Design (CSCWD)10.1109/CSCWD49262.2021.9437719(250-255)Online publication date: 5-May-2021
  • (2021)A semi-transparent selective undo algorithm for multi-user collaborative editorsFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-020-9518-x15:5Online publication date: 1-Oct-2021
  • (2020)Real Differences between OT and CRDT under a General Transformation Framework for Consistency Maintenance in Co-EditorsProceedings of the ACM on Human-Computer Interaction10.1145/33751864:GROUP(1-26)Online publication date: 4-Jan-2020
  • (2019)Themis: An AST-Based Lock-Free Routes Synchronizing and Sharing System for Self-Driving in Edge Computing EnvironmentsIEEE Access10.1109/ACCESS.2019.29480217(151692-151704)Online publication date: 2019
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media