High Responsiveness for Group Editing CRDTs

Simple item page
dc.contributor.authorBriot, Loïck
dc.contributor.authorUrso, Pascal
dc.contributor.authorShapiro, Marc
dc.date.accessioned2023-03-17T22:48:57Z
dc.date.available2023-03-17T22:48:57Z
dc.date.issued2016
dc.description.abstractGroup 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.doi10.1145/2957276.2957300
dc.identifier.urihttps://dl.eusset.eu/handle/20.500.12015/4586
dc.language.isoen
dc.publisherAssociation for Computing Machinery
dc.relation.ispartofProceedings of the 2016 ACM International Conference on Supporting Group Work
dc.subjectcrdt
dc.subjectlinear data structure
dc.subjecttombstones management
dc.titleHigh Responsiveness for Group Editing CRDTsen
dc.typeText/Conference Paper
gi.citation.startPage51–60
gi.conference.locationSanibel Island, Florida, USA

Files

Collections

GROUP 2016