broken_source:
"""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(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)

source:
"""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(e + ':' + 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)

prompt:
Removing an element at one replica also cancels a concurrent add of the same element elsewhere.

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.

split: open-access


broken_source:
"""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]
            live[r].pop(e, None)
        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)

meaning: Fixture-count band, not measured model difficulty

deps: stdlib

source:
"""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].get(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)

prompt:
Removed elements come back as soon as a peer that still holds them merges in.

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.

split: open-access


broken_source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(ops, replicas):
    seq = {r: 0 for r in replicas}
    live = {r: {} for r in replicas}
    dead = {r: set() for r in replicas}
    for op in ops:
        kind = op[0]
        if kind == 'add':
            r, e = op[1], op[2]
            seq[r] += 1
            live[r].setdefault(e, set()).add(r + ':' + str(seq[r]))
        elif kind == 'rem':
            r, e = op[1], op[2]
            dead[r] |= live[r].pop(e, set())
        else:
            s, d = op[1], op[2]
            for e, tags in live[s].items():
                live[d].setdefault(e, set()).update(tags)
            for e in list(live[d]):
                live[d][e] -= dead[d]
                if not live[d][e]:
                    del live[d][e]
    return [sorted(live[r]) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e1'], ['merge', 'a', 'b'], ['rem', 'a', 'e1'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'p', 'q', 'r'], ['m0', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
    2: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e2'], ['merge', 'a', 'b'], ['rem', 'a', 'e2'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'p', 'q', 'r'], ['m0', 'm1', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
    3: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e3'], ['merge', 'a', 'b'], ['rem', 'a', 'e3'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['add', 'b', 'm2'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'm2', 'p', 'q', 'r'], ['m0', 'm1', 'm2', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
    4: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e4'], ['merge', 'a', 'b'], ['rem', 'a', 'e4'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['add', 'b', 'm2'], ['add', 'b', 'm3'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'm2', 'm3', 'p', 'q', 'r'], ['m0', 'm1', 'm2', 'm3', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
    5: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e5'], ['merge', 'a', 'b'], ['rem', 'a', 'e5'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['add', 'b', 'm2'], ['add', 'b', 'm3'], ['add', 'b', 'm4'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'm2', 'm3', 'm4', 'p', 'q', 'r'], ['m0', 'm1', 'm2', 'm3', 'm4', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

source:
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(ops, replicas):
    seq = {r: 0 for r in replicas}
    live = {r: {} for r in replicas}
    dead = {r: set() for r in replicas}
    for op in ops:
        kind = op[0]
        if kind == 'add':
            r, e = op[1], op[2]
            seq[r] += 1
            live[r].setdefault(e, set()).add(r + ':' + str(seq[r]))
        elif kind == 'rem':
            r, e = op[1], op[2]
            dead[r] |= live[r].pop(e, set())
        else:
            s, d = op[1], op[2]
            dead[d] = set(dead[s])
            for e, tags in live[s].items():
                live[d].setdefault(e, set()).update(tags)
            for e in list(live[d]):
                live[d][e] -= dead[d]
                if not live[d][e]:
                    del live[d][e]
    return [sorted(live[r]) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e1'], ['merge', 'a', 'b'], ['rem', 'a', 'e1'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'p', 'q', 'r'], ['m0', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
    2: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e2'], ['merge', 'a', 'b'], ['rem', 'a', 'e2'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'p', 'q', 'r'], ['m0', 'm1', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
    3: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e3'], ['merge', 'a', 'b'], ['rem', 'a', 'e3'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['add', 'b', 'm2'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'm2', 'p', 'q', 'r'], ['m0', 'm1', 'm2', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
    4: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e4'], ['merge', 'a', 'b'], ['rem', 'a', 'e4'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['add', 'b', 'm2'], ['add', 'b', 'm3'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'm2', 'm3', 'p', 'q', 'r'], ['m0', 'm1', 'm2', 'm3', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
    5: [('concurrent add survives remove elsewhere', [[['add', 'a', 'x'], ['merge', 'a', 'b'], ['rem', 'b', 'x'], ['add', 'a', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('same counters on different replicas do not collide', [[['add', 'a', 'x'], ['add', 'b', 'x'], ['rem', 'b', 'x'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('removal propagates by merge', [[['add', 'a', 'e5'], ['merge', 'a', 'b'], ['rem', 'a', 'e5'], ['merge', 'a', 'b']], ['a', 'b']], [[], []]), ('local remove is visible immediately', [[['add', 'a', 'x'], ['add', 'a', 'y'], ['rem', 'a', 'x']], ['a', 'b']], [['y'], []]), ('own earlier removes are not undone by stale peers', [[['add', 'a', 'z'], ['merge', 'a', 'b'], ['rem', 'a', 'z'], ['add', 'b', 'w'], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['w'], ['w']]), ('removed element absent from sender is dropped at receiver', [[['add', 'b', 'k'], ['merge', 'b', 'a'], ['rem', 'b', 'k'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('multiple elements', [[['add', 'a', 'p'], ['add', 'b', 'q'], ['add', 'a', 'r'], ['add', 'b', 'm0'], ['add', 'b', 'm1'], ['add', 'b', 'm2'], ['add', 'b', 'm3'], ['add', 'b', 'm4'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['m0', 'm1', 'm2', 'm3', 'm4', 'p', 'q', 'r'], ['m0', 'm1', 'm2', 'm3', 'm4', 'p', 'q', 'r']]), ('receiver own tombstone blocks resurrected tag', [[['add', 'a', 't'], ['merge', 'a', 'b'], ['rem', 'b', 't'], ['merge', 'a', 'b']], ['a', 'b']], [['t'], []])],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

prompt:
A remove never takes effect on replicas other than the one where it happened.

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.

split: open-access


broken_source:
"""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[s]):
                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)

source:
"""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[s]
                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)

prompt:
An element removed at the sender stays visible at the receiver after merge.

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.

split: open-access


broken_source:
"""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)

source:
"""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)

prompt:
A fully removed element keeps appearing in the membership list after merge.

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.

split: open-access