A comprehensive study of Convergent and Commutative Replicated Data Types

Résumé : La cohérence à terme vise à assurer que les répliques d'un objet partagé modifiable convergent sans synchronisation à priori. Les approches antérieures du problème sont \emph{ad-hoc} et sujettes à erreur. Nous proposons une approche basée sur des principes formels\,: baser la conception des types de données sur des propriétés mathématiques simples, suffisantes pour garantir la cohérence à terme. Nous appelons ces types de données des CRDT (Convergent/Commutative Replicated Data Types). Ce papier fournit formalise la réplication asynchrone, qu'elle soit basée sur l'état ou sur les opérations, et fournit une condition suffisante adaptée à chacun de ces cas. Il décrit plusieurs CRDT utiles, dont des contenants permettant les opérations add et remove avec une sémantique propre, et des types de données plus complexes comme les graphes, les graphes acycliques monotones, et les séquences. Il contient une discussion de propriétés dont on a besoin pour mettre en œuvre des CRDT non triviaux.
Type de document :
Rapport
[Research Report] RR-7506, Inria – Centre Paris-Rocquencourt; INRIA. 2011, pp.50


https://hal.inria.fr/inria-00555588
Contributeur : Marc Shapiro <>
Soumis le : jeudi 13 janvier 2011 - 19:34:51
Dernière modification le : vendredi 16 septembre 2016 - 15:19:26
Document(s) archivé(s) le : mardi 6 novembre 2012 - 11:25:57

Fichier

techreport.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00555588, version 1

Collections

Citation

Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski. A comprehensive study of Convergent and Commutative Replicated Data Types. [Research Report] RR-7506, Inria – Centre Paris-Rocquencourt; INRIA. 2011, pp.50. <inria-00555588>

Exporter

Partager

Métriques

Consultations de
la notice

6102

Téléchargements du document

53133