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 metadatas

https://hal.inria.fr/hal-00738680
Contributor : Marc Shapiro <>
Submitted on : Tuesday, October 9, 2012 - 6:38:03 PM
Last modification on : Thursday, March 21, 2019 - 1:07:29 PM
Long-term archiving on : Friday, December 16, 2016 - 9:32:02 PM

Files

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

Identifiers

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

Citation

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⟩

Share

Metrics

Record views

437

Files downloads

1167