FAILURE MAP
← Case archive

FA-74861 / CRDT convergence / Open access

G-Counter gossip: the value reads only the local slot · case 01

A replica reports only its own increments even after receiving everyone else's state.

Verified by executionVariant 1 · 7 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The value reads the replica's own slot rather than summing all slots.

VERIFIED REPAIR

The counter value is the sum of every slot in the replica's map.

Unsuccessful approach: Taking the largest slot is correct only when one replica did all the increments.

Case contract

Each replica keeps a grow-only map replica->count. ["inc", r, k] adds positive integer k to r's own slot; a non-positive k is rejected and counted. ["sync", src, dst] merges src into dst by pointwise maximum. Return per-replica values (sum of slots), the rejection count, and the first replica's sorted slots.

Why this case matters

State-based counters must converge under repeated, reordered and transitive gossip.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(events, replicas):
    state = {r: {} for r in replicas}
    rejected = 0
    for ev in events:
        if ev[0] == 'inc':
            r, amount = ev[1], ev[2]
            if amount <= 0:
                rejected += 1
                continue
            state[r][r] = state[r].get(r, 0) + amount
        elif ev[0] == 'sync':
            src, dst = state[ev[1]], state[ev[2]]
            for k, v in src.items():
                dst[k] = max(dst.get(k, 0), v)
    values = [state[r].get(r, 0) for r in replicas]
    return {'values': values, 'rejected': rejected, 'state': sorted([k, v] for k, v in state[replicas[0]].items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('repeated sync is idempotent', [[['inc', 'a', 2], ['sync', 'a', 'b'], ['sync', 'a', 'b'], ['inc', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c', 'd']], {'values': [4, 4, 0, 0], 'rejected': 0, 'state': [['a', 2], ['b', 2]]}), ('transitive gossip carries third-party slots', [[['inc', 'a', 1], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['inc', 'c', 1], ['sync', 'c', 'd']], ['a', 'b', 'c', 'd']], {'values': [1, 1, 2, 2], 'rejected': 0, 'state': [['a', 1]]}), ('stale path does not regress a slot', [[['inc', 'a', 1], ['sync', 'a', 'd'], ['inc', 'a', 1], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['sync', 'd', 'c']], ['a', 'b', 'c', 'd']], {'values': [2, 2, 2, 1], 'rejected': 0, 'state': [['a', 2]]}), ('zero and negative amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', -1], ['inc', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 2, 0], 'rejected': 2, 'state': [['a', 3], ['c', 2]]}), ('concurrent increments all survive', [[['inc', 'a', 1], ['inc', 'b', 3], ['inc', 'c', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c', 'd']], {'values': [5, 5, 5, 0], 'rejected': 0, 'state': [['a', 1], ['b', 3], ['c', 1]]}), ('empty history', [[], ['a', 'b', 'c', 'd']], {'values': [0, 0, 0, 0], 'rejected': 0, 'state': []}), ('repeated local increments accumulate', [[['inc', 'a', 1], ['sync', 'a', 'a'], ['inc', 'a', 1], ['inc', 'd', 1]], ['a', 'b', 'c', 'd']], {'values': [2, 0, 0, 1], 'rejected': 0, 'state': [['a', 2]]})],
    2: [('repeated sync is idempotent', [[['inc', 'a', 3], ['sync', 'a', 'b'], ['sync', 'a', 'b'], ['inc', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c', 'd']], {'values': [5, 5, 0, 0], 'rejected': 0, 'state': [['a', 3], ['b', 2]]}), ('transitive gossip carries third-party slots', [[['inc', 'a', 2], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['inc', 'c', 1], ['sync', 'c', 'd']], ['a', 'b', 'c', 'd']], {'values': [2, 2, 3, 3], 'rejected': 0, 'state': [['a', 2]]}), ('stale path does not regress a slot', [[['inc', 'a', 1], ['sync', 'a', 'd'], ['inc', 'a', 2], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['sync', 'd', 'c']], ['a', 'b', 'c', 'd']], {'values': [3, 3, 3, 1], 'rejected': 0, 'state': [['a', 3]]}), ('zero and negative amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', -2], ['inc', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 2, 0], 'rejected': 2, 'state': [['a', 3], ['c', 2]]}), ('concurrent increments all survive', [[['inc', 'a', 2], ['inc', 'b', 4], ['inc', 'c', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c', 'd']], {'values': [7, 7, 7, 0], 'rejected': 0, 'state': [['a', 2], ['b', 4], ['c', 1]]}), ('empty history', [[], ['a', 'b', 'c', 'd']], {'values': [0, 0, 0, 0], 'rejected': 0, 'state': []}), ('repeated local increments accumulate', [[['inc', 'a', 2], ['sync', 'a', 'a'], ['inc', 'a', 1], ['inc', 'd', 2]], ['a', 'b', 'c', 'd']], {'values': [3, 0, 0, 2], 'rejected': 0, 'state': [['a', 3]]})],
    3: [('repeated sync is idempotent', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['sync', 'a', 'b'], ['inc', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c', 'd']], {'values': [6, 6, 0, 0], 'rejected': 0, 'state': [['a', 4], ['b', 2]]}), ('transitive gossip carries third-party slots', [[['inc', 'a', 3], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['inc', 'c', 1], ['sync', 'c', 'd']], ['a', 'b', 'c', 'd']], {'values': [3, 3, 4, 4], 'rejected': 0, 'state': [['a', 3]]}), ('stale path does not regress a slot', [[['inc', 'a', 1], ['sync', 'a', 'd'], ['inc', 'a', 3], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['sync', 'd', 'c']], ['a', 'b', 'c', 'd']], {'values': [4, 4, 4, 1], 'rejected': 0, 'state': [['a', 4]]}), ('zero and negative amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', -3], ['inc', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 2, 0], 'rejected': 2, 'state': [['a', 3], ['c', 2]]}), ('concurrent increments all survive', [[['inc', 'a', 3], ['inc', 'b', 5], ['inc', 'c', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c', 'd']], {'values': [9, 9, 9, 0], 'rejected': 0, 'state': [['a', 3], ['b', 5], ['c', 1]]}), ('empty history', [[], ['a', 'b', 'c', 'd']], {'values': [0, 0, 0, 0], 'rejected': 0, 'state': []}), ('repeated local increments accumulate', [[['inc', 'a', 3], ['sync', 'a', 'a'], ['inc', 'a', 1], ['inc', 'd', 3]], ['a', 'b', 'c', 'd']], {'values': [4, 0, 0, 3], 'rejected': 0, 'state': [['a', 4]]})],
    4: [('repeated sync is idempotent', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['sync', 'a', 'b'], ['inc', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c', 'd']], {'values': [7, 7, 0, 0], 'rejected': 0, 'state': [['a', 5], ['b', 2]]}), ('transitive gossip carries third-party slots', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['inc', 'c', 1], ['sync', 'c', 'd']], ['a', 'b', 'c', 'd']], {'values': [4, 4, 5, 5], 'rejected': 0, 'state': [['a', 4]]}), ('stale path does not regress a slot', [[['inc', 'a', 1], ['sync', 'a', 'd'], ['inc', 'a', 4], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['sync', 'd', 'c']], ['a', 'b', 'c', 'd']], {'values': [5, 5, 5, 1], 'rejected': 0, 'state': [['a', 5]]}), ('zero and negative amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', -4], ['inc', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 2, 0], 'rejected': 2, 'state': [['a', 3], ['c', 2]]}), ('concurrent increments all survive', [[['inc', 'a', 4], ['inc', 'b', 6], ['inc', 'c', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c', 'd']], {'values': [11, 11, 11, 0], 'rejected': 0, 'state': [['a', 4], ['b', 6], ['c', 1]]}), ('empty history', [[], ['a', 'b', 'c', 'd']], {'values': [0, 0, 0, 0], 'rejected': 0, 'state': []}), ('repeated local increments accumulate', [[['inc', 'a', 4], ['sync', 'a', 'a'], ['inc', 'a', 1], ['inc', 'd', 4]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 0, 4], 'rejected': 0, 'state': [['a', 5]]})],
    5: [('repeated sync is idempotent', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['sync', 'a', 'b'], ['inc', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c', 'd']], {'values': [8, 8, 0, 0], 'rejected': 0, 'state': [['a', 6], ['b', 2]]}), ('transitive gossip carries third-party slots', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['inc', 'c', 1], ['sync', 'c', 'd']], ['a', 'b', 'c', 'd']], {'values': [5, 5, 6, 6], 'rejected': 0, 'state': [['a', 5]]}), ('stale path does not regress a slot', [[['inc', 'a', 1], ['sync', 'a', 'd'], ['inc', 'a', 5], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['sync', 'd', 'c']], ['a', 'b', 'c', 'd']], {'values': [6, 6, 6, 1], 'rejected': 0, 'state': [['a', 6]]}), ('zero and negative amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', -5], ['inc', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 2, 0], 'rejected': 2, 'state': [['a', 3], ['c', 2]]}), ('concurrent increments all survive', [[['inc', 'a', 5], ['inc', 'b', 7], ['inc', 'c', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c', 'd']], {'values': [13, 13, 13, 0], 'rejected': 0, 'state': [['a', 5], ['b', 7], ['c', 1]]}), ('empty history', [[], ['a', 'b', 'c', 'd']], {'values': [0, 0, 0, 0], 'rejected': 0, 'state': []}), ('repeated local increments accumulate', [[['inc', 'a', 5], ['sync', 'a', 'a'], ['inc', 'a', 1], ['inc', 'd', 5]], ['a', 'b', 'c', 'd']], {'values': [6, 0, 0, 5], 'rejected': 0, 'state': [['a', 6]]})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
repeated sync is idempotent{'rejected': 0, 'state': [['a', 2], ['b', 2]], 'values': [2, 2, 0, 0]}{'rejected': 0, 'state': [['a', 2], ['b', 2]], 'values': [4, 4, 0, 0]}Failed
transitive gossip carries third-party slots{'rejected': 0, 'state': [['a', 1]], 'values': [1, 0, 1, 0]}{'rejected': 0, 'state': [['a', 1]], 'values': [1, 1, 2, 2]}Failed
stale path does not regress a slot{'rejected': 0, 'state': [['a', 2]], 'values': [2, 0, 0, 0]}{'rejected': 0, 'state': [['a', 2]], 'values': [2, 2, 2, 1]}Failed
zero and negative amounts are rejected{'rejected': 2, 'state': [['a', 3], ['c', 2]], 'values': [3, 0, 2, 0]}{'rejected': 2, 'state': [['a', 3], ['c', 2]], 'values': [5, 0, 2, 0]}Failed
concurrent increments all survive{'rejected': 0, 'state': [['a', 1], ['b', 3], ['c', 1]], 'values': [1, 3, 1, 0]}{'rejected': 0, 'state': [['a', 1], ['b', 3], ['c', 1]], 'values': [5, 5, 5, 0]}Failed
empty history{'rejected': 0, 'state': [], 'values': [0, 0, 0, 0]}{'rejected': 0, 'state': [], 'values': [0, 0, 0, 0]}Passed
repeated local increments accumulate{'rejected': 0, 'state': [['a', 2]], 'values': [2, 0, 0, 1]}{'rejected': 0, 'state': [['a', 2]], 'values': [2, 0, 0, 1]}Passed

SHA-256 / 52cc544869a04a134059d30752916c11b0eeae6742b3314d3a16e2c7eaf6c236

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(events, replicas):
    state = {r: {} for r in replicas}
    rejected = 0
    for ev in events:
        if ev[0] == 'inc':
            r, amount = ev[1], ev[2]
            if amount <= 0:
                rejected += 1
                continue
            state[r][r] = state[r].get(r, 0) + amount
        elif ev[0] == 'sync':
            src, dst = state[ev[1]], state[ev[2]]
            for k, v in src.items():
                dst[k] = max(dst.get(k, 0), v)
    values = [max(state[r].values(), default=0) for r in replicas]
    return {'values': values, 'rejected': rejected, 'state': sorted([k, v] for k, v in state[replicas[0]].items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('repeated sync is idempotent', [[['inc', 'a', 2], ['sync', 'a', 'b'], ['sync', 'a', 'b'], ['inc', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c', 'd']], {'values': [4, 4, 0, 0], 'rejected': 0, 'state': [['a', 2], ['b', 2]]}), ('transitive gossip carries third-party slots', [[['inc', 'a', 1], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['inc', 'c', 1], ['sync', 'c', 'd']], ['a', 'b', 'c', 'd']], {'values': [1, 1, 2, 2], 'rejected': 0, 'state': [['a', 1]]}), ('stale path does not regress a slot', [[['inc', 'a', 1], ['sync', 'a', 'd'], ['inc', 'a', 1], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['sync', 'd', 'c']], ['a', 'b', 'c', 'd']], {'values': [2, 2, 2, 1], 'rejected': 0, 'state': [['a', 2]]}), ('zero and negative amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', -1], ['inc', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 2, 0], 'rejected': 2, 'state': [['a', 3], ['c', 2]]}), ('concurrent increments all survive', [[['inc', 'a', 1], ['inc', 'b', 3], ['inc', 'c', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c', 'd']], {'values': [5, 5, 5, 0], 'rejected': 0, 'state': [['a', 1], ['b', 3], ['c', 1]]}), ('empty history', [[], ['a', 'b', 'c', 'd']], {'values': [0, 0, 0, 0], 'rejected': 0, 'state': []}), ('repeated local increments accumulate', [[['inc', 'a', 1], ['sync', 'a', 'a'], ['inc', 'a', 1], ['inc', 'd', 1]], ['a', 'b', 'c', 'd']], {'values': [2, 0, 0, 1], 'rejected': 0, 'state': [['a', 2]]})],
    2: [('repeated sync is idempotent', [[['inc', 'a', 3], ['sync', 'a', 'b'], ['sync', 'a', 'b'], ['inc', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c', 'd']], {'values': [5, 5, 0, 0], 'rejected': 0, 'state': [['a', 3], ['b', 2]]}), ('transitive gossip carries third-party slots', [[['inc', 'a', 2], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['inc', 'c', 1], ['sync', 'c', 'd']], ['a', 'b', 'c', 'd']], {'values': [2, 2, 3, 3], 'rejected': 0, 'state': [['a', 2]]}), ('stale path does not regress a slot', [[['inc', 'a', 1], ['sync', 'a', 'd'], ['inc', 'a', 2], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['sync', 'd', 'c']], ['a', 'b', 'c', 'd']], {'values': [3, 3, 3, 1], 'rejected': 0, 'state': [['a', 3]]}), ('zero and negative amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', -2], ['inc', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 2, 0], 'rejected': 2, 'state': [['a', 3], ['c', 2]]}), ('concurrent increments all survive', [[['inc', 'a', 2], ['inc', 'b', 4], ['inc', 'c', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c', 'd']], {'values': [7, 7, 7, 0], 'rejected': 0, 'state': [['a', 2], ['b', 4], ['c', 1]]}), ('empty history', [[], ['a', 'b', 'c', 'd']], {'values': [0, 0, 0, 0], 'rejected': 0, 'state': []}), ('repeated local increments accumulate', [[['inc', 'a', 2], ['sync', 'a', 'a'], ['inc', 'a', 1], ['inc', 'd', 2]], ['a', 'b', 'c', 'd']], {'values': [3, 0, 0, 2], 'rejected': 0, 'state': [['a', 3]]})],
    3: [('repeated sync is idempotent', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['sync', 'a', 'b'], ['inc', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c', 'd']], {'values': [6, 6, 0, 0], 'rejected': 0, 'state': [['a', 4], ['b', 2]]}), ('transitive gossip carries third-party slots', [[['inc', 'a', 3], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['inc', 'c', 1], ['sync', 'c', 'd']], ['a', 'b', 'c', 'd']], {'values': [3, 3, 4, 4], 'rejected': 0, 'state': [['a', 3]]}), ('stale path does not regress a slot', [[['inc', 'a', 1], ['sync', 'a', 'd'], ['inc', 'a', 3], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['sync', 'd', 'c']], ['a', 'b', 'c', 'd']], {'values': [4, 4, 4, 1], 'rejected': 0, 'state': [['a', 4]]}), ('zero and negative amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', -3], ['inc', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 2, 0], 'rejected': 2, 'state': [['a', 3], ['c', 2]]}), ('concurrent increments all survive', [[['inc', 'a', 3], ['inc', 'b', 5], ['inc', 'c', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c', 'd']], {'values': [9, 9, 9, 0], 'rejected': 0, 'state': [['a', 3], ['b', 5], ['c', 1]]}), ('empty history', [[], ['a', 'b', 'c', 'd']], {'values': [0, 0, 0, 0], 'rejected': 0, 'state': []}), ('repeated local increments accumulate', [[['inc', 'a', 3], ['sync', 'a', 'a'], ['inc', 'a', 1], ['inc', 'd', 3]], ['a', 'b', 'c', 'd']], {'values': [4, 0, 0, 3], 'rejected': 0, 'state': [['a', 4]]})],
    4: [('repeated sync is idempotent', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['sync', 'a', 'b'], ['inc', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c', 'd']], {'values': [7, 7, 0, 0], 'rejected': 0, 'state': [['a', 5], ['b', 2]]}), ('transitive gossip carries third-party slots', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['inc', 'c', 1], ['sync', 'c', 'd']], ['a', 'b', 'c', 'd']], {'values': [4, 4, 5, 5], 'rejected': 0, 'state': [['a', 4]]}), ('stale path does not regress a slot', [[['inc', 'a', 1], ['sync', 'a', 'd'], ['inc', 'a', 4], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['sync', 'd', 'c']], ['a', 'b', 'c', 'd']], {'values': [5, 5, 5, 1], 'rejected': 0, 'state': [['a', 5]]}), ('zero and negative amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', -4], ['inc', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 2, 0], 'rejected': 2, 'state': [['a', 3], ['c', 2]]}), ('concurrent increments all survive', [[['inc', 'a', 4], ['inc', 'b', 6], ['inc', 'c', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c', 'd']], {'values': [11, 11, 11, 0], 'rejected': 0, 'state': [['a', 4], ['b', 6], ['c', 1]]}), ('empty history', [[], ['a', 'b', 'c', 'd']], {'values': [0, 0, 0, 0], 'rejected': 0, 'state': []}), ('repeated local increments accumulate', [[['inc', 'a', 4], ['sync', 'a', 'a'], ['inc', 'a', 1], ['inc', 'd', 4]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 0, 4], 'rejected': 0, 'state': [['a', 5]]})],
    5: [('repeated sync is idempotent', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['sync', 'a', 'b'], ['inc', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c', 'd']], {'values': [8, 8, 0, 0], 'rejected': 0, 'state': [['a', 6], ['b', 2]]}), ('transitive gossip carries third-party slots', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['inc', 'c', 1], ['sync', 'c', 'd']], ['a', 'b', 'c', 'd']], {'values': [5, 5, 6, 6], 'rejected': 0, 'state': [['a', 5]]}), ('stale path does not regress a slot', [[['inc', 'a', 1], ['sync', 'a', 'd'], ['inc', 'a', 5], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['sync', 'd', 'c']], ['a', 'b', 'c', 'd']], {'values': [6, 6, 6, 1], 'rejected': 0, 'state': [['a', 6]]}), ('zero and negative amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', -5], ['inc', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 2, 0], 'rejected': 2, 'state': [['a', 3], ['c', 2]]}), ('concurrent increments all survive', [[['inc', 'a', 5], ['inc', 'b', 7], ['inc', 'c', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c', 'd']], {'values': [13, 13, 13, 0], 'rejected': 0, 'state': [['a', 5], ['b', 7], ['c', 1]]}), ('empty history', [[], ['a', 'b', 'c', 'd']], {'values': [0, 0, 0, 0], 'rejected': 0, 'state': []}), ('repeated local increments accumulate', [[['inc', 'a', 5], ['sync', 'a', 'a'], ['inc', 'a', 1], ['inc', 'd', 5]], ['a', 'b', 'c', 'd']], {'values': [6, 0, 0, 5], 'rejected': 0, 'state': [['a', 6]]})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
repeated sync is idempotent{'rejected': 0, 'state': [['a', 2], ['b', 2]], 'values': [2, 2, 0, 0]}{'rejected': 0, 'state': [['a', 2], ['b', 2]], 'values': [4, 4, 0, 0]}Failed
transitive gossip carries third-party slots{'rejected': 0, 'state': [['a', 1]], 'values': [1, 1, 1, 1]}{'rejected': 0, 'state': [['a', 1]], 'values': [1, 1, 2, 2]}Failed
stale path does not regress a slot{'rejected': 0, 'state': [['a', 2]], 'values': [2, 2, 2, 1]}{'rejected': 0, 'state': [['a', 2]], 'values': [2, 2, 2, 1]}Passed
zero and negative amounts are rejected{'rejected': 2, 'state': [['a', 3], ['c', 2]], 'values': [3, 0, 2, 0]}{'rejected': 2, 'state': [['a', 3], ['c', 2]], 'values': [5, 0, 2, 0]}Failed
concurrent increments all survive{'rejected': 0, 'state': [['a', 1], ['b', 3], ['c', 1]], 'values': [3, 3, 3, 0]}{'rejected': 0, 'state': [['a', 1], ['b', 3], ['c', 1]], 'values': [5, 5, 5, 0]}Failed
empty history{'rejected': 0, 'state': [], 'values': [0, 0, 0, 0]}{'rejected': 0, 'state': [], 'values': [0, 0, 0, 0]}Passed
repeated local increments accumulate{'rejected': 0, 'state': [['a', 2]], 'values': [2, 0, 0, 1]}{'rejected': 0, 'state': [['a', 2]], 'values': [2, 0, 0, 1]}Passed

SHA-256 / 6aa87f590f8a4b05e2732f8a707f72f3d86a87ce23f3875f60feffa02d9d32be

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(events, replicas):
    state = {r: {} for r in replicas}
    rejected = 0
    for ev in events:
        if ev[0] == 'inc':
            r, amount = ev[1], ev[2]
            if amount <= 0:
                rejected += 1
                continue
            state[r][r] = state[r].get(r, 0) + amount
        elif ev[0] == 'sync':
            src, dst = state[ev[1]], state[ev[2]]
            for k, v in src.items():
                dst[k] = max(dst.get(k, 0), v)
    values = [sum(state[r].values()) for r in replicas]
    return {'values': values, 'rejected': rejected, 'state': sorted([k, v] for k, v in state[replicas[0]].items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('repeated sync is idempotent', [[['inc', 'a', 2], ['sync', 'a', 'b'], ['sync', 'a', 'b'], ['inc', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c', 'd']], {'values': [4, 4, 0, 0], 'rejected': 0, 'state': [['a', 2], ['b', 2]]}), ('transitive gossip carries third-party slots', [[['inc', 'a', 1], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['inc', 'c', 1], ['sync', 'c', 'd']], ['a', 'b', 'c', 'd']], {'values': [1, 1, 2, 2], 'rejected': 0, 'state': [['a', 1]]}), ('stale path does not regress a slot', [[['inc', 'a', 1], ['sync', 'a', 'd'], ['inc', 'a', 1], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['sync', 'd', 'c']], ['a', 'b', 'c', 'd']], {'values': [2, 2, 2, 1], 'rejected': 0, 'state': [['a', 2]]}), ('zero and negative amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', -1], ['inc', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 2, 0], 'rejected': 2, 'state': [['a', 3], ['c', 2]]}), ('concurrent increments all survive', [[['inc', 'a', 1], ['inc', 'b', 3], ['inc', 'c', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c', 'd']], {'values': [5, 5, 5, 0], 'rejected': 0, 'state': [['a', 1], ['b', 3], ['c', 1]]}), ('empty history', [[], ['a', 'b', 'c', 'd']], {'values': [0, 0, 0, 0], 'rejected': 0, 'state': []}), ('repeated local increments accumulate', [[['inc', 'a', 1], ['sync', 'a', 'a'], ['inc', 'a', 1], ['inc', 'd', 1]], ['a', 'b', 'c', 'd']], {'values': [2, 0, 0, 1], 'rejected': 0, 'state': [['a', 2]]})],
    2: [('repeated sync is idempotent', [[['inc', 'a', 3], ['sync', 'a', 'b'], ['sync', 'a', 'b'], ['inc', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c', 'd']], {'values': [5, 5, 0, 0], 'rejected': 0, 'state': [['a', 3], ['b', 2]]}), ('transitive gossip carries third-party slots', [[['inc', 'a', 2], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['inc', 'c', 1], ['sync', 'c', 'd']], ['a', 'b', 'c', 'd']], {'values': [2, 2, 3, 3], 'rejected': 0, 'state': [['a', 2]]}), ('stale path does not regress a slot', [[['inc', 'a', 1], ['sync', 'a', 'd'], ['inc', 'a', 2], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['sync', 'd', 'c']], ['a', 'b', 'c', 'd']], {'values': [3, 3, 3, 1], 'rejected': 0, 'state': [['a', 3]]}), ('zero and negative amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', -2], ['inc', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 2, 0], 'rejected': 2, 'state': [['a', 3], ['c', 2]]}), ('concurrent increments all survive', [[['inc', 'a', 2], ['inc', 'b', 4], ['inc', 'c', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c', 'd']], {'values': [7, 7, 7, 0], 'rejected': 0, 'state': [['a', 2], ['b', 4], ['c', 1]]}), ('empty history', [[], ['a', 'b', 'c', 'd']], {'values': [0, 0, 0, 0], 'rejected': 0, 'state': []}), ('repeated local increments accumulate', [[['inc', 'a', 2], ['sync', 'a', 'a'], ['inc', 'a', 1], ['inc', 'd', 2]], ['a', 'b', 'c', 'd']], {'values': [3, 0, 0, 2], 'rejected': 0, 'state': [['a', 3]]})],
    3: [('repeated sync is idempotent', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['sync', 'a', 'b'], ['inc', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c', 'd']], {'values': [6, 6, 0, 0], 'rejected': 0, 'state': [['a', 4], ['b', 2]]}), ('transitive gossip carries third-party slots', [[['inc', 'a', 3], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['inc', 'c', 1], ['sync', 'c', 'd']], ['a', 'b', 'c', 'd']], {'values': [3, 3, 4, 4], 'rejected': 0, 'state': [['a', 3]]}), ('stale path does not regress a slot', [[['inc', 'a', 1], ['sync', 'a', 'd'], ['inc', 'a', 3], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['sync', 'd', 'c']], ['a', 'b', 'c', 'd']], {'values': [4, 4, 4, 1], 'rejected': 0, 'state': [['a', 4]]}), ('zero and negative amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', -3], ['inc', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 2, 0], 'rejected': 2, 'state': [['a', 3], ['c', 2]]}), ('concurrent increments all survive', [[['inc', 'a', 3], ['inc', 'b', 5], ['inc', 'c', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c', 'd']], {'values': [9, 9, 9, 0], 'rejected': 0, 'state': [['a', 3], ['b', 5], ['c', 1]]}), ('empty history', [[], ['a', 'b', 'c', 'd']], {'values': [0, 0, 0, 0], 'rejected': 0, 'state': []}), ('repeated local increments accumulate', [[['inc', 'a', 3], ['sync', 'a', 'a'], ['inc', 'a', 1], ['inc', 'd', 3]], ['a', 'b', 'c', 'd']], {'values': [4, 0, 0, 3], 'rejected': 0, 'state': [['a', 4]]})],
    4: [('repeated sync is idempotent', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['sync', 'a', 'b'], ['inc', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c', 'd']], {'values': [7, 7, 0, 0], 'rejected': 0, 'state': [['a', 5], ['b', 2]]}), ('transitive gossip carries third-party slots', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['inc', 'c', 1], ['sync', 'c', 'd']], ['a', 'b', 'c', 'd']], {'values': [4, 4, 5, 5], 'rejected': 0, 'state': [['a', 4]]}), ('stale path does not regress a slot', [[['inc', 'a', 1], ['sync', 'a', 'd'], ['inc', 'a', 4], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['sync', 'd', 'c']], ['a', 'b', 'c', 'd']], {'values': [5, 5, 5, 1], 'rejected': 0, 'state': [['a', 5]]}), ('zero and negative amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', -4], ['inc', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 2, 0], 'rejected': 2, 'state': [['a', 3], ['c', 2]]}), ('concurrent increments all survive', [[['inc', 'a', 4], ['inc', 'b', 6], ['inc', 'c', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c', 'd']], {'values': [11, 11, 11, 0], 'rejected': 0, 'state': [['a', 4], ['b', 6], ['c', 1]]}), ('empty history', [[], ['a', 'b', 'c', 'd']], {'values': [0, 0, 0, 0], 'rejected': 0, 'state': []}), ('repeated local increments accumulate', [[['inc', 'a', 4], ['sync', 'a', 'a'], ['inc', 'a', 1], ['inc', 'd', 4]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 0, 4], 'rejected': 0, 'state': [['a', 5]]})],
    5: [('repeated sync is idempotent', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['sync', 'a', 'b'], ['inc', 'b', 2], ['sync', 'b', 'a']], ['a', 'b', 'c', 'd']], {'values': [8, 8, 0, 0], 'rejected': 0, 'state': [['a', 6], ['b', 2]]}), ('transitive gossip carries third-party slots', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['inc', 'c', 1], ['sync', 'c', 'd']], ['a', 'b', 'c', 'd']], {'values': [5, 5, 6, 6], 'rejected': 0, 'state': [['a', 5]]}), ('stale path does not regress a slot', [[['inc', 'a', 1], ['sync', 'a', 'd'], ['inc', 'a', 5], ['sync', 'a', 'b'], ['sync', 'b', 'c'], ['sync', 'd', 'c']], ['a', 'b', 'c', 'd']], {'values': [6, 6, 6, 1], 'rejected': 0, 'state': [['a', 6]]}), ('zero and negative amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', -5], ['inc', 'c', 2], ['sync', 'c', 'a'], ['inc', 'a', 3]], ['a', 'b', 'c', 'd']], {'values': [5, 0, 2, 0], 'rejected': 2, 'state': [['a', 3], ['c', 2]]}), ('concurrent increments all survive', [[['inc', 'a', 5], ['inc', 'b', 7], ['inc', 'c', 1], ['sync', 'a', 'b'], ['sync', 'c', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c', 'd']], {'values': [13, 13, 13, 0], 'rejected': 0, 'state': [['a', 5], ['b', 7], ['c', 1]]}), ('empty history', [[], ['a', 'b', 'c', 'd']], {'values': [0, 0, 0, 0], 'rejected': 0, 'state': []}), ('repeated local increments accumulate', [[['inc', 'a', 5], ['sync', 'a', 'a'], ['inc', 'a', 1], ['inc', 'd', 5]], ['a', 'b', 'c', 'd']], {'values': [6, 0, 0, 5], 'rejected': 0, 'state': [['a', 6]]})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
repeated sync is idempotent{'rejected': 0, 'state': [['a', 2], ['b', 2]], 'values': [4, 4, 0, 0]}{'rejected': 0, 'state': [['a', 2], ['b', 2]], 'values': [4, 4, 0, 0]}Passed
transitive gossip carries third-party slots{'rejected': 0, 'state': [['a', 1]], 'values': [1, 1, 2, 2]}{'rejected': 0, 'state': [['a', 1]], 'values': [1, 1, 2, 2]}Passed
stale path does not regress a slot{'rejected': 0, 'state': [['a', 2]], 'values': [2, 2, 2, 1]}{'rejected': 0, 'state': [['a', 2]], 'values': [2, 2, 2, 1]}Passed
zero and negative amounts are rejected{'rejected': 2, 'state': [['a', 3], ['c', 2]], 'values': [5, 0, 2, 0]}{'rejected': 2, 'state': [['a', 3], ['c', 2]], 'values': [5, 0, 2, 0]}Passed
concurrent increments all survive{'rejected': 0, 'state': [['a', 1], ['b', 3], ['c', 1]], 'values': [5, 5, 5, 0]}{'rejected': 0, 'state': [['a', 1], ['b', 3], ['c', 1]], 'values': [5, 5, 5, 0]}Passed
empty history{'rejected': 0, 'state': [], 'values': [0, 0, 0, 0]}{'rejected': 0, 'state': [], 'values': [0, 0, 0, 0]}Passed
repeated local increments accumulate{'rejected': 0, 'state': [['a', 2]], 'values': [2, 0, 0, 1]}{'rejected': 0, 'state': [['a', 2]], 'values': [2, 0, 0, 1]}Passed

SHA-256 / 9e8069d5c32f505cb53f08f69d496ae2a7e7337ee6340ea7bd3b43e518eb1ce6

Verification & scope

A deterministic, bounded teaching model of one replicated data type with stipulated operation and merge rules; it is not a production CRDT library and makes no claim of conformance to any specific published design. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:49:00.654360+00:00.

Case digest / 53c575110121040dc938396087dd43d49100a91598b52e7b0a90d24fc614d481