Papers
Conflict-free Replicated Data Types
Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski · SSS 2011 (Stabilization, Safety, and Security of Distributed Systems), 2011
The problem: replicating without synchronizing, but without ad hoc conflicts
Traditional strong consistency serializes all updates into a single total global order. This becomes a performance and scalability bottleneck and, by the CAP theorem, conflicts with availability and partition tolerance. That is why, in scenarios with high network latency or partitions (cloud computing, P2P networks, disconnected operation), eventual consistency (EC) is attractive: an update runs on one replica without synchronization, is sent to the others later, and all of them end up being applied at every replica, asynchronously and possibly in different orders. The cost is that concurrent updates can conflict, and arbitrating the conflict may require consensus and undoing operations (roll-back). The authors observe that the literature gives little guidance on designing a correct optimistic system: published EC approaches are ad hoc, brittle, and error-prone, and they cite the concurrency anomalies of the Amazon shopping cart as an example. The paper's proposal is a theoretically grounded approach: instead of resolving conflicts afterward, choose data types whose mathematical properties (monotonicity in a semilattice and/or commutativity) guarantee that there are no conflicts. A trivial example given is a replicated counter, which converges because incrementing and decrementing commute, assuming no overflow.
Strong Eventual Consistency: immediate convergence among those who have seen the same updates
The paper formalizes eventual consistency with three requirements: eventual delivery (an update delivered to a correct replica eventually reaches all correct replicas), convergence (correct replicas that have delivered the same updates eventually reach equivalent states), and termination (every method execution terminates). The informal idea is that replicas reach the same final value if clients stop sending updates. The proposed model, Strong Eventual Consistency (SEC), adds a stronger condition, strong convergence: replicas that have delivered the same set of updates have an equivalent state, without waiting for any reconciliation period and without needing an arbitration mechanism. This avoids the pattern of executing an update right away, discovering later that it conflicts with another one, and undoing it, which wastes resources and generally requires consensus so that all replicas arbitrate the same way. A data type that satisfies the sufficient conditions for SEC is called a Conflict-free Replicated Data Type (CRDT). The system model assumes non-Byzantine processes connected by an asynchronous network that can partition and recover; processes may fail by crash-stop and, if they come back, they keep their memory.
Two sufficient conditions: CvRDT (state-based) and CmRDT (operation-based)
The paper gives two sufficient conditions for SEC, one for each replication style. In the state-based style, each replica changes its own state with updates and, from time to time, sends its state to another replica, which merges it into its own. A CvRDT requires that the possible states form a semilattice with a partial order, that the merge compute the least upper bound (LUB) of the two states, and that each update only make the state grow in that order. Since the LUB is commutative, associative, and idempotent, the order and duplication of merges do not matter. Theorem 1 states that, with eventual delivery and termination, this object is SEC. In the operation-based style, there is no merge: each update is a pair made of a prepare method, with no side effects and executed only at the source replica, and an effect method, executed at all replicas. A CmRDT requires that all concurrent operations commute and that delivery use a reliable causal-order broadcast (each message delivered exactly once, in an order consistent with happened-before). Theorem 2 guarantees SEC in that case. The paper also proves (Theorems 3 and 4) that the two styles are equivalent: each can emulate the other.
Trade-offs: CAP, fault tolerance, and the relationship to sequential consistency
On the CAP theorem, the authors argue that, since network failures are inevitable at large scale and availability is usually a priority, giving up strong consistency does not have to mean giving up every guarantee. An SEC replica is always available for reads and writes, regardless of network conditions, and any subset of replicas that can communicate converges even when isolated from the rest. SEC tolerates up to n-1 simultaneous failures per stop and does not require solving consensus. There is, however, a semantic price: SEC is incomparable with sequential consistency. To show that an SEC object may not be sequentially consistent, the paper uses a set with add and remove in which, for an add concurrent with a remove of the same element, the add wins. In a scenario with two replicas performing operations in parallel and a third doing the merge, the final state contains at the same time two elements whose removal would be the last event in any sequential order, a result that is impossible in a sequential execution. The paper notes that other semantics are possible for concurrent add and remove (the remove winning, for example), all compatible with strong convergence, and that the choice depends on the application. In the opposite direction, without failures, a sequentially consistent object is SEC, but in general sequential consistency requires consensus, which is not possible in the face of n-1 failures.
See the ideas at work
Practice the designs that use this paper in the System Design school.