Vibe Engines
YouTube

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

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.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? open the hints under the problem, or 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.

CPython · WebAssembly
Examples and constraints 4 examples
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]
EXAMPLE 3
Input payloads = [[2,1], [0,5]]
Output 7
merge → [2,5]; the total beats both payloads’ own sums (3 and 5)
EXAMPLE 4
Input payloads = [[1,2,3]]
Output 6
edge case: one payload but three replicas — the vector length, not the payload count, sets the slots
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.
Hints 4 ideas
HINTS — 4 IDEAS
  1. Start the merged vector as all zeros (or as the first payload), then for each payload take merged[i] = max(merged[i], payload[i]).
  2. 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.
  3. The counter’s value is sum(merged).
  4. Convince yourself it is order-independent: max is commutative and associative, and merging the same state twice changes nothing (idempotent).
Approach, complexity & discussion — open after you solve

Start from brute force

The first version most people write adds everything up: sum(sum(p) for p in payloads). It looks reasonable if you picture each payload as a batch of increments, and it costs O(P · N) time and O(1) space for P payloads of N slots. It is wrong because payloads are overlapping snapshots, not deltas: a count a replica reports is also inside every later snapshot that saw it. The first example gives 7 instead of 6, because replica 0’s single increment appears in two payloads, and [[3, 0], [3, 0]], one state delivered twice, gives 6 instead of 3. The next guess, the largest payload total, fails too: [[2, 1], [0, 5]] gives 5, and the answer is 7.

The approach

Merge per slot, not per payload. The insight is that slot i is written only by replica i and only ever grows, so every payload’s entry i is some past value of replica i’s count, and the largest one seen is the latest. Taking that maximum for every slot and summing counts each replica’s increments exactly once, however many payloads repeat them. Element-wise max is commutative, associative and idempotent, so neither the order of payloads nor a duplicate can change the result. The invariant: after the first t payloads, merged[i] is the largest count for replica i among them.

The reference reads the slot count from the vectors, n = len(payloads[0]), and starts from merged = [0] * n, which is the identity for max because counts are never negative. It folds each payload in with merged[i] = max(merged[i], p[i]) and returns sum(merged). Starting from a fresh list, rather than from payloads[0] itself, also keeps it from mutating the caller’s input.

slot 0slot 1slot 2payload 1100payload 2020payload 3103max per slot123adding all: 1+2+4 = 7replica 0 counted twicesum(merged) = 6slot i is written only by replica i, so its max is the latest count
The first example, read by column. Each slot keeps the largest count any payload reports for that replica, so replica 0’s one increment, present in two snapshots, is counted once. Summing rows instead treats overlapping snapshots as separate batches.

Walk through an example

The first example folds three payloads into merged, and the last column shows what adding every payload would give instead.

steppayload pmerged after maxsum(merged)adding instead
start—[0, 0, 0]00
1[1, 0, 0][1, 0, 0]11
2[0, 2, 0][1, 2, 0]33
3[1, 0, 3][1, 2, 3]; slot 0 stays 1, since max(1, 1) = 167
return——6—

Complexity

Reference: O(P · N) time for P payloads of N slots, since each slot of each payload is read once, and O(N) extra space for merged. Adding everything up: also O(P · N) time, with O(1) space. It is not slower, it is wrong, because it counts an increment once for every payload that contains it.

Edge cases to test

  • [[3, 0], [3, 0]], the same state delivered twice: the answer is 3, not 6. Idempotence is what makes duplicate messages harmless.
  • [[2, 1], [0, 5]]: the answer is 7, more than either payload’s own total (3 and 5), because each replica’s latest count comes from a different payload.
  • [[1, 2, 3]], one payload and three replicas: the answer is 6. Reading the slot count from len(payloads) instead of len(payloads[0]) gives 1 here, yet passes every input with as many payloads as slots.
  • [[5, 5], [1, 1]], a stale snapshot arriving after a fresh one: the answer is 10. Max ignores the older state whatever order the payloads arrive in.
  • An empty list: the reference reads payloads[0] and raises IndexError. A counter with no known states is 0, so if your contract allows an empty list, return 0 for it.

Common mistakes

  • Summing entries on merge instead of taking the max — that double-counts increments.
  • Taking the largest payload total instead of merging slot by slot: [[2, 1], [0, 5]] gives 5, but the merged vector [2, 5] sums to 7.
  • Writing merged = payloads[0] and then updating merged[i]: the value is right, but the caller’s first payload is overwritten (on the first example [1, 0, 0] becomes [1, 2, 3]).
  • Sizing merged by the number of payloads instead of the vector length. The two are equal in most small tests, which is why the bug survives them.

Follow-ups an interviewer asks next

Support increments and merges between live replicas, not just reading.
Each replica holds the vector and its own index i. increment() does p[i] += 1, and only replica i ever touches slot i. merge(other) sets every slot j to max(p[j], other[j]), and value() is sum(p). Because the merge is commutative, associative and idempotent, replicas can gossip their states in any order, any number of times, and still converge.
The counter must also go down.
A G-Counter cannot, because max discards a lower value. Use a PN-Counter: two G-Counters, P for increments and N for decrements, each merged by element-wise max, with value sum(P) - sum(N). A decrement is an increment of N, so both halves still only grow and still merge safely.
Replicas join and leave, so a fixed-length vector does not fit.
Store the payload as a map from replica id to count. Merge takes the union of the keys, reading a missing key as 0 and taking the max where both sides have one; the value is the sum of the map’s values. Ids must never be reused: a replica that restarts with an old id and an empty state has its new increments hidden under the old maximum.
Sending the whole vector on every sync costs too much.
Send deltas instead: only the slots that changed since the last sync with that peer, applied with the same element-wise max. This is the delta-state CRDT idea. The merge rule is what makes partial state safe, because a delta that arrives twice or out of order leaves the same result.

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.

The alternative it replaces is a single authoritative counter, one row in one database, which every increment must reach and lock. That is simple and always exact, but every write pays a round trip to that one place, and a replica that cannot reach it cannot count at all. A G-Counter flips the trade-off: each replica increments its own slot locally, with no network call, and accepts that two replicas may briefly report different totals until they exchange state. Every value a replica reports is a lower bound of the true count, never an overcount, and once all states have been exchanged every replica reports the same number. That guarantee is called strong eventual consistency.

The term CRDT comes from Shapiro, Preguiça, Baquero and Zawirski’s 2011 work on conflict-free replicated data types, which framed the pattern this challenge uses. The states form a join-semilattice: a partial order (vector A is at or below vector B when every slot of A is at most the matching slot of B) where any two states have a least upper bound, here the element-wise max. Updates only move a state upward and merge is the least upper bound, and any data type built that way converges. Sets that only grow (merge is union), registers that keep the value with the highest timestamp, and the PN-Counter from the follow-ups are all instances of the same recipe.

The cost is metadata. The payload holds a slot for every replica that has ever incremented, so the state grows with the number of writers rather than with the count, and a system with many short-lived clients, a mobile app where each install is a replica, can carry more vector than value. That is why practical designs group clients behind a small set of server replicas, use the map form so absent replicas cost nothing, and send deltas instead of whole states.

Check yourself

What does gcounter_value([[4, 1, 0], [2, 3, 0], [4, 0, 2]]) return, and what would summing every entry give?

It returns 9: the column maxima are 4, 3 and 2. Summing every entry gives 16, because replica 0’s count of 4 appears in two payloads and the stale 2 and 1 are added on top of the newer values.

Replica 1 had counted 7 when it crashed. It restarts with an empty state under the same id and increments twice, so the payloads are [[5, 7], [0, 2]]. What does the counter read, and how many increments really happened?

It reads 12, but 5 + 7 + 2 = 14 increments happened. Slot 1’s max is still the old 7, so the two new increments hide underneath it until the restarted replica passes 7. A restarted replica must either recover its old count or take a fresh id.

A PN-Counter has increment payloads P = [[3, 0], [1, 2]] and decrement payloads N = [[1, 0], [0, 1]]. What is its value?

3. Each half merges on its own with element-wise max: P becomes [3, 2], sum 5, and N becomes [1, 1], sum 2. The value is 5 − 2. Subtracting slot by slot before merging would lose decrements to the max.

Each of N replicas sends its full vector to every other replica once per round. How many numbers cross the network per round, and what is that for N = 100?

N(N − 1) messages of N slots each, which is O(N³) numbers: 100 × 99 × 100 = 990,000 for 100 replicas. Sending only changed slots (deltas) or gossiping to a few random peers per round instead of all of them is how real systems keep this down.

Reference solution

Reference solution — Python
def gcounter_value(payloads):
    n = len(payloads[0])
    merged = [0] * n
    for p in payloads:                      # merge = element-wise maximum
        for i in range(n):
            merged[i] = max(merged[i], p[i])
    return sum(merged)                       # value = sum of per-replica counts


print(gcounter_value([[1, 0, 0], [0, 2, 0], [1, 0, 3]]))   # -> 6
print(gcounter_value([[3, 0], [3, 0]]))                    # -> 3
Reference solution — TypeScript
function gcounterValue(payloads: number[][]): number {
  const n = payloads[0].length;
  const merged = new Array(n).fill(0);
  for (const p of payloads)                 // merge = element-wise maximum
    for (let i = 0; i < n; i++) merged[i] = Math.max(merged[i], p[i]);
  return merged.reduce((a, b) => a + b, 0);  // value = sum of counts
}

console.log(gcounterValue([[1, 0, 0], [0, 2, 0], [1, 0, 3]]));  // -> 6
console.log(gcounterValue([[3, 0], [3, 0]]));                   // -> 3

Questions about CRDT: Grow-Only Counter

What is a G-Counter CRDT?

A G-Counter, or grow-only counter, is a conflict-free replicated data type: a counter that several replicas can increment independently, without locks or coordination, and that always converges to the same value once they exchange state. Each replica keeps a vector with one slot per replica and only ever increments its own slot. Merging two states takes the maximum of each slot, and the counter’s value is the sum of the merged vector. It is the simplest state-based CRDT and a building block for more complex ones.

Why does a G-Counter merge with max instead of addition?

Because the states are snapshots, not deltas. When replica A sends its vector to B, the counts in it include increments B may already have seen through another path, and adding vectors would count those again: two copies of the state [3, 0] would add up to 6 when only 3 increments happened. Max is safe because slot i only ever grows and is only written by replica i, so the largest value seen for slot i is simply the most recent one. It is also idempotent, so duplicate messages are harmless.

Why must CRDT merges be commutative, associative and idempotent?

Those three properties are what let replicas converge without coordination. Commutative means the order of two merges does not matter, associative means the grouping does not matter, and idempotent means merging the same state twice changes nothing. Networks reorder, batch and duplicate messages, so a merge with all three gives the same result however the states arrive. Element-wise max has all three, which is why in this challenge any order of payloads, or a repeated payload, gives the same value.

Can a G-Counter be decremented?

No. A decrement would lower a slot, and the max-based merge would discard the lower value in favor of the older, higher one, so the decrement would vanish on the next sync. The standard fix is a PN-Counter, which pairs two G-Counters: one counts increments and the other counts decrements, and the value is the first sum minus the second. Both halves only ever grow, so both merge safely with element-wise max.

Finished this one? 0 / 76 Challenges done
NextRaft Leader Election (Majority) Next on the “Systems, limits & distribution” ladder · rung 9 of 9

Explore the topic

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

More Challenges