Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path →
CRDT: Grow-Only Counter
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.
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.
Implement gcounter_value(payloads): fold the payloads together with element-wise max, then return the sum of the resulting vector.
Examples and constraints 4 examples
payloads = [[1,0,0], [0,2,0], [1,0,3]]6payloads = [[3,0], [3,0]]3payloads = [[2,1], [0,5]]7payloads = [[1,2,3]]6- 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
- 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).
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.
Walk through an example
The first example folds three payloads into merged, and the last column shows what adding every payload would give instead.
| step | payload p | merged after max | sum(merged) | adding instead |
|---|---|---|---|---|
| start | — | [0, 0, 0] | 0 | 0 |
| 1 | [1, 0, 0] | [1, 0, 0] | 1 | 1 |
| 2 | [0, 2, 0] | [1, 2, 0] | 3 | 3 |
| 3 | [1, 0, 3] | [1, 2, 3]; slot 0 stays 1, since max(1, 1) = 1 | 6 | 7 |
| 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 fromlen(payloads)instead oflen(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 raisesIndexError. 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 updatingmerged[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
mergedby 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()doesp[i] += 1, and only replica i ever touches slot i.merge(other)sets every slot j tomax(p[j], other[j]), andvalue()issum(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]])) # -> 3Reference 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]])); // -> 3Questions 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.
Explore the topic
See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.
More Challenges
- Circuit BreakerStop one failing dependency from taking down the fleet: trip after consecutive failures, fail fast while open, probe once after the cooldown. Implement the closed → open → half-open state machine as a pure, testable replay. Solve it in Python or TypeScript.Read →
- Consistent Hashing RingHow distributed caches decide which node owns a key — with tiny churn when nodes join or leave. Build a hash ring with virtual nodes and route keys clockwise. A provided hash keeps Python and TypeScript in sync. Hidden tests.Read →
- Raft Leader Election (Majority)The heartbeat of the Raft consensus algorithm: a candidate becomes leader only by winning a strict majority of the cluster — the rule that guarantees at most one leader per term. Decide an election round. Solve it in Python or TypeScript, with hidden tests.Read →
- Vector Clock MergeVector clocks let processes with no shared time agree on which event caused which. The key operation: on receive, take the element-wise max of the two clocks, then tick your own entry. Solve it in Python or TypeScript, with hidden tests.Read →
- Verify a Webhook SignatureEvery real integration sends signed webhooks — and every FDE has to verify them. Recompute the signature over the payload, compare in constant time, and reject stale events to stop replay attacks. Solve it in Python or TypeScript, with hidden tests.Read →
- Idempotency Key HandlerNetworks retry. A webhook fires twice; a payment is re-sent after a timeout. Without idempotency you double-charge or double-write. The fix: dedupe by a client-supplied key and always return the first result. Solve it in Python or TypeScript, with hidden tests.Read →