Skip to Main content Skip to Navigation
New interface
Reports (Research report)

An optimized conflict-free replicated set

Abstract : Eventual consistency of replicated data supports concurrent updates, reduces latency and improves fault tolerance, but forgoes strong consistency. Accordingly, several cloud computing platforms implement eventually-consistent data types. The set is a widespread and useful abstraction, and many replicated set designs have been proposed. We present a reasoning abstraction, \emph{permutation equivalence}, that systematizes the characterization of the expected concurrency semantics of concurrent types. Under this framework we present one of the existing conflict-free replicated data types, Observed-Remove Set. Furthermore, in order to decrease the size of meta-data, we propose a new optimization to avoid tombstones. This approach that can be transposed to other data types, such as maps, graphs or sequences.
Complete list of metadata
Contributor : Marc Shapiro Connect in order to contact the contributor
Submitted on : Tuesday, October 9, 2012 - 6:38:03 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:45 AM
Long-term archiving on: : Friday, December 16, 2016 - 9:32:02 PM


Files produced by the author(s)


  • HAL Id : hal-00738680, version 1
  • ARXIV : 1210.3368


Annette Bieniusa, Marek Zawirski, Nuno Preguiça, Marc Shapiro, Carlos Baquero, et al.. An optimized conflict-free replicated set. [Research Report] RR-8083, INRIA. 2012, pp.12. ⟨hal-00738680⟩



Record views


Files downloads