Efficient state-based CRDTs by decomposition

Abstract

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 (d-CRDT). A d-CRDT is viewed as a join of multiple fine-grained CRDTs of the same type, called deltas (d). The deltas are produced by applying d-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 d-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.