Efficient state-based CRDTs by decomposition

• Type: Article in International Conference Proceedings Book
• Date: 2014

Authors

Almeida, PS (Author) Other; Shoker, A (Author) Other; Baquero, C (Author) Other

Conference proceedings International

Title: Proceedings of the 1st Workshop on the Principles and Practice of Eventual Consistency, PaPEC 2014

Pages: 3:1-3:2

1st Workshop on the Principles and Practice of Eventual Consistency, PaPEC 2014

Amsterdam, 13 April 2014 through 13 April 2014

Indexing

Scopus - 1 Citation

Other information

Authenticus ID: P-009-DNS

DOI: 10.1145/2596631.259663

Abstract (EN): Eventual consistency is a relaxed consistency model used in large-scale distributed systems that seek better availability when consistency can be delayed. CRDTs are distributed data types that make eventual consistency of a distributed object possible and non ad-hoc. Specifically, state-based CRDTs achieve this through shipping the entire replica state that is, eventually, merged to other replicas ensuring conver- gence. This imposes a large communication overhead when the replica size or the number of replicas gets larger. In this work, we introduce a decomposable version of state-based CRDTs, called Delta State-based CRDTs (¿-CRDT). A ¿-CRDT is viewed as a join of multiple fine-grained CRDTs of the same type, called deltas (¿). The deltas are produced by applying ¿-mutators, on a replica state, which are mod- ified versions of the original CRDT mutators. This makes it possible to ship small deltas (or batches) instead of ship- ping the entire state. The challenges are to make the join of deltas equivalent to the join of the entire object in clas- sical state-based CRDTs, and to find a way to derive the ¿-mutators. We address this challenge in this work, and we explore the minimal requirements that a communication al- gorithm must offer according to the guarantees provided by the underlying messaging middleware. Copyright © 2007 by the Association for Computing Machinery, Inc.

Language: English

Type (Professor's evaluation): Scientific