Conflict-free replicated data type

In distributed computing, a conflict-free replicated data type (abbreviated CRDT) is a type of specially-designed data structure used to achieve strong eventual consistency (SEC) and monotonicity (absence of rollbacks) . As their name indicates, a CRDT instance is distributed into several replicas; each replica can be mutated promptly and concurrently; the potential divergence between replicas is however guaranteed to be eventually reconciled through downstream synchronisation (off the critical path); consequently CRDTs are known to be highly available.

There are two alternative routes to ensure SEC: operation-based CRDTs and state-based CRDTs . The two alternatives are equivalent, as one can emulate the other, but there is a tradeoff: operation-based CRDTs require additional guarantees from the whereas state-based CRDTs have a high dissemination overhead, as the entire state must be disseminated. Delta state CRDTs (or simply Delta CRDTs) are optimised state-based CRDTs where only recently applied mutations to a state are disseminated instead of the entire state. Pure operation-based CRDTs are also an improved variant of operation-based CRDTs that reduce the meta-data size through exploiting the causality information of the middleware.

CRDTs are used to replicate data across multiple computers in a network, executing updates without the need for remote synchronization. This would lead to merge conflicts in systems using conventional eventual consistency technology, but CRDTs are designed such that conflicts are mathematically impossible. Under the constraints of the CAP theorem they provide the strongest consistency guarantees for available/partition-tolerant (AP) settings. In contrast, consensus protocols such as Paxos are required for strongly-consistent/partition-tolerant (CP) settings.

The CRDT concept was first formally defined in 2007 by Marc Shapiro and Nuno Preguiça in terms of operation commutativity, and development was initially motivated by collaborative text editing. The concept of semilattice evolution of replicated states was first defined by Baquero and Moura in 1997, and development was initially motivated by mobile computing. The two concepts were later unified in 2011. Precursor ideas can be traced back as far as 1990

...
Wikipedia