Abstract unordered and ordered trees CRDT

Stéphane Martin 1, * Mehdi Ahmed-Nacer 1 Pascal Urso 1
* Auteur correspondant
1 SCORE - Services and Cooperation
Inria Nancy - Grand Est, LORIA - NSS - Department of Networks, Systems and Services
Résumé : Les arbres sont une structure de donnée fondamentale dans beaucoup de domaines de l'informatique théorique et de l'ingénierie logicielle. Dans ce rapport, nous montrons comment assurer la consistance d'arbres répliqués de manière optimiste. Dans la réplication optimiste, les différentes répliques d'un système distribué peuvent passer par différents états intermédiaires avant de converger. Une nouvelle méthode pour assurer la convergence est de définir des CRDT (Conflict-free Replicated Data Types). Dans ce rapport, nous proposons une collection de CRDT structure d'arbres en utilisant les CRDT ensembles déjà existants. Nous assurons la cohérence de la structure de données en présence de mutations concurrentes, en utilisant un algorithme de réparation en une ou deux phases. Pour chacune de ces phases, nous proposons plusieurs politiques de réparations indépendantes. Nous donnons ainsi le choix au développeur de l'application distribuée le contrôle total sur le comportement de l'arbre partagé lors de modifications concurrentes. Enfin, nous proposons d'utiliser des résultats connus et nouveaux sur les CRDT séquences ordonnés, pour ajoutant des informations de positionnement sur les noeuds ou les arêtes de l'arbre. Nous définissons ainsi des CRDT de structure d'arbres ou les noeuds frères sont ordonnées.
Type de document :
Rapport
[Research Report] RR-7825, INRIA. 2011, pp.23
Liste complète des métadonnées

https://hal.inria.fr/hal-00648106
Contributeur : Stéphane Martin <>
Soumis le : lundi 9 janvier 2012 - 15:34:01
Dernière modification le : jeudi 11 janvier 2018 - 06:23:13
Document(s) archivé(s) le : mardi 13 décembre 2016 - 20:50:54

Fichiers

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

Identifiants

  • HAL Id : hal-00648106, version 2
  • ARXIV : 1201.1784

Citation

Stéphane Martin, Mehdi Ahmed-Nacer, Pascal Urso. Abstract unordered and ordered trees CRDT. [Research Report] RR-7825, INRIA. 2011, pp.23. 〈hal-00648106v2〉

Partager

Métriques

Consultations de la notice

458

Téléchargements de fichiers

299