High Responsiveness for Group Editing CRDTs
Fulltext URI
Document type
Additional Information
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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
Keywords
Citation
URI
Collections
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