Skip to Main content Skip to Navigation
New interface
Conference papers

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
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Alain Monteil Connect in order to contact the contributor
Submitted on : Thursday, December 24, 2015 - 9:42:59 AM
Last modification on : Thursday, September 15, 2022 - 2:38:03 PM
Long-term archiving on: : Friday, March 25, 2016 - 11:10:41 AM


Files produced by the author(s)


  • HAL Id : hal-01248197, version 1


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. ⟨hal-01248197⟩



Record views


Files downloads