Abstract unordered and ordered trees CRDT

Stéphane Martin 1, * Mehdi Ahmed-Nacer 1 Pascal Urso 1
* Corresponding author
1 SCORE - Services and Cooperation
Inria Nancy - Grand Est, LORIA - NSS - Department of Networks, Systems and Services
Abstract : Trees are fundamental data structure for many areas of computer science and system engineering. In this report, we show how to ensure eventual consistency of optimistically replicated trees. In optimistic replication, the different replicas of a distributed system are allowed to diverge but should eventually reach the same value if no more mutations occur. A new method to ensure eventual consistency is to design Conflict-free Replicated Data Types (CRDT). In this report, we design a collection of tree CRDT using existing set CRDTs. The remaining concurrency problems particular to tree data structure are resolved using one or two layers of correction algorithm. For each of these layer, we propose different and independent policies. Any combination of set CRDT and policies can be constructed, giving to the distributed application programmer the entire control of the behavior of the shared data in face of concurrent mutations. We also propose to order these trees by adding a positioning layer which is also independent to obtain a collection of ordered tree CRDTs.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/hal-00648106
Contributor : Stéphane Martin <>
Submitted on : Monday, January 9, 2012 - 3:34:01 PM
Last modification on : Tuesday, December 18, 2018 - 4:26:01 PM
Long-term archiving on : Tuesday, December 13, 2016 - 8:50:54 PM

Files

RR-7825.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00648106, version 2
  • ARXIV : 1201.1784

Citation

Stéphane Martin, Mehdi Ahmed-Nacer, Pascal Urso. Abstract unordered and ordered trees CRDT. [Research Report] RR-7825, INRIA. 2011, pp.23. ⟨hal-00648106v2⟩

Share

Metrics

Record views

491

Files downloads

385