CRDTs are distributed data types that make eventual consistency of a distributed object possible and non ad-hoc. Specifically, state-based CRDTs achieve this by sharing local state changes through shipping the entire state, that is then merged to other replicas with an idempotent, associative, and commutative join operation, ensuring convergence.This imposes a large communication overhead as the state size becomes larger. We introduce Delta State Conflict-Free Replicated Datatypes ({\delta}-CRDT) , which make use of \delta%DIFDELCMD < }%%% -mutators, defined in such a way to return a delta-state, typically, with a much smaller size than the full state. Delta-states are joined to the local state as well as to the remote states (after being shipped). This can achieve the best of both worlds: small messages with an incremental nature, as in operation-based CRDTs, disseminated over unreliable communication channels, as in traditional state-based CRDTs.  } We introduce the {\delta}-CRDT framework, and we explain it through establishing a correspondence to current state- based CRDTs. In addition, we present two anti-entropy algorithms: a basic one that provides eventual convergence, and another one that ensures both convergence and causal consistency. We also introduce two {\delta}-CRDT specifications of well-known replicated datatypes.
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 en- tire state, that may be large, and merging it to other replicas ; whereas operation-based CRDTs disseminate operations (i.e., small states) assuming an exactly-once reliable dissemination layer. We introduce Delta State Conflict-Free Replicated Datatypes ({\delta}-CRDT) %DIFDELCMD < }%%% that can achieve the best of both worlds: 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 \delta}-mutators to return a delta-state, typically with a much smaller size than the full state, that is joined to both: local and remote states. We introduce the {\delta}-CRDT framework, and we explain it through establishing a correspondence to current state-based CRDTs. In addition, we present an anti-entropy algorithm that ensures causal consistency, and we introduce two {\delta}-CRDT specifications of well-known replicated datatypes.
R
achieve this by sharing local state changes through shipping the entire
ensure convergence through disseminating the en- tire
R
is then merged
may be large, and merging it
R
with an idempotent, associative, and commutative join operation, ensuring convergence.This imposes a large communication overhead as the state size becomes larger.
; whereas operation-based CRDTs disseminate operations (i.e., small states) assuming an exactly-once reliable dissemination layer.
D
, which make use of
D
\delta
R
-mutators, defined in such a way to return a delta-state, typically, with a much smaller size than the full state. Delta-states are joined to the local state as well as to the remote states (after being shipped). This
that
A
This is achieved by defining
A
\delta
A
-mutators to return a delta-state, typically with a much smaller size than the full state, that is joined to both: local and remote states.
R
state- based
state-based
R
two
an
R
algorithms: a basic one that provides eventual convergence, and another one that ensures both convergence and causal consistency. We also
algorithm that ensures causal consistency, and we