Conflict-free Replicated Data Types (2011)
December 31, 2023In a distributed system with replicated objects distributed across processes interconnected by an asynchronous network, updating a replica without synchronization can lead to conflicts when the update is sent to other replicas. Conflict-free Replicated Data Types (CRDTs) are data structures whose states form a join semilattice and monotonically non-decreasing across updates. The replicas of CRDTs that have delivered the same updates eventually reach the same state if clents stop submitting updates.
The processes in this system are assumed to be non-Byzantine and may crash silently, remaining crashed forever or recovering.
Clients can read the state of an object using queries (\(q\)) and modify it using updates (\(u\)). The merge operation (\(m\)) combines the state of a remote replica. Queries are side-effect-free. The \(k^{\text{th}}\) method execution at replica \(i\) is denoted as \(f^k_i(a)\), where \(f\) is either \(q,\ u\ \) or \(m\), and \(a\). \(a\) denotes the arguments. Replica \(i\) has initial state \(s^0_i\), and \(f^k_i(a)\) make a transition from \(s^{k-1}_i\) to \(s^k_i\). This transition is noted as \(s^{k-1}_i\bullet f^k_i(a)=s_i^k\).
There are two types of CRDTs: State-based Convergent Replicated Data Types (CvRDTs) and Operation-based Commutative Replicated Data Types (CmRDTs). CvRDTs and CmRDTs are equivalent, meaning any CvRDT can be emulated by a CmRDT, and vice versa.
CvRDTs use merge methods, whereas CmRDTs do not. A join semilattice is a partial order \(\le\) with a least upper bound \(\sqcup\) for all pairs of states \((s, s’)\). It follows that \(\sqcup\) is commutative \((s\sqcup s’ = s’\sqcup s)\), idempotent \((s \sqcup s = s)\) and associative \(((s\sqcup s’)\sqcup s’’ = s\sqcup (s’ \sqcup s’’))\). Merging state \(s\) with remote state \(s’\) computes the least upper bound of the two states, i.e., \(s\bullet m(s’) = s\sqcup s’\), and any states are monotonically non-decreasing across updates, i.e., \(s\le s\bullet u\). In that case, correct replicas that have delivered the same updates have equivalent state.