CODING CHALLENGE · N°51

CRDT: Grow-Only Counter

Easy Distributed SystemsCRDTConsistency

A counter that many replicas increment independently, with no coordination, yet always converge to the same total after syncing — a G-Counter, the simplest CRDT. The secret is a per-replica payload merged by element-wise maximum, which is commutative, associative and idempotent. Compute the converged value. Solve it in Python or TypeScript, with hidden tests.

The problem

A grow-only counter (G-Counter) is replicated across several nodes. Each replica keeps a payload: a vector of per-replica counts (only replica i ever increments entry i). To read the counter, you merge all the payloads you have by taking the element-wise maximum, then sum the merged vector. Implement gcounter_value(payloads): given a list of payload vectors (all the same length), return the counter’s converged value.

EXAMPLE 1

Input payloads = [[1,0,0], [0,2,0], [1,0,3]]

Output 6

merge → [1,2,3], sum → 6

EXAMPLE 2

Input payloads = [[3,0], [3,0]]

Output 3

merging identical states is idempotent: max is still [3,0]

CONSTRAINTS

All payload vectors have the same length (one slot per replica). Merge = element-wise maximum across every payload.
The value is the sum of the merged vector.
The merge is commutative, associative and idempotent, so replicas converge to the same value regardless of sync order or duplicate messages — that is what makes it a CRDT.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement gcounter_value(payloads): fold the payloads together with element-wise max, then return the sum of the resulting vector.

HINTS — 4 IDEAS

Start the merged vector as all zeros (or as the first payload), then for each payload take merged[i] = max(merged[i], payload[i]).
Element-wise max is the whole trick: it keeps, per replica, the highest count anyone has seen — so it never double-counts and never goes backwards.
The counter’s value is sum(merged).
Convince yourself it is order-independent: max is commutative and associative, and merging the same state twice changes nothing (idempotent).

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Each node keeps its own counter in a map (node → count). An increment bumps only that node’s entry. The value of the counter is the sum of all entries. To merge two replicas, take the element-wise max per node — since a node only ever grows its own entry, the max is always the more-up-to-date value, and merges converge no matter the order.

Complexity

Time O(N) nodes to read the value or merge; space O(N).

Common mistakes

Summing entries on merge instead of taking the max — that double-counts increments.
Letting a node write another node’s entry, which breaks the convergence guarantee.
Not handling a node that appears only in one of the two replicas being merged.

Where this shows up

A G-Counter is the simplest CRDT: it converges without any coordination, so concurrent increments across replicas merge deterministically. It is the building block for conflict-free counters — likes, views, votes — in distributed and offline-first systems where you cannot afford a lock on every increment.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Distributed Systems