More Web Proxy on the site http://driver.im/

research-article

LSEQ: an adaptive structure for sequences in distributed collaborative editing

Authors:

Brice Nédelec,

Achour Mostefaoui,

Emmanuel DesmontilsAuthors Info & Claims

DocEng '13: Proceedings of the 2013 ACM symposium on Document engineering

Pages 37 - 46

https://doi.org/10.1145/2494266.2494278

Published: 10 September 2013 Publication History

Abstract

Distributed collaborative editing systems allow users to work distributed in time, space and across organizations. Trending distributed collaborative editors such as Google Docs, Etherpad or Git have grown in popularity over the years. A new kind of distributed editors based on a family of distributed data structure replicated on several sites called Conflict-free Replicated Data Type (CRDT for short) appeared recently. This paper considers a CRDT that represents a distributed sequence of basic elements that can be lines, words or characters (sequence CRDT). The possible operations on this sequence are the insertion and the deletion of elements. Compared to the state of the art, this approach is more decentralized and better scales in terms of the number of participants. However, its space complexity is linear with respect to the total number of inserts and the insertion points in the document. This makes the overall performance of such editors dependent on the editing behaviour of users. This paper proposes and models LSEQ, an adaptive allocation strategy for a sequence CRDT. LSEQ achieves in the average a sub-linear spatial-complexity whatever is the editing behaviour. A series of experiments validates LSEQ showing that it outperforms existing approaches.

References

[1]

M. Ahmed-Nacer, C.-L. Ignat, G. Oster, H.-G. Roh, and P. Urso. Evaluating CRDTs for Real-time Document Editing. In ACM, editor, 11th ACM Symposium on Document Engineering, pages 103--112, Mountain View, California, Etats-Unis, Sept. 2011.

Digital Library

[2]

A. Andersson. Faster deterministic sorting and searching in linear space. In Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on, pages 135--141. IEEE, 1996.

Digital Library

[3]

A. Andersson and M. Thorup. Dynamic ordered sets with exponential search trees. J. ACM, 54(3), June 2007.

Digital Library

[4]

C. A. Ellis and S. J. Gibbs. Concurrency control in groupware systems. In Proceedings of the 1989 ACM SIGMOD international conference on Management of data, SIGMOD '89, pages 399--407, New York, NY, USA, 1989. ACM.

Digital Library

[5]

C. A. Ellis, S. J. Gibbs, and G. Rein. Groupware: some issues and experiences. Communications of the ACM, 34(1):39--58, 1991.

Digital Library

[6]

S. Greenberg and D. Marwood. Real time groupware as a distributed system: concurrency control and its effect on the interface. In Proceedings of the 1994 ACM conference on Computer supported cooperative work, pages 207--217, 1994.

Digital Library

[7]

V. Grishchenko. Deep hypertext with embedded revision control implemented in regular expressions. In Proceedings of the 6th International Symposium on Wikis and Open Collaboration, WikiSym '10, pages 3:1--3:10, New York, NY, USA, 2010. ACM.

Digital Library

[8]

P. R. Johnson and R. H. Thomas. Maintenance of duplicate databases. RFC 677, Jan. 1975.

Digital Library

[9]

M. Letia, N. Preguica, and M. Shapiro. Crdts: Consistency without concurrency control. Arxiv preprint arXiv:0907.0929, 2009.

[10]

D. A. Nichols, P. Curtis, M. Dixon, and J. Lamping. High-latency, low-bandwidth windowing in the jupiter collaboration system. In Proceedings of the 8th annual ACM symposium on User interface and software technology, pages 111--120. ACM, 1995.

Digital Library

[11]

G. Oster, P. Urso, P. Molli, and A. Imine. Data consistency for p2p collaborative editing. In Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work, pages 259--268. ACM, 2006.

Digital Library

[12]

N. Preguica, J. M. Marques, M. Shapiro, and M. Letia. A commutative replicated data type for cooperative editing. In Distributed Computing Systems, 2009. ICDCS'09. 29th IEEE International Conference on, pages 395--403. Ieee, 2009.

Digital Library

[13]

H.-G. Roh, M. Jeon, J.-S. Kim, and J. Lee. Replicated abstract data types: Building blocks for collaborative applications. Journal of Parallel and Distributed Computing, 71(3):354--368, 2011.

Digital Library

[14]

Y. Saito and M. Shapiro. Replication: Optimistic Approaches. technical report, 2002.

[15]

Y. Saito and M. Shapiro. Optimistic replication. ACM Comput. Surv., 37(1):42--81, Mar. 2005.

Digital Library

[16]

M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski. Conflict-free replicated data types. Stabilization, Safety, and Security of Distributed Systems, pages 386--400, 2011.

Digital Library

[17]

A. Singh and D. Garg. Implementation and performance analysis of exponential tree sorting. International Journal of Computer Applications ISBN, pages 978--93, 2011.

[18]

C. Sun and C. Ellis. Operational transformation in real-time group editors: issues, algorithms, and achievements. In Proceedings of the 1998 ACM conference on Computer supported cooperative work, CSCW '98, pages 59--68, New York, NY, USA, 1998. ACM.

Digital Library

[19]

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 (TOCHI), 5(1):63--108, 1998.

Digital Library

[20]

S. Weiss, P. Urso, and P. Molli. Wooki: A p2p wiki-based collaborative writing tool. In B. Benatallah, F. Casati, D. Georgakopoulos, C. Bartolini, W. Sadiq, and C. Godart, editors, Web Information Systems Engineering - WISE 2007, volume 4831 of Lecture Notes in Computer Science, pages 503--512. Springer Berlin Heidelberg, 2007.

Digital Library

[21]

S. Weiss, P. Urso, and P. Molli. Logoot: a scalable optimistic replication algorithm for collaborative editing on p2p networks. In Distributed Computing Systems, 2009. ICDCS'09. 29th IEEE International Conference on, pages 404--412. IEEE, 2009.

Digital Library

[22]

S. Weiss, P. Urso, and P. Molli. Logoot-undo: Distributed collaborative editing system on p2p networks. IEEE Trans. Parallel Distrib. Syst., 21(8):1162--1174, 2010.

Digital Library

[23]

W. Yu. A string-wise crdt for group editing. In Proceedings of the 17th ACM international conference on Supporting group work, GROUP '12, pages 141--144, New York, NY, USA, 2012. ACM.

Digital Library

Cited By

Adams MGriffis EPorter TSatish SZhao EOmar C(2025)Grove: A Bidirectionally Typed Collaborative Structure Editor CalculusProceedings of the ACM on Programming Languages10.1145/37049099:POPL(2176-2204)Online publication date: 9-Jan-2025
https://dl.acm.org/doi/10.1145/3704909
Matijević HVranić SKranjčić NCetl V(2024)Real-Time Co-Editing of Geographic FeaturesISPRS International Journal of Geo-Information10.3390/ijgi1312044113:12(441)Online publication date: 7-Dec-2024
https://doi.org/10.3390/ijgi13120441
Almeida P(2024)Approaches to Conflict-free Replicated Data TypesACM Computing Surveys10.1145/369524957:2(1-36)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1145/3695249
Show More Cited By

Index Terms

LSEQ: an adaptive structure for sequences in distributed collaborative editing
1. Applied computing
  1. Document management and text processing
    1. Document management
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Empirical software validation
  2. Software organization and properties
    1. Software functional properties
      1. Formal methods
    2. Software system structures
      1. Distributed systems organizing principles
        Organizing principles for web applications

Recommendations

Peritext: A CRDT for Collaborative Rich Text Editing
CSCW

Conflict-Free Replicated Data Types (CRDTs) support decentralized collaborative editing of shared data, enabling peer-to-peer sharing and flexible branching and merging workflows. While there is extensive work on CRDTs for plain text, much less is known ...
Moving elements in list CRDTs
PaPoC '20: Proceedings of the 7th Workshop on Principles and Practice of Consistency for Distributed Data

Conflict-free Replicated Data Types (CRDTs) for lists allow multiple users to concurrently insert and delete elements in a shared list object. However, existing algorithms behave poorly when users concurrently move list elements to a new position (i.e. ...
Evaluating CRDTs for real-time document editing
DocEng '11: Proceedings of the 11th ACM symposium on Document engineering

Nowadays, real-time editing systems are catching on. Tools such as Etherpad or Google Docs enable multiple authors at dispersed locations to collaboratively write shared documents. In such systems, a replication mechanism is required to ensure ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DocEng '13: Proceedings of the 2013 ACM symposium on Document engineering

September 2013

582 pages

ISBN:9781450317894

DOI:10.1145/2494266

Conference Chair:
Simone Marinai
University of Florence, Italy
,
Program Chair:
Kim Marriott
Monash University, Australia

Copyright © 2013 ACM.

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

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 September 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DocEng '13

Sponsor:

SIGWEB

DocEng '13: ACM Symposium on Document Engineering 2013

September 10 - 13, 2013

Florence, Italy

Acceptance Rates

DocEng '13 Paper Acceptance Rate 16 of 50 submissions, 32%;

Overall Acceptance Rate 194 of 564 submissions, 34%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
447
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)4

Reflects downloads up to 31 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Adams MGriffis EPorter TSatish SZhao EOmar C(2025)Grove: A Bidirectionally Typed Collaborative Structure Editor CalculusProceedings of the ACM on Programming Languages10.1145/37049099:POPL(2176-2204)Online publication date: 9-Jan-2025
https://dl.acm.org/doi/10.1145/3704909
Matijević HVranić SKranjčić NCetl V(2024)Real-Time Co-Editing of Geographic FeaturesISPRS International Journal of Geo-Information10.3390/ijgi1312044113:12(441)Online publication date: 7-Dec-2024
https://doi.org/10.3390/ijgi13120441
Almeida P(2024)Approaches to Conflict-free Replicated Data TypesACM Computing Surveys10.1145/369524957:2(1-36)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1145/3695249
Freudenthaler LChristakis MPradel M(2024)Decentralized Near-Synchronous Local-First Programming CollaborationProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3685555(1909-1911)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3685555
Da LKleppmann M(2024)Extending JSON CRDTs with Move OperationsProceedings of the 11th Workshop on Principles and Practice of Consistency for Distributed Data10.1145/3642976.3653030(8-14)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3642976.3653030
Stokkink QPouwelse J(2024)A Local-First Approach for Green Smart ContractsDistributed Ledger Technologies: Research and Practice10.1145/36071963:2(1-21)Online publication date: 18-Jun-2024
https://dl.acm.org/doi/10.1145/3607196
Zhou SLi YShang TKong W(2023)A Paradigm for Collaborative 3D Editing via List Conflict-free Replicated Data TypesProceedings of the 7th International Conference on Computer Science and Application Engineering10.1145/3627915.3627919(1-6)Online publication date: 17-Oct-2023
https://dl.acm.org/doi/10.1145/3627915.3627919
Bauwens JDe Porre KGonzalez Boix EGonzalez Boix ESutra P(2023)[Short paper] Towards improved collaborative text editing CRDTs by using Natural Language ProcessingProceedings of the 10th Workshop on Principles and Practice of Consistency for Distributed Data10.1145/3578358.3591330(51-55)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3578358.3591330
Yanakieva EBird PBieniusa AGonzalez Boix ESutra P(2023)A Study of Semantics for CRDT-based Collaborative SpreadsheetsProceedings of the 10th Workshop on Principles and Practice of Consistency for Distributed Data10.1145/3578358.3591324(37-43)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3578358.3591324
Barreto APaulino HSilva JPreguiça N(2023)PS-CRDTsFuture Generation Computer Systems10.1016/j.future.2022.12.013141:C(755-767)Online publication date: 15-Feb-2023
https://dl.acm.org/doi/10.1016/j.future.2022.12.013
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten