Math to the Rescue
The reason CRDTs work is that their merge operations satisfy three mathematical properties. You don't need to memorize the formal definitions, but understanding them intuitively is essential.
1. Commutativity: The order of operations doesn't change the result.
- $A \cup B = B \cup A$ (set union)
- Applying "Alice's update then Bob's update" gives the same result as "Bob's update then Alice's update."
2. Associativity: Grouping of operations doesn't change the result.
- $(A \cup B) \cup C = A \cup (B \cup C)$
- It doesn't matter which two replicas sync first before a third joins.
3. Idempotency: Applying the same operation twice gives the same result as applying it once.
- $A \cup A = A$
- If a sync message is delivered twice due to a network retry, the state doesn't change. This is critical in unreliable networks.
Why These Three Properties Together?
In a distributed system, messages can arrive out of order (commutativity handles this), be partially delivered to different subsets of nodes (associativity handles this), and be duplicated by retries (idempotency handles this). A data structure whose merge function satisfies all three is immune to the chaos of real networks.
Contrast with non-CRDT operations:
- "Set value to X" is not commutative: "Set to A, then Set to B" ≠ "Set to B, then Set to A."
- "Increment by 1" applied twice is not idempotent: you get +2 instead of +1.
- "Add element X with a unique tag" IS commutative, associative, and idempotent.
Key Point: These three properties together form the mathematical contract that allows CRDTs to merge in any order, from any subset of replicas, over any unreliable network — and always converge. A data structure that satisfies all three is called a join-semilattice, the formal mathematical structure underlying all state-based CRDTs.