  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; whereas operation-based CRDTs disseminate
operations (i.e., small states) assuming an exactly-once reliable dissemination
layer. We introduce Delta State Conflict-Free Replicated Data Types
($\delta$-CRDTs) 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 to be joined with 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 for eventual convergence, and
another one that ensures causal consistency. Finally, we introduce several
$\delta$-CRDT specifications of both well-known replicated datatypes and novel
datatypes, including a generic map composition.
