FA-75136 / CRDT convergence / Open access

Tombstone garbage collection by causal stability: a tombstone equal to the stable point is kept · case 01

Tombstones that every member has acknowledged are retained one round too long.

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

ROOT CAUSE

Purging requires the stable point to strictly exceed the tombstone sequence.

VERIFIED REPAIR

Purge when the stable acknowledgement is at or above the tombstone sequence.

Unsuccessful approach: Allowing one below the stable point purges a tombstone that some member has not delivered.

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 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': ['y', 'z'], 'purged': ['x']}`	`{'kept': [], 'purged': ['x', 'y', 'z']}`	Failed
one lagging member blocks	`{'kept': ['x', 'y', 'z'], 'purged': []}`	`{'kept': ['z'], 'purged': ['x', 'y']}`	Failed
a silent member blocks	`{'kept': ['x', 'y', 'z'], 'purged': []}`	`{'kept': ['x', 'y', 'z'], 'purged': []}`	Passed
departed members do not block	`{'kept': ['y', 'z'], 'purged': ['x']}`	`{'kept': [], 'purged': ['x', 'y', 'z']}`	Failed
departed member stale report is ignored	`{'kept': ['y', 'z'], 'purged': ['x']}`	`{'kept': [], 'purged': ['x', 'y', 'z']}`	Failed
ack exactly equal to the tombstone	`{'kept': ['q'], 'purged': []}`	`{'kept': [], 'purged': ['q']}`	Failed
ack one below the tombstone	`{'kept': ['q'], 'purged': []}`	`{'kept': ['q'], 'purged': []}`	Passed
observer outside membership is ignored	`{'kept': ['y', 'z'], 'purged': ['x']}`	`{'kept': [], 'purged': ['x', 'y', 'z']}`	Failed
majority is not enough	`{'kept': ['m'], 'purged': []}`	`{'kept': ['m'], 'purged': []}`	Passed

SHA-256 / 05d388075ab69f07368e3579dd3fb3ac7ea4828b174dfee67c8d454fac0bc93e

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 live)
    purged, kept = [], []
    for elem, origin, seq in tombstones:
        if stable[origin] >= seq - 1:
            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': ['y', 'z'], 'purged': ['x']}`	`{'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': [], 'purged': ['q']}`	`{'kept': ['q'], 'purged': []}`	Failed
observer outside membership is ignored	`{'kept': [], 'purged': ['x', 'y', 'z']}`	`{'kept': [], 'purged': ['x', 'y', 'z']}`	Passed
majority is not enough	`{'kept': [], 'purged': ['m']}`	`{'kept': ['m'], 'purged': []}`	Failed

SHA-256 / 3b48f621cf6e3a86b1f922d2fcb19a47ab295f2a656f85c4e1aada99c45f5919

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.232886+00:00.

Case digest / fe821b464478c6b99c9948e3ceef22f85acff62a8e8adbf028891a0a47f147da