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

Explore the topic

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

Distributed Systems