Abstract unordered and ordered trees CRDT

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.

Data and Resources

Additional Info

Field Value
Source https://inria.hal.science/hal-00648106
Author Martin, Stéphane, Ahmed-Nacer, Mehdi, Urso, Pascal
Maintainer CCSD
Last Updated November 9, 2026, 11:47 (UTC)
Created November 9, 2026, 11:47 (UTC)
Identifier Report N°: RR-7825
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Services and Cooperation (SCORE) ; Centre Inria de l'Université de Lorraine ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Networks, Systems and Services (LORIA - NSS) ; Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) ; Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA) ; Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)
creator Martin, Stéphane
date 2011-12-05T00:00:00
harvest_object_id c62ce090-9f1b-4070-bbd2-8c54a7465899
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-11-04T00:00:00
relation info:eu-repo/semantics/altIdentifier/arxiv/1201.1784
set_spec type:REPORT