{"abstract":"An edge removed on one replica remains visible on the others.","category":"CRDT convergence","checks":8,"contract":"Vertices and edges each have grow-only add and remove sets. A vertex is live when added and not removed; an edge is visible when added, not removed, and both endpoints are live. At the origin replica, adding an edge requires both endpoints live, removing a vertex requires no visible edge touching it in either direction, and removing an edge requires it visible; failed preconditions record the op index. [\"merge\", s, d] unions all four sets into d. Return sorted live vertices and visible edges per replica plus rejections.","evaluation_group":"w2-crdt-convergence-two-phase-graph","failed_approach":"Intersecting removed-edge sets forgets removals that only one replica has seen.","family":"w2-crdt-convergence-two-phase-graph-edge-tombstone-merge","id":"FA-75076","implementations":{"attempt":{"sha256":"86a67496161af2719786626738cd2c961190ee0e07ff5e75c926d5cdbc9ebce5","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(ops, replicas):\n    VA = {r: set() for r in replicas}\n    VR = {r: set() for r in replicas}\n    EA = {r: set() for r in replicas}\n    ER = {r: set() for r in replicas}\n    rejected = []\n    def vlive(r, v):\n        return v in VA[r] and v not in VR[r]\n    def evis(r, e):\n        return e in EA[r] and e not in ER[r] and vlive(r, e[0]) and vlive(r, e[1])\n    for i, op in enumerate(ops):\n        kind, r = op[0], op[1]\n        if kind == 'addv':\n            VA[r].add(op[2])\n        elif kind == 'remv':\n            v = op[2]\n            if not vlive(r, v) or any(evis(r, e) and v in e for e in EA[r]):\n                rejected.append(i)\n            else:\n                VR[r].add(v)\n        elif kind == 'adde':\n            e = (op[2], op[3])\n            if vlive(r, e[0]) and vlive(r, e[1]):\n                EA[r].add(e)\n            else:\n                rejected.append(i)\n        elif kind == 'reme':\n            e = (op[2], op[3])\n            if evis(r, e):\n                ER[r].add(e)\n            else:\n                rejected.append(i)\n        else:\n            d = op[2]\n            VA[d] |= VA[r]\n            VR[d] |= VR[r]\n            EA[d] |= EA[r]\n            ER[d] &= ER[r]\n    out = []\n    for r in replicas:\n        out.append([sorted(v for v in VA[r] if vlive(r, v)), sorted(list(e) for e in EA[r] if evis(r, e))])\n    return {'graphs': out, 'rejected': rejected}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = {\n    1: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w1'], ['adde', 'a', 'w1', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'p', 'q'], []]], 'rejected': []})],\n    2: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w2'], ['adde', 'a', 'w2', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'p', 'q'], []]], 'rejected': []})],\n    3: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w3'], ['adde', 'a', 'w3', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1'], ['addv', 'b', 'n2']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'n2', 'p', 'q'], []]], 'rejected': []})],\n    4: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w4'], ['adde', 'a', 'w4', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1'], ['addv', 'b', 'n2'], ['addv', 'b', 'n3']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'n2', 'n3', 'p', 'q'], []]], 'rejected': []})],\n    5: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w5'], ['adde', 'a', 'w5', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1'], ['addv', 'b', 'n2'], ['addv', 'b', 'n3'], ['addv', 'b', 'n4']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'n2', 'n3', 'n4', 'p', 'q'], []]], 'rejected': []})],\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":"55c0047abff2eb25f4cc80a949dbe15b837527c0b1869e875e8960da25a0b5f7","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(ops, replicas):\n    VA = {r: set() for r in replicas}\n    VR = {r: set() for r in replicas}\n    EA = {r: set() for r in replicas}\n    ER = {r: set() for r in replicas}\n    rejected = []\n    def vlive(r, v):\n        return v in VA[r] and v not in VR[r]\n    def evis(r, e):\n        return e in EA[r] and e not in ER[r] and vlive(r, e[0]) and vlive(r, e[1])\n    for i, op in enumerate(ops):\n        kind, r = op[0], op[1]\n        if kind == 'addv':\n            VA[r].add(op[2])\n        elif kind == 'remv':\n            v = op[2]\n            if not vlive(r, v) or any(evis(r, e) and v in e for e in EA[r]):\n                rejected.append(i)\n            else:\n                VR[r].add(v)\n        elif kind == 'adde':\n            e = (op[2], op[3])\n            if vlive(r, e[0]) and vlive(r, e[1]):\n                EA[r].add(e)\n            else:\n                rejected.append(i)\n        elif kind == 'reme':\n            e = (op[2], op[3])\n            if evis(r, e):\n                ER[r].add(e)\n            else:\n                rejected.append(i)\n        else:\n            d = op[2]\n            VA[d] |= VA[r]\n            VR[d] |= VR[r]\n            EA[d] |= EA[r]\n    out = []\n    for r in replicas:\n        out.append([sorted(v for v in VA[r] if vlive(r, v)), sorted(list(e) for e in EA[r] if evis(r, e))])\n    return {'graphs': out, 'rejected': rejected}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = {\n    1: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w1'], ['adde', 'a', 'w1', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'p', 'q'], []]], 'rejected': []})],\n    2: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w2'], ['adde', 'a', 'w2', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'p', 'q'], []]], 'rejected': []})],\n    3: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w3'], ['adde', 'a', 'w3', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1'], ['addv', 'b', 'n2']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'n2', 'p', 'q'], []]], 'rejected': []})],\n    4: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w4'], ['adde', 'a', 'w4', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1'], ['addv', 'b', 'n2'], ['addv', 'b', 'n3']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'n2', 'n3', 'p', 'q'], []]], 'rejected': []})],\n    5: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w5'], ['adde', 'a', 'w5', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1'], ['addv', 'b', 'n2'], ['addv', 'b', 'n3'], ['addv', 'b', 'n4']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'n2', 'n3', 'n4', 'p', 'q'], []]], 'rejected': []})],\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":"ee616f41ed40913648bb507ba5c16e92f7405514bb81255c774778f1e9752c7a","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(ops, replicas):\n    VA = {r: set() for r in replicas}\n    VR = {r: set() for r in replicas}\n    EA = {r: set() for r in replicas}\n    ER = {r: set() for r in replicas}\n    rejected = []\n    def vlive(r, v):\n        return v in VA[r] and v not in VR[r]\n    def evis(r, e):\n        return e in EA[r] and e not in ER[r] and vlive(r, e[0]) and vlive(r, e[1])\n    for i, op in enumerate(ops):\n        kind, r = op[0], op[1]\n        if kind == 'addv':\n            VA[r].add(op[2])\n        elif kind == 'remv':\n            v = op[2]\n            if not vlive(r, v) or any(evis(r, e) and v in e for e in EA[r]):\n                rejected.append(i)\n            else:\n                VR[r].add(v)\n        elif kind == 'adde':\n            e = (op[2], op[3])\n            if vlive(r, e[0]) and vlive(r, e[1]):\n                EA[r].add(e)\n            else:\n                rejected.append(i)\n        elif kind == 'reme':\n            e = (op[2], op[3])\n            if evis(r, e):\n                ER[r].add(e)\n            else:\n                rejected.append(i)\n        else:\n            d = op[2]\n            VA[d] |= VA[r]\n            VR[d] |= VR[r]\n            EA[d] |= EA[r]\n            ER[d] |= ER[r]\n    out = []\n    for r in replicas:\n        out.append([sorted(v for v in VA[r] if vlive(r, v)), sorted(list(e) for e in EA[r] if evis(r, e))])\n    return {'graphs': out, 'rejected': rejected}\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = {\n    1: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w1'], ['adde', 'a', 'w1', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'p', 'q'], []]], 'rejected': []})],\n    2: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w2'], ['adde', 'a', 'w2', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'p', 'q'], []]], 'rejected': []})],\n    3: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w3'], ['adde', 'a', 'w3', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1'], ['addv', 'b', 'n2']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'n2', 'p', 'q'], []]], 'rejected': []})],\n    4: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w4'], ['adde', 'a', 'w4', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1'], ['addv', 'b', 'n2'], ['addv', 'b', 'n3']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'n2', 'n3', 'p', 'q'], []]], 'rejected': []})],\n    5: [('edge between live vertices', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [['u', 'v'], [['u', 'v']]]], 'rejected': []}), ('edge to a missing vertex is rejected', [[['addv', 'a', 'u'], ['adde', 'a', 'u', 'w5'], ['adde', 'a', 'w5', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [1, 2]}), ('edge to a removed vertex is rejected', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['remv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['adde', 'a', 'v', 'u']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': [3, 4]}), ('vertex with incoming edge cannot be removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['remv', 'a', 'v'], ['remv', 'a', 'u']], ['a', 'b']], {'graphs': [[['u', 'v'], [['u', 'v']]], [[], []]], 'rejected': [3, 4]}), ('vertex removable after its edge is removed', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['adde', 'a', 'u', 'v'], ['reme', 'a', 'u', 'v'], ['remv', 'a', 'v']], ['a', 'b']], {'graphs': [[['u'], []], [[], []]], 'rejected': []}), ('concurrent vertex removal hides dangling edge', [[['addv', 'a', 'u'], ['addv', 'a', 'v'], ['merge', 'a', 'b'], ['adde', 'a', 'u', 'v'], ['remv', 'b', 'v'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], {'graphs': [[['u'], []], [['u'], []]], 'rejected': []}), ('concurrent removal of the source vertex hides the edge', [[['addv', 'a', 'x'], ['addv', 'a', 'y'], ['merge', 'a', 'b'], ['adde', 'a', 'x', 'y'], ['remv', 'b', 'x'], ['merge', 'b', 'a']], ['a', 'b']], {'graphs': [[['y'], []], [['y'], []]], 'rejected': []}), ('edge removal propagates', [[['addv', 'a', 'p'], ['addv', 'a', 'q'], ['adde', 'a', 'p', 'q'], ['merge', 'a', 'b'], ['reme', 'b', 'p', 'q'], ['merge', 'b', 'a'], ['addv', 'b', 'n0'], ['addv', 'b', 'n1'], ['addv', 'b', 'n2'], ['addv', 'b', 'n3'], ['addv', 'b', 'n4']], ['a', 'b']], {'graphs': [[['p', 'q'], []], [['n0', 'n1', 'n2', 'n3', 'n4', 'p', 'q'], []]], 'rejected': []})],\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-two-phase-graph-edge-tombstone-merge","generated_at":"2026-09-29T14:49:02.843563+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Graph CRDTs must keep edges consistent with vertex removals that happen concurrently on other replicas.","repair":"Union the removed-edge set into the destination during merge.","root_cause":"Merge unions vertex sets and added edges but omits the removed-edge set.","sha256":"a61dea8b109f29c8c8428def59c8db5b381d42fbc070f9a3f1993824bb1bf532","title":"Two-phase graph: merge does not carry edge removals · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":40.508,"exit_code":1,"observations":[{"actual":{"graphs":[[["u","v"],[["u","v"]]],[["u","v"],[["u","v"]]]],"rejected":[]},"check":"edge between live vertices","expected":{"graphs":[[["u","v"],[["u","v"]]],[["u","v"],[["u","v"]]]],"rejected":[]},"passed":true},{"actual":{"graphs":[[["u"],[]],[[],[]]],"rejected":[1,2]},"check":"edge to a missing vertex is rejected","expected":{"graphs":[[["u"],[]],[[],[]]],"rejected":[1,2]},"passed":true},{"actual":{"graphs":[[["u"],[]],[[],[]]],"rejected":[3,4]},"check":"edge to a removed vertex is rejected","expected":{"graphs":[[["u"],[]],[[],[]]],"rejected":[3,4]},"passed":true},{"actual":{"graphs":[[["u","v"],[["u","v"]]],[[],[]]],"rejected":[3,4]},"check":"vertex with incoming edge cannot be removed","expected":{"graphs":[[["u","v"],[["u","v"]]],[[],[]]],"rejected":[3,4]},"passed":true},{"actual":{"graphs":[[["u"],[]],[[],[]]],"rejected":[]},"check":"vertex removable after its edge is removed","expected":{"graphs":[[["u"],[]],[[],[]]],"rejected":[]},"passed":true},{"actual":{"graphs":[[["u"],[]],[["u"],[]]],"rejected":[]},"check":"concurrent vertex removal hides dangling edge","expected":{"graphs":[[["u"],[]],[["u"],[]]],"rejected":[]},"passed":true},{"actual":{"graphs":[[["y"],[]],[["y"],[]]],"rejected":[]},"check":"concurrent removal of the source vertex hides the edge","expected":{"graphs":[[["y"],[]],[["y"],[]]],"rejected":[]},"passed":true},{"actual":{"graphs":[[["p","q"],[["p","q"]]],[["n0","p","q"],[]]],"rejected":[]},"check":"edge removal propagates","expected":{"graphs":[[["p","q"],[]],[["n0","p","q"],[]]],"rejected":[]},"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"edge between live vertices\", \"actual\": {\"graphs\": [[[\"u\", \"v\"], [[\"u\", \"v\"]]], [[\"u\", \"v\"], [[\"u\", \"v\"]]]], \"rejected\": []}, \"expected\": {\"graphs\": [[[\"u\", \"v\"], [[\"u\", \"v\"]]], [[\"u\", \"v\"], [[\"u\", \"v\"]]]], \"rejected\": []}, \"passed\": true}, {\"check\": \"edge to a missing vertex is rejected\", \"actual\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": [1, 2]}, \"expected\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": [1, 2]}, \"passed\": true}, {\"check\": \"edge to a removed vertex is rejected\", \"actual\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": [3, 4]}, \"expected\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": [3, 4]}, \"passed\": true}, {\"check\": \"vertex with incoming edge cannot be removed\", \"actual\": {\"graphs\": [[[\"u\", \"v\"], [[\"u\", \"v\"]]], [[], []]], \"rejected\": [3, 4]}, \"expected\": {\"graphs\": [[[\"u\", \"v\"], [[\"u\", \"v\"]]], [[], []]], \"rejected\": [3, 4]}, \"passed\": true}, {\"check\": \"vertex removable after its edge is removed\", \"actual\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": []}, \"expected\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": []}, \"passed\": true}, {\"check\": \"concurrent vertex removal hides dangling edge\", \"actual\": {\"graphs\": [[[\"u\"], []], [[\"u\"], []]], \"rejected\": []}, \"expected\": {\"graphs\": [[[\"u\"], []], [[\"u\"], []]], \"rejected\": []}, \"passed\": true}, {\"check\": \"concurrent removal of the source vertex hides the edge\", \"actual\": {\"graphs\": [[[\"y\"], []], [[\"y\"], []]], \"rejected\": []}, \"expected\": {\"graphs\": [[[\"y\"], []], [[\"y\"], []]], \"rejected\": []}, \"passed\": true}, {\"check\": \"edge removal propagates\", \"actual\": {\"graphs\": [[[\"p\", \"q\"], [[\"p\", \"q\"]]], [[\"n0\", \"p\", \"q\"], []]], \"rejected\": []}, \"expected\": {\"graphs\": [[[\"p\", \"q\"], []], [[\"n0\", \"p\", \"q\"], []]], \"rejected\": []}, \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":43.855,"exit_code":1,"observations":[{"actual":{"graphs":[[["u","v"],[["u","v"]]],[["u","v"],[["u","v"]]]],"rejected":[]},"check":"edge between live vertices","expected":{"graphs":[[["u","v"],[["u","v"]]],[["u","v"],[["u","v"]]]],"rejected":[]},"passed":true},{"actual":{"graphs":[[["u"],[]],[[],[]]],"rejected":[1,2]},"check":"edge to a missing vertex is rejected","expected":{"graphs":[[["u"],[]],[[],[]]],"rejected":[1,2]},"passed":true},{"actual":{"graphs":[[["u"],[]],[[],[]]],"rejected":[3,4]},"check":"edge to a removed vertex is rejected","expected":{"graphs":[[["u"],[]],[[],[]]],"rejected":[3,4]},"passed":true},{"actual":{"graphs":[[["u","v"],[["u","v"]]],[[],[]]],"rejected":[3,4]},"check":"vertex with incoming edge cannot be removed","expected":{"graphs":[[["u","v"],[["u","v"]]],[[],[]]],"rejected":[3,4]},"passed":true},{"actual":{"graphs":[[["u"],[]],[[],[]]],"rejected":[]},"check":"vertex removable after its edge is removed","expected":{"graphs":[[["u"],[]],[[],[]]],"rejected":[]},"passed":true},{"actual":{"graphs":[[["u"],[]],[["u"],[]]],"rejected":[]},"check":"concurrent vertex removal hides dangling edge","expected":{"graphs":[[["u"],[]],[["u"],[]]],"rejected":[]},"passed":true},{"actual":{"graphs":[[["y"],[]],[["y"],[]]],"rejected":[]},"check":"concurrent removal of the source vertex hides the edge","expected":{"graphs":[[["y"],[]],[["y"],[]]],"rejected":[]},"passed":true},{"actual":{"graphs":[[["p","q"],[["p","q"]]],[["n0","p","q"],[]]],"rejected":[]},"check":"edge removal propagates","expected":{"graphs":[[["p","q"],[]],[["n0","p","q"],[]]],"rejected":[]},"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"edge between live vertices\", \"actual\": {\"graphs\": [[[\"u\", \"v\"], [[\"u\", \"v\"]]], [[\"u\", \"v\"], [[\"u\", \"v\"]]]], \"rejected\": []}, \"expected\": {\"graphs\": [[[\"u\", \"v\"], [[\"u\", \"v\"]]], [[\"u\", \"v\"], [[\"u\", \"v\"]]]], \"rejected\": []}, \"passed\": true}, {\"check\": \"edge to a missing vertex is rejected\", \"actual\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": [1, 2]}, \"expected\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": [1, 2]}, \"passed\": true}, {\"check\": \"edge to a removed vertex is rejected\", \"actual\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": [3, 4]}, \"expected\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": [3, 4]}, \"passed\": true}, {\"check\": \"vertex with incoming edge cannot be removed\", \"actual\": {\"graphs\": [[[\"u\", \"v\"], [[\"u\", \"v\"]]], [[], []]], \"rejected\": [3, 4]}, \"expected\": {\"graphs\": [[[\"u\", \"v\"], [[\"u\", \"v\"]]], [[], []]], \"rejected\": [3, 4]}, \"passed\": true}, {\"check\": \"vertex removable after its edge is removed\", \"actual\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": []}, \"expected\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": []}, \"passed\": true}, {\"check\": \"concurrent vertex removal hides dangling edge\", \"actual\": {\"graphs\": [[[\"u\"], []], [[\"u\"], []]], \"rejected\": []}, \"expected\": {\"graphs\": [[[\"u\"], []], [[\"u\"], []]], \"rejected\": []}, \"passed\": true}, {\"check\": \"concurrent removal of the source vertex hides the edge\", \"actual\": {\"graphs\": [[[\"y\"], []], [[\"y\"], []]], \"rejected\": []}, \"expected\": {\"graphs\": [[[\"y\"], []], [[\"y\"], []]], \"rejected\": []}, \"passed\": true}, {\"check\": \"edge removal propagates\", \"actual\": {\"graphs\": [[[\"p\", \"q\"], [[\"p\", \"q\"]]], [[\"n0\", \"p\", \"q\"], []]], \"rejected\": []}, \"expected\": {\"graphs\": [[[\"p\", \"q\"], []], [[\"n0\", \"p\", \"q\"], []]], \"rejected\": []}, \"passed\": false}], \"passed\": false}\n"},"fixed":{"elapsed_ms":45.156,"exit_code":0,"observations":[{"actual":{"graphs":[[["u","v"],[["u","v"]]],[["u","v"],[["u","v"]]]],"rejected":[]},"check":"edge between live vertices","expected":{"graphs":[[["u","v"],[["u","v"]]],[["u","v"],[["u","v"]]]],"rejected":[]},"passed":true},{"actual":{"graphs":[[["u"],[]],[[],[]]],"rejected":[1,2]},"check":"edge to a missing vertex is rejected","expected":{"graphs":[[["u"],[]],[[],[]]],"rejected":[1,2]},"passed":true},{"actual":{"graphs":[[["u"],[]],[[],[]]],"rejected":[3,4]},"check":"edge to a removed vertex is rejected","expected":{"graphs":[[["u"],[]],[[],[]]],"rejected":[3,4]},"passed":true},{"actual":{"graphs":[[["u","v"],[["u","v"]]],[[],[]]],"rejected":[3,4]},"check":"vertex with incoming edge cannot be removed","expected":{"graphs":[[["u","v"],[["u","v"]]],[[],[]]],"rejected":[3,4]},"passed":true},{"actual":{"graphs":[[["u"],[]],[[],[]]],"rejected":[]},"check":"vertex removable after its edge is removed","expected":{"graphs":[[["u"],[]],[[],[]]],"rejected":[]},"passed":true},{"actual":{"graphs":[[["u"],[]],[["u"],[]]],"rejected":[]},"check":"concurrent vertex removal hides dangling edge","expected":{"graphs":[[["u"],[]],[["u"],[]]],"rejected":[]},"passed":true},{"actual":{"graphs":[[["y"],[]],[["y"],[]]],"rejected":[]},"check":"concurrent removal of the source vertex hides the edge","expected":{"graphs":[[["y"],[]],[["y"],[]]],"rejected":[]},"passed":true},{"actual":{"graphs":[[["p","q"],[]],[["n0","p","q"],[]]],"rejected":[]},"check":"edge removal propagates","expected":{"graphs":[[["p","q"],[]],[["n0","p","q"],[]]],"rejected":[]},"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"edge between live vertices\", \"actual\": {\"graphs\": [[[\"u\", \"v\"], [[\"u\", \"v\"]]], [[\"u\", \"v\"], [[\"u\", \"v\"]]]], \"rejected\": []}, \"expected\": {\"graphs\": [[[\"u\", \"v\"], [[\"u\", \"v\"]]], [[\"u\", \"v\"], [[\"u\", \"v\"]]]], \"rejected\": []}, \"passed\": true}, {\"check\": \"edge to a missing vertex is rejected\", \"actual\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": [1, 2]}, \"expected\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": [1, 2]}, \"passed\": true}, {\"check\": \"edge to a removed vertex is rejected\", \"actual\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": [3, 4]}, \"expected\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": [3, 4]}, \"passed\": true}, {\"check\": \"vertex with incoming edge cannot be removed\", \"actual\": {\"graphs\": [[[\"u\", \"v\"], [[\"u\", \"v\"]]], [[], []]], \"rejected\": [3, 4]}, \"expected\": {\"graphs\": [[[\"u\", \"v\"], [[\"u\", \"v\"]]], [[], []]], \"rejected\": [3, 4]}, \"passed\": true}, {\"check\": \"vertex removable after its edge is removed\", \"actual\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": []}, \"expected\": {\"graphs\": [[[\"u\"], []], [[], []]], \"rejected\": []}, \"passed\": true}, {\"check\": \"concurrent vertex removal hides dangling edge\", \"actual\": {\"graphs\": [[[\"u\"], []], [[\"u\"], []]], \"rejected\": []}, \"expected\": {\"graphs\": [[[\"u\"], []], [[\"u\"], []]], \"rejected\": []}, \"passed\": true}, {\"check\": \"concurrent removal of the source vertex hides the edge\", \"actual\": {\"graphs\": [[[\"y\"], []], [[\"y\"], []]], \"rejected\": []}, \"expected\": {\"graphs\": [[[\"y\"], []], [[\"y\"], []]], \"rejected\": []}, \"passed\": true}, {\"check\": \"edge removal propagates\", \"actual\": {\"graphs\": [[[\"p\", \"q\"], []], [[\"n0\", \"p\", \"q\"], []]], \"rejected\": []}, \"expected\": {\"graphs\": [[[\"p\", \"q\"], []], [[\"n0\", \"p\", \"q\"], []]], \"rejected\": []}, \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}