{"abstract":"An element removed at the sender stays visible at the receiver after merge.","category":"CRDT convergence","checks":8,"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.","evaluation_group":"w2-crdt-convergence-or-set-unique-tags","failed_approach":"Filtering with only the sender's tombstones lets a stale peer resurrect tags the receiver itself removed.","family":"w2-crdt-convergence-or-set-unique-tags-filter-scope","id":"FA-74946","implementations":{"attempt":{"sha256":"03504373afff73011ffa2da8fa1d550048f2879da51d59dcbbfe90f3778230a8","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(ops, replicas):\n    seq = {r: 0 for r in replicas}\n    live = {r: {} for r in replicas}\n    dead = {r: set() for r in replicas}\n    for op in ops:\n        kind = op[0]\n        if kind == 'add':\n            r, e = op[1], op[2]\n            seq[r] += 1\n            live[r].setdefault(e, set()).add(r + ':' + str(seq[r]))\n        elif kind == 'rem':\n            r, e = op[1], op[2]\n            dead[r] |= live[r].pop(e, set())\n        else:\n            s, d = op[1], op[2]\n            dead[d] |= dead[s]\n            for e, tags in live[s].items():\n                live[d].setdefault(e, set()).update(tags)\n            for e in list(live[d]):\n                live[d][e] -= dead[s]\n                if not live[d][e]:\n                    del live[d][e]\n    return [sorted(live[r]) for r in replicas]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = {\n    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'], []])],\n    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'], []])],\n    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'], []])],\n    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'], []])],\n    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}[N]\nfor label, args, expected in cases:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"833d4f4857108536bfeed9bd8f4fdd0d9a1ea87aa9eaabf3b6e974528c745084","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(ops, replicas):\n    seq = {r: 0 for r in replicas}\n    live = {r: {} for r in replicas}\n    dead = {r: set() for r in replicas}\n    for op in ops:\n        kind = op[0]\n        if kind == 'add':\n            r, e = op[1], op[2]\n            seq[r] += 1\n            live[r].setdefault(e, set()).add(r + ':' + str(seq[r]))\n        elif kind == 'rem':\n            r, e = op[1], op[2]\n            dead[r] |= live[r].pop(e, set())\n        else:\n            s, d = op[1], op[2]\n            dead[d] |= dead[s]\n            for e, tags in live[s].items():\n                live[d].setdefault(e, set()).update(tags)\n            for e in list(live[s]):\n                live[d][e] -= dead[d]\n                if not live[d][e]:\n                    del live[d][e]\n    return [sorted(live[r]) for r in replicas]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = {\n    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'], []])],\n    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'], []])],\n    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'], []])],\n    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'], []])],\n    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}[N]\nfor label, args, expected in cases:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"82f00ca260a448b855640660956716535c72ae143c297514f6470809f1fd720e","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(ops, replicas):\n    seq = {r: 0 for r in replicas}\n    live = {r: {} for r in replicas}\n    dead = {r: set() for r in replicas}\n    for op in ops:\n        kind = op[0]\n        if kind == 'add':\n            r, e = op[1], op[2]\n            seq[r] += 1\n            live[r].setdefault(e, set()).add(r + ':' + str(seq[r]))\n        elif kind == 'rem':\n            r, e = op[1], op[2]\n            dead[r] |= live[r].pop(e, set())\n        else:\n            s, d = op[1], op[2]\n            dead[d] |= dead[s]\n            for e, tags in live[s].items():\n                live[d].setdefault(e, set()).update(tags)\n            for e in list(live[d]):\n                live[d][e] -= dead[d]\n                if not live[d][e]:\n                    del live[d][e]\n    return [sorted(live[r]) for r in replicas]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = {\n    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'], []])],\n    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'], []])],\n    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'], []])],\n    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'], []])],\n    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}[N]\nfor label, args, expected in cases:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-crdt-convergence-or-set-unique-tags-filter-scope","generated_at":"2026-09-29T14:49:01.579464+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Observed-remove sets give add-wins semantics for concurrent add/remove pairs.","repair":"After the union, filter every element held by the receiver against its tombstones.","root_cause":"Tombstone filtering iterates the sender's live elements, skipping elements the sender has already removed.","sha256":"595a2459f4f0e3bb93b4aeebc343492eee93b3551cacfd5bfb32525d0fc53419","title":"Observed-remove set with unique tags: merge filters only elements the sender still holds · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":42.578,"exit_code":1,"observations":[{"actual":[["x"],["x"]],"check":"concurrent add survives remove elsewhere","expected":[["x"],["x"]],"passed":true},{"actual":[["x"],["x"]],"check":"same counters on different replicas do not collide","expected":[["x"],["x"]],"passed":true},{"actual":[[],[]],"check":"removal propagates by merge","expected":[[],[]],"passed":true},{"actual":[["y"],[]],"check":"local remove is visible immediately","expected":[["y"],[]],"passed":true},{"actual":[["w","z"],["w"]],"check":"own earlier removes are not undone by stale peers","expected":[["w"],["w"]],"passed":false},{"actual":[[],[]],"check":"removed element absent from sender is dropped at receiver","expected":[[],[]],"passed":true},{"actual":[["m0","p","q","r"],["m0","p","q","r"]],"check":"multiple elements","expected":[["m0","p","q","r"],["m0","p","q","r"]],"passed":true},{"actual":[["t"],["t"]],"check":"receiver own tombstone blocks resurrected tag","expected":[["t"],[]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"concurrent add survives remove elsewhere\", \"actual\": [[\"x\"], [\"x\"]], \"expected\": [[\"x\"], [\"x\"]], \"passed\": true}, {\"check\": \"same counters on different replicas do not collide\", \"actual\": [[\"x\"], [\"x\"]], \"expected\": [[\"x\"], [\"x\"]], \"passed\": true}, {\"check\": \"removal propagates by merge\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}, {\"check\": \"local remove is visible immediately\", \"actual\": [[\"y\"], []], \"expected\": [[\"y\"], []], \"passed\": true}, {\"check\": \"own earlier removes are not undone by stale peers\", \"actual\": [[\"w\", \"z\"], [\"w\"]], \"expected\": [[\"w\"], [\"w\"]], \"passed\": false}, {\"check\": \"removed element absent from sender is dropped at receiver\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}, {\"check\": \"multiple elements\", \"actual\": [[\"m0\", \"p\", \"q\", \"r\"], [\"m0\", \"p\", \"q\", \"r\"]], \"expected\": [[\"m0\", \"p\", \"q\", \"r\"], [\"m0\", \"p\", \"q\", \"r\"]], \"passed\": true}, {\"check\": \"receiver own tombstone blocks resurrected tag\", \"actual\": [[\"t\"], [\"t\"]], \"expected\": [[\"t\"], []], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":41.04,"exit_code":1,"observations":[{"actual":[["x"],["x"]],"check":"concurrent add survives remove elsewhere","expected":[["x"],["x"]],"passed":true},{"actual":[["x"],["x"]],"check":"same counters on different replicas do not collide","expected":[["x"],["x"]],"passed":true},{"actual":[[],["e1"]],"check":"removal propagates by merge","expected":[[],[]],"passed":false},{"actual":[["y"],[]],"check":"local remove is visible immediately","expected":[["y"],[]],"passed":true},{"actual":[["w"],["w","z"]],"check":"own earlier removes are not undone by stale peers","expected":[["w"],["w"]],"passed":false},{"actual":[["k"],[]],"check":"removed element absent from sender is dropped at receiver","expected":[[],[]],"passed":false},{"actual":[["m0","p","q","r"],["m0","p","q","r"]],"check":"multiple elements","expected":[["m0","p","q","r"],["m0","p","q","r"]],"passed":true},{"actual":[["t"],[]],"check":"receiver own tombstone blocks resurrected tag","expected":[["t"],[]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"concurrent add survives remove elsewhere\", \"actual\": [[\"x\"], [\"x\"]], \"expected\": [[\"x\"], [\"x\"]], \"passed\": true}, {\"check\": \"same counters on different replicas do not collide\", \"actual\": [[\"x\"], [\"x\"]], \"expected\": [[\"x\"], [\"x\"]], \"passed\": true}, {\"check\": \"removal propagates by merge\", \"actual\": [[], [\"e1\"]], \"expected\": [[], []], \"passed\": false}, {\"check\": \"local remove is visible immediately\", \"actual\": [[\"y\"], []], \"expected\": [[\"y\"], []], \"passed\": true}, {\"check\": \"own earlier removes are not undone by stale peers\", \"actual\": [[\"w\"], [\"w\", \"z\"]], \"expected\": [[\"w\"], [\"w\"]], \"passed\": false}, {\"check\": \"removed element absent from sender is dropped at receiver\", \"actual\": [[\"k\"], []], \"expected\": [[], []], \"passed\": false}, {\"check\": \"multiple elements\", \"actual\": [[\"m0\", \"p\", \"q\", \"r\"], [\"m0\", \"p\", \"q\", \"r\"]], \"expected\": [[\"m0\", \"p\", \"q\", \"r\"], [\"m0\", \"p\", \"q\", \"r\"]], \"passed\": true}, {\"check\": \"receiver own tombstone blocks resurrected tag\", \"actual\": [[\"t\"], []], \"expected\": [[\"t\"], []], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":42.711,"exit_code":0,"observations":[{"actual":[["x"],["x"]],"check":"concurrent add survives remove elsewhere","expected":[["x"],["x"]],"passed":true},{"actual":[["x"],["x"]],"check":"same counters on different replicas do not collide","expected":[["x"],["x"]],"passed":true},{"actual":[[],[]],"check":"removal propagates by merge","expected":[[],[]],"passed":true},{"actual":[["y"],[]],"check":"local remove is visible immediately","expected":[["y"],[]],"passed":true},{"actual":[["w"],["w"]],"check":"own earlier removes are not undone by stale peers","expected":[["w"],["w"]],"passed":true},{"actual":[[],[]],"check":"removed element absent from sender is dropped at receiver","expected":[[],[]],"passed":true},{"actual":[["m0","p","q","r"],["m0","p","q","r"]],"check":"multiple elements","expected":[["m0","p","q","r"],["m0","p","q","r"]],"passed":true},{"actual":[["t"],[]],"check":"receiver own tombstone blocks resurrected tag","expected":[["t"],[]],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"concurrent add survives remove elsewhere\", \"actual\": [[\"x\"], [\"x\"]], \"expected\": [[\"x\"], [\"x\"]], \"passed\": true}, {\"check\": \"same counters on different replicas do not collide\", \"actual\": [[\"x\"], [\"x\"]], \"expected\": [[\"x\"], [\"x\"]], \"passed\": true}, {\"check\": \"removal propagates by merge\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}, {\"check\": \"local remove is visible immediately\", \"actual\": [[\"y\"], []], \"expected\": [[\"y\"], []], \"passed\": true}, {\"check\": \"own earlier removes are not undone by stale peers\", \"actual\": [[\"w\"], [\"w\"]], \"expected\": [[\"w\"], [\"w\"]], \"passed\": true}, {\"check\": \"removed element absent from sender is dropped at receiver\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}, {\"check\": \"multiple elements\", \"actual\": [[\"m0\", \"p\", \"q\", \"r\"], [\"m0\", \"p\", \"q\", \"r\"]], \"expected\": [[\"m0\", \"p\", \"q\", \"r\"], [\"m0\", \"p\", \"q\", \"r\"]], \"passed\": true}, {\"check\": \"receiver own tombstone blocks resurrected tag\", \"actual\": [[\"t\"], []], \"expected\": [[\"t\"], []], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}