FA-74951 / CRDT convergence / Open access
Observed-remove set with unique tags: elements with no live tags remain members · case 01
A fully removed element keeps appearing in the membership list after merge.
ROOT CAUSE
After subtracting tombstones the merge keeps entries whose tag set became empty.
VERIFIED REPAIR
Delete any element whose live tag set is empty after filtering.
Unsuccessful approach: Cleaning up only elements the sender still lists misses elements the sender itself removed.
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]
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]
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', 'z'], ['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']] | [['t'], []] | Failed |
SHA-256 / 4c06098cf4a20de6ccf6f80b22a55c45d456353ca034c96a294925bdbea305cf
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] |= 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] and e in live[s]:
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 / 67ecca44dc86921836566b43e20d7a19f8fb1ba1bf6860ec150f1c8f70595696
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.601607+00:00.
Case digest / ad14d2eb70d56a00c5b6f118f72f0ca7958227e6bbe4f033571e2d8340b56417