FA-75126 / CRDT convergence / Open access
Tombstone garbage collection by causal stability: silent members do not block purging · case 01
A member that has never reported is treated as caught up.
ROOT CAUSE
Stability iterates over replicas that reported acknowledgements instead of the live membership.
VERIFIED REPAIR
Iterate the live membership and treat a missing report as zero.
Unsuccessful approach: Taking the union with reporters also lets observers and departed members hold back collection.
Case contract
Tombstones are [element, origin, seq]. acks maps replica -> {origin: highest delivered seq}. The live membership is members minus departed. A tombstone is causally stable, and may be purged, when every live member has reported an ack for its origin at or above seq; a live member with no report counts as zero. Other reporters are ignored. Return sorted purged and kept elements.
Why this case matters
Sequence and set CRDTs can only discard tombstones once every replica is guaranteed to have seen the deletion.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(tombstones, acks, members, departed):
live = [mb for mb in members if mb not in departed]
stable = {}
for origin in sorted({t[1] for t in tombstones}):
stable[origin] = min(acks.get(mb, {}).get(origin, 0) for mb in acks if mb not in departed)
purged, kept = [], []
for elem, origin, seq in tombstones:
if stable[origin] >= seq:
purged.append(elem)
else:
kept.append(elem)
return {'purged': sorted(purged), 'kept': sorted(kept)}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('all members acknowledged', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 3, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 1, 'b': 2}, 'c': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 1]], {'a': {'b': 1}, 'b': {'b': 1}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 2]], {'a': {'b': 1}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
2: [('all members acknowledged', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 4, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 2, 'b': 2}, 'c': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 2]], {'a': {'b': 2}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 3]], {'a': {'b': 2}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
3: [('all members acknowledged', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 5, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 3]], {'a': {'b': 3}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 4]], {'a': {'b': 3}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
4: [('all members acknowledged', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 6, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 4]], {'a': {'b': 4}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 5]], {'a': {'b': 4}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
5: [('all members acknowledged', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 7, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 5]], {'a': {'b': 5}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 6]], {'a': {'b': 5}, 'b': {'b': 6}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
}[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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| all members acknowledged | {'kept': [], 'purged': ['x', 'y', 'z']} | {'kept': [], 'purged': ['x', 'y', 'z']} | Passed |
| one lagging member blocks | {'kept': ['z'], 'purged': ['x', 'y']} | {'kept': ['z'], 'purged': ['x', 'y']} | Passed |
| a silent member blocks | {'kept': [], 'purged': ['x', 'y', 'z']} | {'kept': ['x', 'y', 'z'], 'purged': []} | Failed |
| departed members do not block | {'kept': [], 'purged': ['x', 'y', 'z']} | {'kept': [], 'purged': ['x', 'y', 'z']} | Passed |
| departed member stale report is ignored | {'kept': [], 'purged': ['x', 'y', 'z']} | {'kept': [], 'purged': ['x', 'y', 'z']} | Passed |
| ack exactly equal to the tombstone | {'kept': [], 'purged': ['q']} | {'kept': [], 'purged': ['q']} | Passed |
| ack one below the tombstone | {'kept': ['q'], 'purged': []} | {'kept': ['q'], 'purged': []} | Passed |
| observer outside membership is ignored | {'kept': ['x', 'y', 'z'], 'purged': []} | {'kept': [], 'purged': ['x', 'y', 'z']} | Failed |
| majority is not enough | {'kept': ['m'], 'purged': []} | {'kept': ['m'], 'purged': []} | Passed |
SHA-256 / f2046e3d1a9b0a3d6416c000006c3e4ed4eaeabeb9bd1d8bf98c961c43ec7ccd
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(tombstones, acks, members, departed):
live = [mb for mb in members if mb not in departed]
stable = {}
for origin in sorted({t[1] for t in tombstones}):
stable[origin] = min(acks.get(mb, {}).get(origin, 0) for mb in set(live) | set(acks))
purged, kept = [], []
for elem, origin, seq in tombstones:
if stable[origin] >= seq:
purged.append(elem)
else:
kept.append(elem)
return {'purged': sorted(purged), 'kept': sorted(kept)}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('all members acknowledged', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 3, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 1, 'b': 2}, 'c': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 1]], {'a': {'b': 1}, 'b': {'b': 1}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 2]], {'a': {'b': 1}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
2: [('all members acknowledged', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 4, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 2, 'b': 2}, 'c': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 2]], {'a': {'b': 2}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 3]], {'a': {'b': 2}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
3: [('all members acknowledged', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 5, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 3]], {'a': {'b': 3}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 4]], {'a': {'b': 3}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
4: [('all members acknowledged', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 6, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 4]], {'a': {'b': 4}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 5]], {'a': {'b': 4}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
5: [('all members acknowledged', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 7, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 5]], {'a': {'b': 5}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 6]], {'a': {'b': 5}, 'b': {'b': 6}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
}[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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| all members acknowledged | {'kept': [], 'purged': ['x', 'y', 'z']} | {'kept': [], 'purged': ['x', 'y', 'z']} | Passed |
| one lagging member blocks | {'kept': ['z'], 'purged': ['x', 'y']} | {'kept': ['z'], 'purged': ['x', 'y']} | Passed |
| a silent member blocks | {'kept': ['x', 'y', 'z'], 'purged': []} | {'kept': ['x', 'y', 'z'], 'purged': []} | Passed |
| departed members do not block | {'kept': [], 'purged': ['x', 'y', 'z']} | {'kept': [], 'purged': ['x', 'y', 'z']} | Passed |
| departed member stale report is ignored | {'kept': ['x', 'y', 'z'], 'purged': []} | {'kept': [], 'purged': ['x', 'y', 'z']} | Failed |
| ack exactly equal to the tombstone | {'kept': [], 'purged': ['q']} | {'kept': [], 'purged': ['q']} | Passed |
| ack one below the tombstone | {'kept': ['q'], 'purged': []} | {'kept': ['q'], 'purged': []} | Passed |
| observer outside membership is ignored | {'kept': ['x', 'y', 'z'], 'purged': []} | {'kept': [], 'purged': ['x', 'y', 'z']} | Failed |
| majority is not enough | {'kept': ['m'], 'purged': []} | {'kept': ['m'], 'purged': []} | Passed |
SHA-256 / 6a8357a074da4bf884632fba2b69e1c3e18ad1119271ec3ce67e822dca23906d
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(tombstones, acks, members, departed):
live = [mb for mb in members if mb not in departed]
stable = {}
for origin in sorted({t[1] for t in tombstones}):
stable[origin] = min(acks.get(mb, {}).get(origin, 0) for mb in live)
purged, kept = [], []
for elem, origin, seq in tombstones:
if stable[origin] >= seq:
purged.append(elem)
else:
kept.append(elem)
return {'purged': sorted(purged), 'kept': sorted(kept)}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('all members acknowledged', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 3, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 1, 'b': 2}, 'c': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 1]], {'a': {'b': 1}, 'b': {'b': 1}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 2]], {'a': {'b': 1}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 1], ['y', 'b', 2], ['z', 'a', 3]], {'a': {'a': 3, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
2: [('all members acknowledged', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 4, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 2, 'b': 2}, 'c': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 2]], {'a': {'b': 2}, 'b': {'b': 2}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 3]], {'a': {'b': 2}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 2], ['y', 'b', 2], ['z', 'a', 4]], {'a': {'a': 4, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
3: [('all members acknowledged', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 5, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 3, 'b': 2}, 'c': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 3]], {'a': {'b': 3}, 'b': {'b': 3}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 4]], {'a': {'b': 3}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 3], ['y', 'b', 2], ['z', 'a', 5]], {'a': {'a': 5, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
4: [('all members acknowledged', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 6, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 4, 'b': 2}, 'c': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 4]], {'a': {'b': 4}, 'b': {'b': 4}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 5]], {'a': {'b': 4}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 4], ['y', 'b', 2], ['z', 'a', 6]], {'a': {'a': 6, 'b': 2}, 'b': {'a': 6, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
5: [('all members acknowledged', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 7, 'b': 3}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('one lagging member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 5, 'b': 2}, 'c': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': ['x', 'y'], 'kept': ['z']}), ('a silent member blocks', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], []], {'purged': [], 'kept': ['x', 'y', 'z']}), ('departed members do not block', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('departed member stale report is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'c': {'a': 0}}, ['a', 'b', 'c'], ['c']], {'purged': ['x', 'y', 'z'], 'kept': []}), ('ack exactly equal to the tombstone', [[['q', 'b', 5]], {'a': {'b': 5}, 'b': {'b': 5}}, ['a', 'b'], []], {'purged': ['q'], 'kept': []}), ('ack one below the tombstone', [[['q', 'b', 6]], {'a': {'b': 5}, 'b': {'b': 6}}, ['a', 'b'], []], {'purged': [], 'kept': ['q']}), ('observer outside membership is ignored', [[['x', 'a', 5], ['y', 'b', 2], ['z', 'a', 7]], {'a': {'a': 7, 'b': 2}, 'b': {'a': 7, 'b': 2}, 'obs': {}}, ['a', 'b'], []], {'purged': ['x', 'y', 'z'], 'kept': []}), ('majority is not enough', [[['m', 'c', 1]], {'a': {'c': 1}, 'b': {'c': 1}, 'c': {'c': 1}, 'd': {}}, ['a', 'b', 'c', 'd'], []], {'purged': [], 'kept': ['m']})],
}[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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| all members acknowledged | {'kept': [], 'purged': ['x', 'y', 'z']} | {'kept': [], 'purged': ['x', 'y', 'z']} | Passed |
| one lagging member blocks | {'kept': ['z'], 'purged': ['x', 'y']} | {'kept': ['z'], 'purged': ['x', 'y']} | Passed |
| a silent member blocks | {'kept': ['x', 'y', 'z'], 'purged': []} | {'kept': ['x', 'y', 'z'], 'purged': []} | Passed |
| departed members do not block | {'kept': [], 'purged': ['x', 'y', 'z']} | {'kept': [], 'purged': ['x', 'y', 'z']} | Passed |
| departed member stale report is ignored | {'kept': [], 'purged': ['x', 'y', 'z']} | {'kept': [], 'purged': ['x', 'y', 'z']} | Passed |
| ack exactly equal to the tombstone | {'kept': [], 'purged': ['q']} | {'kept': [], 'purged': ['q']} | Passed |
| ack one below the tombstone | {'kept': ['q'], 'purged': []} | {'kept': ['q'], 'purged': []} | Passed |
| observer outside membership is ignored | {'kept': [], 'purged': ['x', 'y', 'z']} | {'kept': [], 'purged': ['x', 'y', 'z']} | Passed |
| majority is not enough | {'kept': ['m'], 'purged': []} | {'kept': ['m'], 'purged': []} | Passed |
SHA-256 / ba1a97253e6c3733fedcf87fe984fcfff0d86b28e4dc15c54509efb7494a1142
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:03.205686+00:00.
Case digest / 08765a13dc75b66f547c0988791551f7b9f528ae22693fecc9f2ae4916dec8ec