High Responsiveness for Group Editing CRDTs

Loïck Briot 1 Pascal Urso 1 Marc Shapiro 2
1 COAST - Web Scale Trustworthy Collaborative Service Systems
Inria Nancy - Grand Est, LORIA - NSS - Department of Networks, Systems and Services
2 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
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.
Type de document :
Communication dans un congrès
ACM International Conference on Supporting Group Work, Nov 2016, Sanibel Island, FL, United States. 〈10.1145/2957276.2957300〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01343941
Contributeur : Pascal Urso <>
Soumis le : lundi 11 juillet 2016 - 09:49:40
Dernière modification le : jeudi 11 janvier 2018 - 06:28:03

Fichier

camera-ready-2016-06-27.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Loïck Briot, Pascal Urso, Marc Shapiro. High Responsiveness for Group Editing CRDTs. ACM International Conference on Supporting Group Work, Nov 2016, Sanibel Island, FL, United States. 〈10.1145/2957276.2957300〉. 〈hal-01343941〉

Partager

Métriques

Consultations de la notice

431

Téléchargements de fichiers

401