Convergent and Commutative Replicated Data Types

Abstract : Eventual consistency aims to ensure that replicas of some mutable shared object converge without foreground synchronisation. Previous approaches to eventual consistency are ad-hoc and error-prone. We study a principled approach: to base the design of shared data types on some simple formal conditions that are sufficient to guarantee eventual consistency. We call these types Convergent or Commutative Replicated Data Types (CRDTs). This paper formalises asynchronous object replication, either state based or oper- ation based, and provides a sufficient condition appropriate for each case. It describes several useful CRDTs, including container data types supporting both add and remove operations with clean semantics, and more complex types such as graphs and monotonic DAGs. It discusses some properties needed to implement non-trivial CRDTs.
Type de document :
Article dans une revue
Bulletin- European Association for Theoretical Computer Science, European Association for Theoretical Computer Science; 1999, 2011, pp.67-88. 〈http://www.eatcs.org/images/bulletin/beatcs104.pdf〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00932833
Contributeur : Marc Shapiro <>
Soumis le : vendredi 17 janvier 2014 - 17:36:46
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : vendredi 18 avril 2014 - 11:52:57

Fichier

CRDTs-beatcs-2011-06.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00932833, version 1

Collections

Citation

Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski. Convergent and Commutative Replicated Data Types. Bulletin- European Association for Theoretical Computer Science, European Association for Theoretical Computer Science; 1999, 2011, pp.67-88. 〈http://www.eatcs.org/images/bulletin/beatcs104.pdf〉. 〈hal-00932833〉

Partager

Métriques

Consultations de la notice

536

Téléchargements de fichiers

671