High Responsiveness for Group Editing CRDTs
| dc.contributor.author | Briot, Loïck | |
| dc.contributor.author | Urso, Pascal | |
| dc.contributor.author | Shapiro, Marc | |
| dc.date.accessioned | 2023-03-17T22:48:57Z | |
| dc.date.available | 2023-03-17T22:48:57Z | |
| dc.date.issued | 2016 | |
| dc.description.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. | en |
| dc.identifier.doi | 10.1145/2957276.2957300 | |
| dc.identifier.uri | https://dl.eusset.eu/handle/20.500.12015/4586 | |
| dc.language.iso | en | |
| dc.publisher | Association for Computing Machinery | |
| dc.relation.ispartof | Proceedings of the 2016 ACM International Conference on Supporting Group Work | |
| dc.subject | crdt | |
| dc.subject | linear data structure | |
| dc.subject | tombstones management | |
| dc.title | High Responsiveness for Group Editing CRDTs | en |
| dc.type | Text/Conference Paper | |
| gi.citation.startPage | 51–60 | |
| gi.citations.count | 15 | |
| gi.citations.element | 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 | |
| gi.citations.element | 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 | |
| gi.citations.element | 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 | |
| gi.citations.element | 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 | |
| gi.citations.element | 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 | |
| gi.citations.element | 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 | |
| gi.citations.element | 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 | |
| gi.citations.element | 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 | |
| gi.citations.element | 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 | |
| gi.citations.element | 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 | |
| gi.citations.element | 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 | |
| gi.citations.element | 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 | |
| gi.citations.element | 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 | |
| gi.citations.element | 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 | |
| gi.citations.element | 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 | |
| gi.conference.location | Sanibel Island, Florida, USA |