Questions: CRDTs: Conflict-Free Replicated Data Types

Question 1

A G-Counter allows each of n replicas to increment only its own entry. When two replicas exchange state, what merge operation ensures they converge to the same count, and why?

• A. Element-wise sum — add corresponding entries so no increments are lost
• B. Element-wise maximum — take the larger value for each entry; because max is commutative and idempotent, replicas converge regardless of message order
• C. Element-wise minimum — take the smaller value to prevent double-counting
• D. Last-write-wins — the most recently timestamped entry overwrites the other

Answer: (B)

Element-wise max is the correct merge for a G-Counter. If replica A has [3,1,0] and replica B has [2,2,0], the merge is [3,2,0] — the total is 5 regardless of which replica you merge from (commutative) and merging again produces the same result (idempotent). Element-wise sum would double-count increments that both replicas already have. Last-write-wins requires coordination to determine 'last.' Max requires none of that.

Question 2

An application needs to ensure no two users can register the same username — a global uniqueness constraint. Can a CRDT provide this guarantee without any coordination?

• A. Yes — an OR-Set CRDT tags each username with a unique identifier, preventing duplicates
• B. Yes — a G-Set's union merge naturally ensures each element appears only once
• C. No — enforcing global uniqueness requires knowing the complete current state across all replicas simultaneously, which requires coordination that CRDTs cannot provide
• D. No — CRDTs only support numeric data types, not strings like usernames

Answer: (C)

CRDTs guarantee convergence for operations whose semantics fit a join semilattice. A uniqueness constraint is fundamentally different: to accept 'alice' you must know that no other replica has already accepted it, which requires a globally consistent snapshot at the moment of the write. CRDTs let each replica accept writes locally and independently — which is precisely why they cannot enforce global exclusion. This is not an implementation limitation but a logical impossibility without coordination.

Question 3

CRDTs achieve conflict-free convergence by having replicas contact a central coordinator before accepting each write operation.

• T. True
• F. False

Answer: False

The entire value of CRDTs is that they require NO coordination. Each replica accepts writes locally and immediately, without contacting any other replica. Convergence is guaranteed not by coordination but by the mathematical properties of the merge operation: commutativity, associativity, and idempotence ensure that no matter in which order replicas exchange updates, they reach the same final state. Requiring a coordinator would make CRDTs equivalent to traditional distributed locks — only fast when the coordinator is reachable.

Question 4

If a replica receives the same CRDT update twice due to network retransmission, applying it a second time corrupts the state.

• T. True
• F. False

Answer: False

CRDTs are idempotent: merging the same state twice produces the same result as merging it once. For a G-Counter, taking element-wise max of [3,1,0] with [3,1,0] yields [3,1,0] — unchanged. Idempotence is one of the three required semilattice properties (alongside commutativity and associativity), and it means replicas can receive duplicate messages from at-least-once delivery networks with no ill effects — a critical property for practical deployment.

Question 5

Why must a CRDT's merge operation be commutative, associative, AND idempotent? What breaks if any one of these properties is missing?

Model answer: Commutativity ensures merge(A,B) = merge(B,A) — replicas that receive updates in different orders converge to the same state. Associativity ensures that pairwise merges in any sequence produce the same result — important when updates propagate through intermediate nodes. Idempotence ensures that receiving the same update more than once has no effect. If commutativity fails, message ordering matters and replicas diverge. If associativity fails, the propagation path affects the result. If idempotence fails, duplicate delivery corrupts state. All three together make coordination unnecessary.

The three properties define a join semilattice, the mathematical structure that guarantees convergence. Each property eliminates a different class of distributed hazard: ordering dependence, path dependence, and duplicate delivery. A system missing any one of these either reintroduces coordination requirements or produces incorrect results — defeating the purpose of a CRDT entirely.