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

N = 1
observations = []
def solve(events, replicas):
    clock = {r: 0 for r in replicas}
    reg = {r: [None, 0, ''] for r in replicas}
    for ev in events:
        if ev[0] == 'set':
            r = ev[1]
            clock[r] += 1
            reg[r] = [ev[2], clock[r], r]
        else:
            s, d = ev[1], ev[2]
            inc = reg[s]
            clock[d] = max(clock[d], inc[1])
            if (inc[2], inc[1]) > (reg[d][2], reg[d][1]):
                reg[d] = list(inc)
    return {'values': [reg[r][0] for r in replicas], 'clocks': [clock[r] for r in replicas]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x1'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q1'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s0', 's0', 's0'], 'clocks': [2, 2, 2]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 4, 4]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv1'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv1', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    2: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x2'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q2'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s1', 's1', 's1'], 'clocks': [3, 3, 3]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 5, 5]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv2'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv2', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    3: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x3'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q3'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['set', 'a', 's2'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s2', 's2', 's2'], 'clocks': [4, 4, 4]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['set', 'b', 'b4'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 6, 6]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv3'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv3', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    4: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x4'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q4'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['set', 'a', 's2'], ['set', 'a', 's3'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s3', 's3', 's3'], 'clocks': [5, 5, 5]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['set', 'b', 'b4'], ['set', 'b', 'b5'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 7, 7]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv4'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv4', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    5: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x5'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q5'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['set', 'a', 's2'], ['set', 'a', 's3'], ['set', 'a', 's4'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s4', 's4', 's4'], 'clocks': [6, 6, 6]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['set', 'b', 'b4'], ['set', 'b', 'b5'], ['set', 'b', 'b6'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 8, 8]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv5'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv5', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
}[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(events, replicas):
    clock = {r: 0 for r in replicas}
    reg = {r: [None, 0, ''] for r in replicas}
    for ev in events:
        if ev[0] == 'set':
            r = ev[1]
            clock[r] += 1
            reg[r] = [ev[2], clock[r], r]
        else:
            s, d = ev[1], ev[2]
            inc = reg[s]
            clock[d] = max(clock[d], inc[1])
            if (inc[1], inc[2]) > (reg[d][1], d):
                reg[d] = list(inc)
    return {'values': [reg[r][0] for r in replicas], 'clocks': [clock[r] for r in replicas]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x1'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q1'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s0', 's0', 's0'], 'clocks': [2, 2, 2]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 4, 4]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv1'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv1', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    2: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x2'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q2'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s1', 's1', 's1'], 'clocks': [3, 3, 3]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 5, 5]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv2'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv2', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    3: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x3'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q3'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['set', 'a', 's2'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s2', 's2', 's2'], 'clocks': [4, 4, 4]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['set', 'b', 'b4'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 6, 6]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv3'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv3', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    4: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x4'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q4'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['set', 'a', 's2'], ['set', 'a', 's3'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s3', 's3', 's3'], 'clocks': [5, 5, 5]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['set', 'b', 'b4'], ['set', 'b', 'b5'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 7, 7]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv4'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv4', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    5: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x5'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q5'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['set', 'a', 's2'], ['set', 'a', 's3'], ['set', 'a', 's4'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s4', 's4', 's4'], 'clocks': [6, 6, 6]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['set', 'b', 'b4'], ['set', 'b', 'b5'], ['set', 'b', 'b6'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 8, 8]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv5'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv5', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
}[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 replica with a large id wins even with a much older write.

Each replica holds a register [value, clock, writer] and a Lamport clock, all starting at [None, 0, ""] and 0. ["set", r, v] increments r's clock and stamps v with (clock, r). ["send", s, d] delivers s's register to d: d's clock becomes max(own, incoming clock) and d adopts the incoming register when (clock, writer) is lexicographically larger. Return values and clocks per replica.

split: open-access


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

N = 1
observations = []
def solve(ops, replicas):
    A = {r: {} for r in replicas}
    R = {r: {} for r in replicas}
    for op in ops:
        if op[0] == 'merge':
            s, d = op[1], op[2]
            for src, dst in ((A[s], A[d]), (R[s], R[d])):
                for e, t in src.items():
                    if t > dst.get(e, -1):
                        dst[e] = t
        else:
            kind, r, e, t = op
            table = A[r] if kind == 'add' else R[r]
            if t > table.get(e, -1):
                table[e] = t
    def members(r):
        return sorted(e for e, t in A[r].items() if t > R[r].get(e, -1))
    return [members(r) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 1], ['rem', 'a', 'x', 1]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 2], ['rem', 'b', 'x', 2], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 6], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 3], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 5], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 5], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 1], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 2], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    2: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 2], ['rem', 'a', 'x', 2]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 3], ['rem', 'b', 'x', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 7], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 4], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 6], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 6], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 2], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 3], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    3: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 3], ['rem', 'a', 'x', 3]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 4], ['rem', 'b', 'x', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 8], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 5], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 7], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 6], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 7], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 3], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 4], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    4: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 4], ['rem', 'a', 'x', 4]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 5], ['rem', 'b', 'x', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 9], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 6], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 8], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 7], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 8], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 4], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 5], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    5: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 5], ['rem', 'a', 'x', 5]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 6], ['rem', 'b', 'x', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 6], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 10], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 7], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 9], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 8], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 9], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 5], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 6], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
}[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):
    A = {r: {} for r in replicas}
    R = {r: {} for r in replicas}
    for op in ops:
        if op[0] == 'merge':
            s, d = op[1], op[2]
            for src, dst in ((A[s], A[d]), (R[s], R[d])):
                for e, t in src.items():
                    if t > dst.get(e, -1):
                        dst[e] = t
        else:
            kind, r, e, t = op
            if kind == 'rem' and A[r].get(e) == t:
                continue
            table = A[r] if kind == 'add' else R[r]
            if t > table.get(e, -1):
                table[e] = t
    def members(r):
        return sorted(e for e, t in A[r].items() if t > R[r].get(e, -1))
    return [members(r) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 1], ['rem', 'a', 'x', 1]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 2], ['rem', 'b', 'x', 2], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 6], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 3], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 5], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 5], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 1], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 2], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    2: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 2], ['rem', 'a', 'x', 2]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 3], ['rem', 'b', 'x', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 7], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 4], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 6], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 6], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 2], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 3], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    3: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 3], ['rem', 'a', 'x', 3]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 4], ['rem', 'b', 'x', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 8], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 5], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 7], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 6], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 7], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 3], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 4], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    4: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 4], ['rem', 'a', 'x', 4]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 5], ['rem', 'b', 'x', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 9], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 6], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 8], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 7], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 8], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 4], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 5], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    5: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 5], ['rem', 'a', 'x', 5]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 6], ['rem', 'b', 'x', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 6], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 10], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 7], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 9], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 8], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 9], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 5], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 6], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
}[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 added and removed at the same timestamp disappears, contrary to the add-wins tie rule.

Each replica keeps add and remove timestamp maps. ["add"|"rem", r, e, t] records t when it exceeds the stored timestamp. ["merge", s, d] folds both maps of s into d by maximum. An element is a member when it has an add timestamp that is greater than or equal to its remove timestamp (ties favour add). 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):
    A = {r: {} for r in replicas}
    R = {r: {} for r in replicas}
    for op in ops:
        if op[0] == 'merge':
            s, d = op[1], op[2]
            for src, dst in ((A[s], A[d]), (R[s], R[d])):
                for e, t in src.items():
                    dst[e] = t
        else:
            kind, r, e, t = op
            table = A[r] if kind == 'add' else R[r]
            if t > table.get(e, -1):
                table[e] = t
    def members(r):
        return sorted(e for e, t in A[r].items() if t >= R[r].get(e, -1))
    return [members(r) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 1], ['rem', 'a', 'x', 1]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 2], ['rem', 'b', 'x', 2], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 6], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 3], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 5], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 5], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 1], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 2], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    2: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 2], ['rem', 'a', 'x', 2]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 3], ['rem', 'b', 'x', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 7], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 4], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 6], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 6], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 2], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 3], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    3: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 3], ['rem', 'a', 'x', 3]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 4], ['rem', 'b', 'x', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 8], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 5], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 7], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 6], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 7], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 3], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 4], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    4: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 4], ['rem', 'a', 'x', 4]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 5], ['rem', 'b', 'x', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 9], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 6], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 8], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 7], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 8], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 4], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 5], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    5: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 5], ['rem', 'a', 'x', 5]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 6], ['rem', 'b', 'x', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 6], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 10], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 7], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 9], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 8], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 9], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 5], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 6], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
}[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):
    A = {r: {} for r in replicas}
    R = {r: {} for r in replicas}
    for op in ops:
        if op[0] == 'merge':
            s, d = op[1], op[2]
            for src, dst in ((A[s], A[d]), (R[s], R[d])):
                for e, t in src.items():
                    if e not in dst:
                        dst[e] = t
        else:
            kind, r, e, t = op
            table = A[r] if kind == 'add' else R[r]
            if t > table.get(e, -1):
                table[e] = t
    def members(r):
        return sorted(e for e, t in A[r].items() if t >= R[r].get(e, -1))
    return [members(r) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 1], ['rem', 'a', 'x', 1]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 2], ['rem', 'b', 'x', 2], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 6], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 3], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 5], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 5], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 1], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 2], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    2: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 2], ['rem', 'a', 'x', 2]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 3], ['rem', 'b', 'x', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 7], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 4], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 6], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 6], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 2], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 3], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    3: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 3], ['rem', 'a', 'x', 3]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 4], ['rem', 'b', 'x', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 8], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 5], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 7], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 6], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 7], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 3], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 4], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    4: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 4], ['rem', 'a', 'x', 4]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 5], ['rem', 'b', 'x', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 9], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 6], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 8], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 7], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 8], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 4], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 5], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    5: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 5], ['rem', 'a', 'x', 5]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 6], ['rem', 'b', 'x', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 6], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 10], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 7], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 9], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 8], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 9], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 5], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 6], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
}[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:
Merging an older replica state resurrects or hides elements depending on delivery order.

Each replica keeps add and remove timestamp maps. ["add"|"rem", r, e, t] records t when it exceeds the stored timestamp. ["merge", s, d] folds both maps of s into d by maximum. An element is a member when it has an add timestamp that is greater than or equal to its remove timestamp (ties favour add). 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):
    A = {r: {} for r in replicas}
    R = {r: {} for r in replicas}
    for op in ops:
        if op[0] == 'merge':
            s, d = op[1], op[2]
            for src, dst in ((A[s], A[d]),):
                for e, t in src.items():
                    if t > dst.get(e, -1):
                        dst[e] = t
        else:
            kind, r, e, t = op
            table = A[r] if kind == 'add' else R[r]
            if t > table.get(e, -1):
                table[e] = t
    def members(r):
        return sorted(e for e, t in A[r].items() if t >= R[r].get(e, -1))
    return [members(r) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 1], ['rem', 'a', 'x', 1]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 2], ['rem', 'b', 'x', 2], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 6], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 3], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 5], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 5], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 1], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 2], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    2: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 2], ['rem', 'a', 'x', 2]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 3], ['rem', 'b', 'x', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 7], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 4], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 6], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 6], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 2], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 3], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    3: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 3], ['rem', 'a', 'x', 3]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 4], ['rem', 'b', 'x', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 8], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 5], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 7], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 6], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 7], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 3], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 4], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    4: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 4], ['rem', 'a', 'x', 4]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 5], ['rem', 'b', 'x', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 9], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 6], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 8], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 7], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 8], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 4], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 5], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    5: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 5], ['rem', 'a', 'x', 5]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 6], ['rem', 'b', 'x', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 6], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 10], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 7], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 9], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 8], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 9], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 5], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 6], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
}[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):
    A = {r: {} for r in replicas}
    R = {r: {} for r in replicas}
    for op in ops:
        if op[0] == 'merge':
            s, d = op[1], op[2]
            for src, dst in ((A[s], A[d]), (R[d], R[s])):
                for e, t in src.items():
                    if t > dst.get(e, -1):
                        dst[e] = t
        else:
            kind, r, e, t = op
            table = A[r] if kind == 'add' else R[r]
            if t > table.get(e, -1):
                table[e] = t
    def members(r):
        return sorted(e for e, t in A[r].items() if t >= R[r].get(e, -1))
    return [members(r) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 1], ['rem', 'a', 'x', 1]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 2], ['rem', 'b', 'x', 2], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 6], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 3], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 5], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 5], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 1], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 2], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    2: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 2], ['rem', 'a', 'x', 2]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 3], ['rem', 'b', 'x', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 7], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 4], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 6], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 6], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 2], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 3], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    3: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 3], ['rem', 'a', 'x', 3]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 4], ['rem', 'b', 'x', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 8], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 5], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 7], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 6], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 7], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 3], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 4], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    4: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 4], ['rem', 'a', 'x', 4]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 5], ['rem', 'b', 'x', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 9], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 6], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 8], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 7], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 8], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 4], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 5], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    5: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 5], ['rem', 'a', 'x', 5]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 6], ['rem', 'b', 'x', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 6], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 10], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 7], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 9], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 8], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 9], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 5], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 6], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
}[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:
Removes never reach other replicas, which keep showing deleted elements.

Each replica keeps add and remove timestamp maps. ["add"|"rem", r, e, t] records t when it exceeds the stored timestamp. ["merge", s, d] folds both maps of s into d by maximum. An element is a member when it has an add timestamp that is greater than or equal to its remove timestamp (ties favour add). 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):
    A = {r: {} for r in replicas}
    R = {r: {} for r in replicas}
    for op in ops:
        if op[0] == 'merge':
            s, d = op[1], op[2]
            for src, dst in ((A[s], A[d]), (R[s], R[d])):
                for e, t in src.items():
                    if t > dst.get(e, -1):
                        dst[e] = t
        else:
            kind, r, e, t = op
            table = A[r] if kind == 'add' else R[r]
            table[e] = t
    def members(r):
        return sorted(e for e, t in A[r].items() if t >= R[r].get(e, -1))
    return [members(r) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 1], ['rem', 'a', 'x', 1]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 2], ['rem', 'b', 'x', 2], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 6], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 3], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 5], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 5], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 1], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 2], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    2: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 2], ['rem', 'a', 'x', 2]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 3], ['rem', 'b', 'x', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 7], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 4], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 6], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 6], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 2], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 3], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    3: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 3], ['rem', 'a', 'x', 3]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 4], ['rem', 'b', 'x', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 8], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 5], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 7], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 6], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 7], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 3], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 4], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    4: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 4], ['rem', 'a', 'x', 4]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 5], ['rem', 'b', 'x', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 9], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 6], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 8], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 7], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 8], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 4], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 5], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    5: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 5], ['rem', 'a', 'x', 5]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 6], ['rem', 'b', 'x', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 6], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 10], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 7], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 9], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 8], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 9], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 5], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 6], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
}[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):
    A = {r: {} for r in replicas}
    R = {r: {} for r in replicas}
    for op in ops:
        if op[0] == 'merge':
            s, d = op[1], op[2]
            for src, dst in ((A[s], A[d]), (R[s], R[d])):
                for e, t in src.items():
                    if t > dst.get(e, -1):
                        dst[e] = t
        else:
            kind, r, e, t = op
            table = A[r] if kind == 'add' else R[r]
            if e not in table:
                table[e] = t
    def members(r):
        return sorted(e for e, t in A[r].items() if t >= R[r].get(e, -1))
    return [members(r) for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 1], ['rem', 'a', 'x', 1]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 2], ['rem', 'b', 'x', 2], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 6], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 3], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 5], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 5], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 1], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 2], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    2: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 2], ['rem', 'a', 'x', 2]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 3], ['rem', 'b', 'x', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 7], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 4], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 6], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 6], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 2], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 3], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    3: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 3], ['rem', 'a', 'x', 3]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 4], ['rem', 'b', 'x', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 8], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 5], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 7], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 6], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 7], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 3], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 4], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    4: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 4], ['rem', 'a', 'x', 4]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 5], ['rem', 'b', 'x', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 9], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 6], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 8], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 7], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 8], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 4], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 5], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
    5: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 5], ['rem', 'a', 'x', 5]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 6], ['rem', 'b', 'x', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 6], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 10], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 7], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 9], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 8], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 9], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 5], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 6], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
}[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 old add delivered late makes a newer element lose to an intermediate remove.

Each replica keeps add and remove timestamp maps. ["add"|"rem", r, e, t] records t when it exceeds the stored timestamp. ["merge", s, d] folds both maps of s into d by maximum. An element is a member when it has an add timestamp that is greater than or equal to its remove timestamp (ties favour add). Return sorted members per replica.

split: open-access