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.
|Title of host publication||Conference Française de Systèmes d'Exploitation|
|Publication status||Published - 1 Jan 2012|
|Event||Conference Française de Systèmes d'Exploitation - |
Duration: 1 Jan 2011 → …
|Conference||Conference Française de Systèmes d'Exploitation|
|Period||1/01/11 → …|