Conference Paper

High Responsiveness for Group Editing CRDTs

Thumbnail Image

Fulltext URI

Document type

Text/Conference Paper

Additional Information

Date

2016

Authors

Briot, Loïck
Urso, Pascal
Shapiro, Marc

Journal Title

Journal ISSN

Volume Title

Source

Proceedings of the 2016 ACM International Conference on Supporting Group Work

Publisher

Association for Computing Machinery

Abstract

Group editing is a crucial feature for many end-user applications. It requires high responsiveness, which can be provided only by optimistic replication algorithms, which come in two classes: classical Operational Transformation (OT), or more recent Conflict-Free Replicated Data Types (CRDTs).Typically, CRDTs perform better on downstream operations, i.e., when merging concurrent operations than OT, because the former have logarithmic complexity and the latter quadratic. However, CRDTs are often less responsive, because their upstream complexity is linear. To improve this, this paper proposes to interpose an auxiliary data structure, called the identifier data structure in front of the base CRDT. The identifier structure ensures logarithmic complexity and does not require replication or synchronization. Combined with a block-wise storage approach, this approach improves upstream execution time by several orders of magnitude, with negligeable impact on memory occupation, network bandwidth, and downstream execution performance.

Description

Briot, Loïck; Urso, Pascal; Shapiro, Marc (2016): High Responsiveness for Group Editing CRDTs. Proceedings of the 2016 ACM International Conference on Supporting Group Work. DOI: 10.1145/2957276.2957300. Association for Computing Machinery. pp. 51–60. Sanibel Island, Florida, USA

Keywords

crdt, linear data structure, tombstones management

Citation

DOI

10.1145/2957276.2957300

URI

URI

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

Collections

GROUP 2016

Endorsement

Review

Supplemented By

Referenced By

Number of citations to item: 15

  • Hyun-Gul Roh, Changsung Kim, Jaemin Woo, Siwan Kim (2017): Kaleido: Implementing a Novel Data System for Multi-Device Synchronization, In: 2017 18th IEEE International Conference on Mobile Data Management (MDM), doi:10.1109/mdm.2017.46
  • Geoffrey Litt, Sarah Lim, Martin Kleppmann, Peter van Hardenberg (2022): Peritext: A CRDT for Collaborative Rich Text Editing, In: Proceedings of the ACM on Human-Computer Interaction CSCW2(6), doi:10.1145/3555644
  • Matthieu Nicolas, Gérald Oster, Olivier Perrin (2020): Efficient renaming in sequence CRDTs, In: Proceedings of the 7th Workshop on Principles and Practice of Consistency for Distributed Data, doi:10.1145/3380787.3393682
  • Xiao Lv, Fazhi He, Weiwei Cai, Yuan Cheng, Yiqi Wu (2017): CRDT-based Conflict Detection and Resolution for Massive-scale Real-time Collaborative CAD systems, In: Proceedings of the 12th Chinese Conference on Computer Supported Cooperative Work and Social Computing, doi:10.1145/3127404.3127436
  • Matthieu Nicolas, Gerald Oster, Olivier Perrin (2022): Efficient Renaming in Sequence CRDTs, In: IEEE Transactions on Parallel and Distributed Systems 12(33), doi:10.1109/tpds.2022.3172570
  • Bo Qin, Peng Peng, Jian Zhang, Hongwei Wang, Ke Ma (2023): A framework and prototype system in support of workflow collaboration and knowledge mining for manufacturing value chains, In: IET Collaborative Intelligent Manufacturing 1(5), doi:10.1049/cim2.12073
  • 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
  • Xiao Lv, Fazhi He, Weiwei Cai, Yuan Cheng (2018): Supporting selective undo of string-wise operations for collaborative editing systems, In: Future Generation Computer Systems, doi:10.1016/j.future.2017.11.046
  • Xiao Lv, Fazhi He, Xiaohu Yan, Yiqi Wu, Yuan Cheng (2019): Integrating selective undo of feature-based modeling operations for real-time collaborative CAD systems, In: Future Generation Computer Systems, doi:10.1016/j.future.2019.05.021
  • 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
  • Elena Yanakieva, Philipp Bird, Annette Bieniusa (2023): A Study of Semantics for CRDT-based Collaborative Spreadsheets, In: Proceedings of the 10th Workshop on Principles and Practice of Consistency for Distributed Data, doi:10.1145/3578358.3591324
  • Emin Karayel, Edgar Gonzàlez (2022): Strong eventual consistency of the collaborative editing framework WOOT, In: Distributed Computing 2(35), doi:10.1007/s00446-021-00414-6
  • Victor Grishchenko, Mikhail Patrakeev (2020): Chronofold, In: Proceedings of the 7th Workshop on Principles and Practice of Consistency for Distributed Data, doi:10.1145/3380787.3393680
  • Tim Jungnickel, Ronny Bräunlich (2017): formic: Building Collaborative Applications with Operational Transformation, In: Lecture Notes in Computer Science, doi:10.1007/978-3-319-59665-5_10
  • 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
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