FA-74941 / CRDT convergence / Open access
Observed-remove set with unique tags: merge does not carry tombstones · case 01
A remove never takes effect on replicas other than the one where it happened.
ROOT CAUSE
The merge omits the tombstone union, so the receiver never learns which tags were removed.
VERIFIED REPAIR
Union the sender's tombstones into the receiver before filtering live tags.
Unsuccessful approach: Replacing the receiver's tombstones with the sender's forgets the receiver's own removes.
Case contract
Each add at replica r creates tag "r:k" where k is r's add counter. A remove at r tombstones only the tags of that element r currently observes and removes them locally. ["merge", s, d] unions tombstones and live tags into d, then subtracts d's tombstones and drops elements with no live tags. Return sorted members per replica.
Why this case matters
Observed-remove sets give add-wins semantics for concurrent add/remove pairs.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ops, replicas):
seq = {r: 0 for r in replicas}
live = {r: {} for r in replicas}
dead = {r: set() for r in replicas}
for op in ops:
kind = op[0]
if kind == 'add':
r, e = op[1], op[2]
seq[r] += 1
live[r].setdefault(e, set()).add(r + ':' + str(seq[r]))
elif kind == 'rem':
r, e = op[1], op[2]
dead[r] |= live[r].pop(e, set())
else:
s, d = op[1], op[2]
for e, tags in live[s].items():
live[d].setdefault(e, set()).update(tags)
for e in list(live[d]):
live[d][e] -= dead[d]
if not live[d][e]:
del live[d][e]
return [sorted(live[r]) for r in replicas]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e1'], ['merge', 'a', 'b'], ['rem', 'a', 'e1'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'p', 'q', 'r'], ['m0', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
2: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e2'], ['merge', 'a', 'b'], ['rem', 'a', 'e2'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'p', 'q', 'r'], ['m0', 'm1', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
3: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e3'], ['merge', 'a', 'b'], ['rem', 'a', 'e3'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['add', 'b', 'm2'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'm2', 'p', 'q', 'r'], ['m0', 'm1', 'm2', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
4: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e4'], ['merge', 'a', 'b'], ['rem', 'a', 'e4'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['add', 'b', 'm2'], ['add', 'b', 'm3'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'm2', 'm3', 'p', 'q', 'r'], ['m0', 'm1', 'm2', 'm3', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
5: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e5'], ['merge', 'a', 'b'], ['rem', 'a', 'e5'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['add', 'b', 'm2'], ['add', 'b', 'm3'], ['add', 'b', 'm4'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'm2', 'm3', 'm4', 'p', 'q', 'r'], ['m0', 'm1', 'm2', 'm3', 'm4', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
}[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 |
|---|---|---|---|
| concurrent add survives remove elsewhere | [['x'], ['x']] | [['x'], ['x']] | Passed |
| same counters on different replicas do not collide | [['x'], ['x']] | [['x'], ['x']] | Passed |
| removal propagates by merge | [[], ['e1']] | [[], []] | Failed |
| local remove is visible immediately | [['y'], []] | [['y'], []] | Passed |
| own earlier removes are not undone by stale peers | [['w'], ['w', 'z']] | [['w'], ['w']] | Failed |
| removed element absent from sender is dropped at receiver | [['k'], []] | [[], []] | Failed |
| multiple elements | [['m0', 'p', 'q', 'r'], ['m0', 'p', 'q', 'r']] | [['m0', 'p', 'q', 'r'], ['m0', 'p', 'q', 'r']] | Passed |
| receiver own tombstone blocks resurrected tag | [['t'], []] | [['t'], []] | Passed |
SHA-256 / 140b071d925384ed56dc1e03a7869a3f77f49ecc079021a7af53fcaf694d70e9
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ops, replicas):
seq = {r: 0 for r in replicas}
live = {r: {} for r in replicas}
dead = {r: set() for r in replicas}
for op in ops:
kind = op[0]
if kind == 'add':
r, e = op[1], op[2]
seq[r] += 1
live[r].setdefault(e, set()).add(r + ':' + str(seq[r]))
elif kind == 'rem':
r, e = op[1], op[2]
dead[r] |= live[r].pop(e, set())
else:
s, d = op[1], op[2]
dead[d] = set(dead[s])
for e, tags in live[s].items():
live[d].setdefault(e, set()).update(tags)
for e in list(live[d]):
live[d][e] -= dead[d]
if not live[d][e]:
del live[d][e]
return [sorted(live[r]) for r in replicas]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e1'], ['merge', 'a', 'b'], ['rem', 'a', 'e1'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'p', 'q', 'r'], ['m0', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
2: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e2'], ['merge', 'a', 'b'], ['rem', 'a', 'e2'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'p', 'q', 'r'], ['m0', 'm1', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
3: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e3'], ['merge', 'a', 'b'], ['rem', 'a', 'e3'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['add', 'b', 'm2'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'm2', 'p', 'q', 'r'], ['m0', 'm1', 'm2', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
4: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e4'], ['merge', 'a', 'b'], ['rem', 'a', 'e4'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['add', 'b', 'm2'], ['add', 'b', 'm3'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'm2', 'm3', 'p', 'q', 'r'], ['m0', 'm1', 'm2', 'm3', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
5: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e5'], ['merge', 'a', 'b'], ['rem', 'a', 'e5'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['add', 'b', 'm2'], ['add', 'b', 'm3'], ['add', 'b', 'm4'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'm2', 'm3', 'm4', 'p', 'q', 'r'], ['m0', 'm1', 'm2', 'm3', 'm4', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
}[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 |
|---|---|---|---|
| concurrent add survives remove elsewhere | [['x'], ['x']] | [['x'], ['x']] | Passed |
| same counters on different replicas do not collide | [['x'], ['x']] | [['x'], ['x']] | Passed |
| removal propagates by merge | [[], []] | [[], []] | Passed |
| local remove is visible immediately | [['y'], []] | [['y'], []] | Passed |
| own earlier removes are not undone by stale peers | [['w', 'z'], ['w', 'z']] | [['w'], ['w']] | Failed |
| removed element absent from sender is dropped at receiver | [[], []] | [[], []] | Passed |
| multiple elements | [['m0', 'p', 'q', 'r'], ['m0', 'p', 'q', 'r']] | [['m0', 'p', 'q', 'r'], ['m0', 'p', 'q', 'r']] | Passed |
| receiver own tombstone blocks resurrected tag | [['t'], ['t']] | [['t'], []] | Failed |
SHA-256 / e1c8e33976566cebbf428e76548bca7bf74c69b296d35174628511c2ed8ffb83
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ops, replicas):
seq = {r: 0 for r in replicas}
live = {r: {} for r in replicas}
dead = {r: set() for r in replicas}
for op in ops:
kind = op[0]
if kind == 'add':
r, e = op[1], op[2]
seq[r] += 1
live[r].setdefault(e, set()).add(r + ':' + str(seq[r]))
elif kind == 'rem':
r, e = op[1], op[2]
dead[r] |= live[r].pop(e, set())
else:
s, d = op[1], op[2]
dead[d] |= dead[s]
for e, tags in live[s].items():
live[d].setdefault(e, set()).update(tags)
for e in list(live[d]):
live[d][e] -= dead[d]
if not live[d][e]:
del live[d][e]
return [sorted(live[r]) for r in replicas]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e1'], ['merge', 'a', 'b'], ['rem', 'a', 'e1'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'p', 'q', 'r'], ['m0', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
2: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e2'], ['merge', 'a', 'b'], ['rem', 'a', 'e2'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'p', 'q', 'r'], ['m0', 'm1', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
3: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e3'], ['merge', 'a', 'b'], ['rem', 'a', 'e3'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['add', 'b', 'm2'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'm2', 'p', 'q', 'r'], ['m0', 'm1', 'm2', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
4: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e4'], ['merge', 'a', 'b'], ['rem', 'a', 'e4'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['add', 'b', 'm2'], ['add', 'b', 'm3'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'm2', 'm3', 'p', 'q', 'r'], ['m0', 'm1', 'm2', 'm3', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
5: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e5'], ['merge', 'a', 'b'], ['rem', 'a', 'e5'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['add', 'b', 'm2'], ['add', 'b', 'm3'], ['add', 'b', 'm4'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'm2', 'm3', 'm4', 'p', 'q', 'r'], ['m0', 'm1', 'm2', 'm3', 'm4', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
}[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 |
|---|---|---|---|
| concurrent add survives remove elsewhere | [['x'], ['x']] | [['x'], ['x']] | Passed |
| same counters on different replicas do not collide | [['x'], ['x']] | [['x'], ['x']] | Passed |
| removal propagates by merge | [[], []] | [[], []] | Passed |
| local remove is visible immediately | [['y'], []] | [['y'], []] | Passed |
| own earlier removes are not undone by stale peers | [['w'], ['w']] | [['w'], ['w']] | Passed |
| removed element absent from sender is dropped at receiver | [[], []] | [[], []] | Passed |
| multiple elements | [['m0', 'p', 'q', 'r'], ['m0', 'p', 'q', 'r']] | [['m0', 'p', 'q', 'r'], ['m0', 'p', 'q', 'r']] | Passed |
| receiver own tombstone blocks resurrected tag | [['t'], []] | [['t'], []] | Passed |
SHA-256 / 82f00ca260a448b855640660956716535c72ae143c297514f6470809f1fd720e
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:01.536157+00:00.
Case digest / 0e7477d61ce1aae53e404fb77f767716128df58634f7f2cdf970eec81170a290