Asynchronous rebalancing of a replicated tree

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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.
Original languageUnknown
Title of host publicationConference Française de Systèmes d'Exploitation
Publication statusPublished - 1 Jan 2012
EventConference Française de Systèmes d'Exploitation -
Duration: 1 Jan 2011 → …


ConferenceConference Française de Systèmes d'Exploitation
Period1/01/11 → …

Cite this