Delta state replicated data types

Citation data:

Journal of Parallel and Distributed Computing, ISSN: 0743-7315, Vol: 111, Page: 162-173

Publication Year:
2018
Usage 7
Abstract Views 6
Link-outs 1
Captures 38
Readers 38
Social Media 38
Tweets 35
Shares, Likes & Comments 3
DOI:
10.1016/j.jpdc.2017.08.003
Author(s):
Paulo Sérgio Almeida; Ali Shoker; Carlos Baquero
Publisher(s):
Elsevier BV
Tags:
Computer Science; Mathematics
Most Recent Tweet View All Tweets
article description
Conflict-free Replicated Data Types (CRDTs) are distributed data types that make eventual consistency of a distributed object possible and non ad-hoc. Specifically, state-based CRDTs ensure convergence through disseminating the entire state, that may be large, and merging it to other replicas. We introduce Delta State Conflict-Free Replicated Data Types ( δ -CRDT) that can achieve the best of both operation-based and state-based CRDTs: small messages with an incremental nature, as in operation-based CRDTs, disseminated over unreliable communication channels, as in traditional state-based CRDTs. This is achieved by defining δ - mutators to return a delta-state, typically with a much smaller size than the full state, that to be joined with both local and remote states. We introduce the δ -CRDT framework, and we explain it through establishing a correspondence to current state-based CRDTs. In addition, we present an anti-entropy algorithm for eventual convergence, and another one that ensures causal consistency. Finally, we introduce several δ -CRDT specifications of both well-known replicated datatypes and novel datatypes, including a generic map composition.