CRDT: Grow-Only Counter

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.

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.

Reference solution

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

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