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 metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01248197
Contributor : Alain Monteil <>
Submitted on : Thursday, December 24, 2015 - 9:42:59 AM
Last modification on : Thursday, March 21, 2019 - 2:46:50 PM
Long-term archiving on : Friday, March 25, 2016 - 11:10:41 AM

File

Asynch%20rebalancing%20of%20a%...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01248197, version 1

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

Share

Metrics

Record views

446

Files downloads

94