Asynchronous rebalancing of a replicated tree

Abstract : We study the problem of rebalancing a replicated tree, while the tree is concurrently being updated in a P2P manner. Tree updates are asynchronous and commutative, as we aim at eventual consistency. However, rebalancing requires strong synchronisation, because only replicas that have performed the same rebalances can communicate with one another. In order to scale to large networks, we propose to break this synchronisation into two parts: commitment within a small core of replicas, followed by asynchronous, pairwise catch-up protocol between replicas at different rebalance numbers. We state the requirements and correctness conditions for this distributed algorithm, and propose a correct solution. Keywords: replicated tree, collaborative editing, garbage collection, distributed systems
Type de document :
Communication dans un congrès
Conférence Française en Systèmes d'Exploitation (CFSE), May 2011, Saint-Malo, France. pp.12, 2011
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01248197
Contributeur : Alain Monteil <>
Soumis le : jeudi 24 décembre 2015 - 09:42:59
Dernière modification le : vendredi 25 mai 2018 - 12:02:04
Document(s) archivé(s) le : vendredi 25 mars 2016 - 11:10:41

Fichier

Asynch%20rebalancing%20of%20a%...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01248197, version 1

Collections

Citation

Marek Zawirski, Marc Shapiro, Nuno Preguiça. Asynchronous rebalancing of a replicated tree. Conférence Française en Systèmes d'Exploitation (CFSE), May 2011, Saint-Malo, France. pp.12, 2011. 〈hal-01248197〉

Partager

Métriques

Consultations de la notice

313

Téléchargements de fichiers

76