Conflict-free Replicated Data Types

Résumé : La réplication selon la politique de cohérence à terme (Eventual Consistency ou EC) autorise toute réplique à accepter des mises à jour sans se synchroniser avec les autres. Cette approche ne bride pas les performances et permet le passage à l'échelle dans les systèmes distribués, par ex. dans l'informatique en nuage. Cependant, les algorithmes EC précédemment publiés sont ad-hoc et sujets aux erreurs. Nous proposons un modèle formel, la cohérence à terme forte (Strong Eventual Consistency ou SEC), dans lequel nous étudions des conditions suffisantes de converegence. Un type de données satisfaisant ces conditions sera dit sans conflit (Conflict-free Replicated Data Type ou CRDT). Les répliques d'un CRDT convergent de façon auto-stabilisante, quel que soit le nombre de fautes. Cet article formalise deux approches courantes, celle basée sur les états et celle basée sur les données, et les conditions suffisantes correspondantes. Nous étudions un certain nombre de CRDT génériques, comme des ensembles, avec une sémantique appropriée pour les opérations add et remove, et approfondissons un type plus complexe, le graphe. Les CRDT peuvent être composés, de façon à développer des applications réparties à grande échelle, et ont des propriétés théoriques intéressantes.
Type de document :
Rapport
[Research Report] RR-7687, INRIA. 2011, pp.18
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00609399
Contributeur : Marek Zawirski <>
Soumis le : samedi 27 août 2011 - 03:40:05
Dernière modification le : vendredi 25 mai 2018 - 12:02:03
Document(s) archivé(s) le : dimanche 4 décembre 2016 - 21:40:43

Fichier

RR-7687.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00609399, version 2

Collections

Citation

Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski. Conflict-free Replicated Data Types. [Research Report] RR-7687, INRIA. 2011, pp.18. 〈inria-00609399v2〉

Partager

Métriques

Consultations de la notice

1283

Téléchargements de fichiers

4778