Conflict-free Replicated Data Types

Abstract : Replicating data under Eventual Consistency (EC) allows any replica to accept updates without remote synchronisation. This ensures performance and scalability in large-scale distributed systems (e.g., clouds). However, published EC approaches are ad-hoc and error-prone. Under a formal Strong Eventual Consistency (SEC) model, we study sufficient conditions for convergence. A data type that satisfies these conditions is called a Conflict-free Replicated Data Type (CRDT). Replicas of any CRDT are guaranteed to converge in a self-stabilising manner, despite any number of failures. This paper formalises two popular approaches (state- and operation-based) and their relevant sufficient conditions. We study a number of useful CRDTs, such as sets with clean semantics, supporting both add and remove operations, and consider in depth the more complex Graph data type. CRDT types can be composed to develop large-scale distributed applications, and have interesting theoretical properties.
Type de document :
Communication dans un congrès
Xavier Défago and Franck Petit and Vincent Villain. SSS 2011 - 13th International Symposium Stabilization, Safety, and Security of Distributed Systems, Oct 2011, Grenoble, France. Springer, 6976, pp.386-400, 2011, Lecture Notes in Computer Science. 〈10.1007/978-3-642-24550-3_29〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00932836
Contributeur : Marc Shapiro <>
Soumis le : vendredi 17 janvier 2014 - 17:46:30
Dernière modification le : vendredi 25 mai 2018 - 12:02:03
Document(s) archivé(s) le : vendredi 18 avril 2014 - 11:53:09

Fichier

CRDTs_SSS-2011.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski. Conflict-free Replicated Data Types. Xavier Défago and Franck Petit and Vincent Villain. SSS 2011 - 13th International Symposium Stabilization, Safety, and Security of Distributed Systems, Oct 2011, Grenoble, France. Springer, 6976, pp.386-400, 2011, Lecture Notes in Computer Science. 〈10.1007/978-3-642-24550-3_29〉. 〈hal-00932836〉

Partager

Métriques

Consultations de la notice

557

Téléchargements de fichiers

393