A comprehensive study of Convergent and Commutative Replicated Data Types
📜 Abstract
Eventual consistency aims to ensure that replicas of some mutable shared object converge without foreground synchronisation. Previous approaches to eventual consistency are ad-hoc and error-prone. We study a principled approach: to base the design of shared data types on some simple formal conditions that are sufficient to guarantee eventual consistency. We call these types Convergent or Commutative Replicated Data Types (CRDTs). This paper formalises asynchronous object replication, either state based or operation based, and provides a sufficient condition appropriate for each case. It describes several useful CRDTs, including container data types supporting both add and remove operations with clean semantics, and more complex types such as graphs, montonic DAGs, and sequences. It discusses some properties needed to implement non-trivial CRDTs.
✨ Summary
The paper establishes a formal framework for replicated data types that converge without foreground synchronization. It distinguishes two approaches: state-based CRDTs, whose replica states form a monotonic join-semilattice and merge computes a least upper bound, and operation-based CRDTs, whose concurrent operations commute under an appropriate delivery order. The authors formalize eventual convergence, specify replication assumptions, and show that the two approaches can emulate one another.
The paper develops a portfolio of CRDT designs, including counters, last-writer-wins and multi-value registers, grow-only and add/remove sets, graphs, monotonic DAGs, and sequence structures such as RGA and continuum-based sequences. It emphasizes that convergence alone does not determine application semantics: data types must explicitly define the treatment of concurrent updates. The paper also identifies metadata growth, tombstones, identifier imbalance, and garbage collection as important implementation concerns. Some garbage collection can use weak background synchronization, while global resets and similar operations may require stronger commitment protocols.
The work helped establish CRDTs as a standard research framework for coordination-free replication. Later research formalized and surveyed CRDT properties, including deterministic convergence after replicas receive the same updates. (arxiv.org) Subsequent systems research applied CRDTs to consistency-level selection and to coordination-free programming frameworks; for example, SIEVE used causally consistent CRDTs when strong consistency was unnecessary, while Lasp used CRDTs including G-Counters for large-scale coordination-free applications. (usenix.org) The paper’s designs and terminology therefore influenced both theoretical work on replicated data types and practical distributed-storage and programming-system designs.