CvRDT

CvRDT, or convergent replicated data type, is a category of CRDTs designed for eventual consistency in distributed systems. In a CvRDT, every replica stores a local state drawn from a lattice and updates are propagated by merging states using a join operation. Because the join is commutative, associative and idempotent, replicas that receive updates in different orders converge to the same state—the least upper bound of all observed updates.

CvRDTs require no coordination for updates. Each replica updates its local state, then periodically or asynchronously sends its state to other replicas; upon receipt, a replica merges the incoming state with its own via the lattice join. The result is monotonic growth in the lattice; merges cannot undo previously observed information, guaranteeing convergence even under partitions and message loss.

Data types implemented as CvRDTs are constructed as lattices. Common examples include grow-only sets (G-Set) with union as join, and counters like the G-Counter where each replica maintains a per-replica counter and the merge takes the elementwise maximum. More sophisticated CvRDTs encode state so that operations appear to be atomic updates, while still maintaining convergence via join.

Benefits of CvRDTs include high availability and partition tolerance, simple conflict resolution, and deterministic convergence independent of message order. Limitations include potential state growth and inefficiency for large histories, and some operations (such as arbitrary deletes) may be difficult to express solely with monotonic joins.

See also: CRDT, OR-Set, G-Counter, PN-Counter, state-based CRDTs.