study › DDIA › Chapter 6 · Replication

A G-Counter Converges; a Naive Counter Loses 80 Increments

Three replicas each bump a shared counter while partitioned — A +100, B +50, C +30, so the answer must be 180. Merged as a single last-write-wins register the counter reports 100 and loses 80 increments; merged as a G-Counter CRDT it converges to exactly 180 in every one of the six merge orders.

Concept

Three replicas each bump a shared counter while partitioned — A does +100, B does +50, C does +30 — so the answer must be 180. Then they reconcile. Model the counter naively, as a single integer register merged by last-write-wins, and the merge keeps only one replica's work: the survivor is 100 and the other 80 increments vanish. Model it as a G-Counter CRDT — each replica keeps a vector of per-replica sub-counts, increment bumps its own entry, merge takes the element-wise MAX, value is the sum — and the replicas converge to exactly 180, in every merge order. Same increments, same true total; the only difference is what "merge" is allowed to know.

Provenance

Designing Data-Intensive Applications, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 6 — Replication, §"Conflict-free replicated datatypes and operational transformation" (and §"Automatic conflict resolution"):

CRDTs are data structures that can be concurrently edited [...] and which automatically resolve conflicts in sensible ways.

The book presents CRDTs as replicated types whose merge is associative, commutative, and idempotent, so replicas converge no matter the order updates arrive. Here you watch a counter do exactly that — and watch the naive version fail to.

Prerequisites

The surprise is about what a merge is allowed to remember. These help; each line notes where it shows up.

Concurrent writes need conflict resolution — while replicas are partitioned they each accept writes; on reconnect something must combine those divergent states. It shows up as the merge() method both counters implement.
Last-write-wins (LWW) discards data — picking one value and dropping the other is a valid conflict resolution, but for a counter it throws away real increments. It shows up as the naive counter losing 80 of 180.
A CRDT merge is commutative, associative, and idempotent — element-wise MAX over per-replica sub-counts has all three properties, which is exactly why merge order cannot change the result. It shows up as all six orders giving 180.
Per-replica bookkeeping (a version vector) — the G-Counter keeps one sub-count per replica id so it can tell "A's 100" apart from "B's 50" instead of collapsing them into one register. It shows up as the {A:100, B:50, C:30} dict whose sum is the value.

Where to learn the prerequisites CRDTs and automatic conflict resolution (#1–#3): DDIA §"Conflict-free replicated datatypes and operational transformation" and §"Automatic conflict resolution"; Shapiro et al., "Conflict-free Replicated Data Types" (2011) for the G-Counter and the merge-lattice argument. Why LWW loses writes (#2): DDIA §"Last write wins (discarding concurrent writes)" — LWW is fine when losing writes is acceptable, and a counter is precisely when it is not. If only one is new, make it #3 — commutative + associative + idempotent merge is the whole reason a CRDT converges.

Environment these numbers came from Deterministic, so the counts reproduce exactly. Captured on macOS 26.5.2 (Darwin 25.5.0), arm64, Python 3.15.0a8, standard library only — no Docker, no deps. No real concurrency: partitions and merges are simulated in one process, so the result is fixed every run. Fixed workload: A:+100, B:+50, C:+30 → true total 180.

Mental model

Two counters, same three replicas, same increments — only the merge differs.

Naive replicated counter — each replica is a single integer. Increment adds 1 to it. To merge two replicas, last-write-wins keeps the larger register (one value simply overwrites the other). There is no way to tell "100 from A" from "100 that already includes B and C," so concurrent increments cannot be summed.
G-Counter CRDT — each replica is a dict {replica_id: count}. Increment bumps its own entry. Merge takes, for every replica id, the MAX of the two sub-counts; the value is the sum of the merged dict. Because A's, B's, and C's contributions live in separate slots, no merge can overwrite one with another.

Both counters implement the same two-method interface (increment, merge); the exercise runs both against the identical workload. The whole thing is one script, code/g_counter_crdt.py.

Setup

cd study/ddia/ch06/code
python3 g_counter_crdt.py

Do not read the output yet — make each prediction first.

Step 1 · the workload

Predict. Three replicas increment while offline: A +100, B +50, C +30. Before any merge logic, what is the true total the counter should report after reconciliation?

What is the true total?

3 replicas increment a shared counter while partitioned, then merge. A: +100 B: +50 C: +30 true total = 180

180 — no surprise yet. The surprise is whether the merge can recover it.

Step 2 · merge the naive counter

Predict. Each replica holds a plain integer (A=100, B=50, C=30) and we merge them last-write-wins. What single number comes out — and how many of the 180 increments survive?

What does last-write-wins report?

naive replicated counter (single integer register, last-write-wins merge): after merging A, B, C -> 100 LOST 80 of 180 increments (44%) -- the merge kept one replica and dropped the rest.

100, not 180 — 80 increments gone. LWW on a single register can only pick a value, never combine two. It keeps A's 100 (the largest) and silently discards B's 50 and C's 30. Nothing errored; the counter just quietly lost 44% of the writes.

Step 3 · merge the G-Counter

Predict. Same three replicas, but now each is a dict — A={A:100}, B={B:50}, C={C:30} — merged by element-wise MAX and summed. What does it report?

What does the G-Counter report?

G-Counter CRDT (per-replica sub-counts, element-wise max merge): after merging A, B, C -> 180 LOST 0 increments -- converged to the exact total.

Exactly 180, nothing lost. The MAX is taken per replica id, so merging {A:100} with {B:50} gives {A:100, B:50} — the entries don't collide, they coexist. Summing the merged dict recovers every increment.

Step 4 · merge order doesn't matter

Predict. There are six orders to merge three replicas. How many distinct final values will the G-Counter produce across all six?

How many distinct values across all six orders?

order-independence -- merge the three G-Counters in every order: merge order A -> B -> C = 180 merge order A -> C -> B = 180 merge order B -> A -> C = 180 merge order B -> C -> A = 180 merge order C -> A -> B = 180 merge order C -> B -> A = 180 every order converges to the same value: the CRDT is order-independent.

One value — 180 — across all six orders. Element-wise MAX is commutative and associative, so the order the replicas reconcile in cannot change where they land. That is convergence: the replicas agree no matter how the network delivers their states.

What you should see

The true total is 180; both counters start from the identical workload.
The naive LWW register merges to 100, losing 80 increments (44%).
The G-Counter merges to 180, losing 0.
All six merge orders of the G-Counter give 180 — one distinct value.

Why

A counter under concurrent updates is the cleanest case where "just pick a value" fails. When three replicas each accept increments during a partition, their states genuinely diverge, and reconciliation has to combine the divergent work, not choose among it. Last-write-wins can only choose. Its merge — keep the larger register — treats the two 3-digit numbers as rivals, so the moment it keeps A's 100 it has thrown B's 50 and C's 30 away. The bug isn't in the arithmetic; it's that a single integer has nowhere to record that its 100 and B's 50 came from different, non-overlapping streams of increments. With only one slot, one write must overwrite the other.

The G-Counter fixes this by giving every replica its own slot. Because A only ever bumps counts["A"] and B only ever bumps counts["B"], the sub-counts are independent — no increment made by one replica can ever be the "same" write as an increment made by another. Merge then doesn't have to choose: for each slot it takes the MAX, which for these disjoint streams just means "carry across whichever replica's entry we have," and the sum reassembles the whole. And because MAX is commutative (max(a,b) = max(b,a)), associative, and idempotent (max(a,a) = a), the merge forms a lattice — every replica climbs monotonically toward the same least-upper-bound state. That is why all six orders converge to 180: the destination is a property of the set of updates, not the order they arrive.

The boundary — a G-Counter only counts up, and convergence is not correctness The MAX-merge trick works because increments are monotonic; subtract, and MAX would happily discard the smaller value again (the fix is a PN-Counter: two G-Counters, one for increments and one for decrements, subtracted). More broadly, a CRDT guarantees the replicas agree on an answer, not that the answer is the one an atomic, linearizable counter would have produced — it dodges coordination by restricting the operations to ones that commute. When your update isn't naturally commutative (transfer money, enforce a uniqueness constraint), no merge function saves you and you're back to consensus. CRDTs move the cost from runtime coordination to design-time: you buy conflict-free merges by giving up operations that can't be made to commute.

Go deeper

Make it subtract. Add a decrement to the G-Counter and watch a MAX-merge lose it, then build a PN-Counter (increments and decrements as two separate G-Counters, value = sum(P) − sum(N)) and confirm it converges again.
Break idempotence. Change the naive merge to add the two registers instead of MAX, then merge the same pair of replicas twice. Predict the double-count, and see why real CRDT merges must be idempotent to survive re-delivered messages.
Grow a grow-only set. Replace the counter with a G-Set (union-merge) and a fictional "remove" and discover why removal is the hard part of CRDTs — the jump from a G-Set to an OR-Set, and why tombstones appear.

Sources: DDIA 2e, Ch. 6, §"Conflict-free replicated datatypes and operational transformation", §"Automatic conflict resolution", §"Last write wins (discarding concurrent writes)" · Shapiro et al., "Conflict-free Replicated Data Types" (2011).