Concepts
Convergence without coordination with CRDTs
Intuition
Imagine two people editing copies of the same shopping list without internet, each jotting down whatever they want. When the copies meet again, you would like them to become the same list automatically, without anyone deciding who is right and without undoing anything. This is guaranteed if the rules for how the list changes are chosen so that the order in which the changes arrive makes no difference: then each person works freely and everyone ends up seeing the same result.
How it works
The paper defines Strong Eventual Consistency (SEC): besides eventual delivery and termination, replicas that have delivered the same set of updates have equivalent state immediately, with no reconciliation period and no conflict arbitration. A data type that satisfies sufficient conditions for this is a CRDT (Conflict-free Replicated Data Type). In the state-based style (CvRDT), the states form a semilattice, each update only makes the state grow in that partial order, and merge computes the least upper bound (LUB) of two states; because the LUB is commutative, associative, and idempotent, the order and duplication of merges do not change the result (Theorem 1). In the operation-based style (CmRDT), each update has a prepare method, free of side effects and executed only at the origin replica, and an effect method, executed at all replicas; concurrent operations are required to commute and delivery must use reliable broadcast with causal order (Theorem 2). The paper proves that the two styles are equivalent, since each can emulate the other. Because convergence comes from the mathematical properties of the type, the replica stays always available for reads and writes, tolerates up to n-1 crash failures, and does not require solving consensus. The price is semantic: SEC is incomparable with sequential consistency, and in a set with concurrent add and remove you must choose a semantics (for example, add wins), which depends on the application.
In practice
Consider CRDTs when replicas need to accept writes during partitions or disconnected operation and you prefer to design the data type to be conflict-free rather than arbitrate conflicts afterward, as in a replicated counter, which converges because increment and decrement commute. The paper cites the anomalies of Amazon's shopping cart as an example of fragile ad hoc approaches. On the other hand, do not use them where the application requires the total order of sequential consistency, and decide explicitly on the semantics of concurrent operations, such as add versus remove.
Use it in a design
Practice the cases that rely on this concept in the System Design school.