A commutative replicated data type for cooperative editing

Abstract : A Commutative Replicated Data Type (CRDT) is one where all concurrent operations commute. The replicas of a CRDT converge automatically, without complex concurrency control. This paper describes Treedoc, a novel CRDT design for cooperative text editing. An essential property is that the identifiers of Treedoc atoms are selected from a dense space. We discuss practical alternatives for implementing the identifier space based on an extended binary tree. We also discuss storage alternatives for data and meta-data, and mechanisms for compacting the tree. In the best case, Treedoc incurs no overhead with respect to a linear text buffer. We validate the results with traces from existing edit histories.
Type de document :
Communication dans un congrès
29th IEEE International Conference on Distributed Computing Systems (ICDCS 2009), Jun 2009, Montreal, Québec, Canada. IEEE Computer Society, pp.395-403, 2009, 〈10.1109/ICDCS.2009.20〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00445975
Contributeur : Brigitte Briot <>
Soumis le : lundi 11 janvier 2010 - 16:24:45
Dernière modification le : lundi 29 mai 2017 - 14:25:07
Document(s) archivé(s) le : vendredi 18 juin 2010 - 00:41:55

Fichier

icdcs09-treedoc.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Nuno Preguiça, Joan Manuel Marquès, Marc Shapiro, Mihai Leția. A commutative replicated data type for cooperative editing. 29th IEEE International Conference on Distributed Computing Systems (ICDCS 2009), Jun 2009, Montreal, Québec, Canada. IEEE Computer Society, pp.395-403, 2009, 〈10.1109/ICDCS.2009.20〉. 〈inria-00445975〉

Partager

Métriques

Consultations de
la notice

459

Téléchargements du document

7320