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

N = 1
observations = []
def solve(events, replicas):
    pos = {r: {} for r in replicas}
    neg = {r: {} for r in replicas}
    rejected = []
    def value(r):
        return sum(pos[r].values()) - sum(neg[r].values())
    for i, ev in enumerate(events):
        kind = ev[0]
        if kind == 'sync':
            s, d = ev[1], ev[2]
            for k, v in pos[s].items():
                pos[d][k] = max(pos[d].get(k, 0), v)
            for k, v in neg[d].items():
                neg[s][k] = max(neg[s].get(k, 0), v)
            continue
        r, amt = ev[1], ev[2]
        if amt <= 0:
            rejected.append(i)
            continue
        if kind == 'inc':
            pos[r][r] = pos[r].get(r, 0) + amt
        else:
            if value(r) < amt:
                rejected.append(i)
                continue
            neg[r][r] = neg[r].get(r, 0) + amt
    return {'values': [value(r) for r in replicas], 'rejected': rejected}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('decrement to exactly zero is allowed', [[['inc', 'a', 1], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rejected': []}), ('decrement beyond local view is rejected', [[['inc', 'a', 1], ['dec', 'b', 1], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [1, 0, 0], 'rejected': [1, 2]}), ('decrement funded by learned increments', [[['inc', 'a', 3], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a'], ['sync', 'b', 'c'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [1, 1, 1], 'rejected': []}), ('concurrent decrements converge', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['dec', 'a', 1], ['dec', 'b', 2], ['sync', 'a', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [1, 1, 1], 'rejected': []}), ('zero amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', 3], ['dec', 'b', 0], ['dec', 'b', 1]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rejected': [0, 2]}), ('repeated decrement slot is refreshed', [[['inc', 'c', 4], ['dec', 'c', 1], ['sync', 'c', 'a'], ['dec', 'c', 1], ['sync', 'c', 'a'], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [2, 2, 2], 'rejected': []}), ('second decrement cannot pass the floor', [[['inc', 'a', 2], ['dec', 'a', 1], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [1, 0, 0], 'rejected': [2]}), ('one-way sync does not pull from the receiver', [[['inc', 'a', 1], ['inc', 'b', 1], ['dec', 'b', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [1, 1, 0], 'rejected': []}), ('mixed history', [[['inc', 'a', 3], ['dec', 'a', 1], ['sync', 'a', 'b'], ['inc', 'b', 1], ['dec', 'b', 2], ['sync', 'b', 'a'], ['sync', 'a', 'c'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [1, 1, 1], 'rejected': []})],
    2: [('decrement to exactly zero is allowed', [[['inc', 'a', 2], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rejected': []}), ('decrement beyond local view is rejected', [[['inc', 'a', 2], ['dec', 'b', 1], ['dec', 'a', 3]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rejected': [1, 2]}), ('decrement funded by learned increments', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['dec', 'b', 3], ['sync', 'b', 'a'], ['sync', 'b', 'c'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [1, 1, 1], 'rejected': []}), ('concurrent decrements converge', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'a', 1], ['dec', 'b', 2], ['sync', 'a', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [3, 3, 3], 'rejected': []}), ('zero amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', 3], ['dec', 'b', 0], ['dec', 'b', 1]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rejected': [0, 2]}), ('repeated decrement slot is refreshed', [[['inc', 'c', 5], ['dec', 'c', 1], ['sync', 'c', 'a'], ['dec', 'c', 1], ['sync', 'c', 'a'], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [3, 3, 3], 'rejected': []}), ('second decrement cannot pass the floor', [[['inc', 'a', 3], ['dec', 'a', 2], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [1, 0, 0], 'rejected': [2]}), ('one-way sync does not pull from the receiver', [[['inc', 'a', 2], ['inc', 'b', 2], ['dec', 'b', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [2, 3, 0], 'rejected': []}), ('mixed history', [[['inc', 'a', 3], ['dec', 'a', 1], ['sync', 'a', 'b'], ['inc', 'b', 2], ['dec', 'b', 2], ['sync', 'b', 'a'], ['sync', 'a', 'c'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [2, 2, 2], 'rejected': []})],
    3: [('decrement to exactly zero is allowed', [[['inc', 'a', 3], ['dec', 'a', 3]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rejected': []}), ('decrement beyond local view is rejected', [[['inc', 'a', 3], ['dec', 'b', 1], ['dec', 'a', 4]], ['a', 'b', 'c']], {'values': [3, 0, 0], 'rejected': [1, 2]}), ('decrement funded by learned increments', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'b', 4], ['sync', 'b', 'a'], ['sync', 'b', 'c'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [1, 1, 1], 'rejected': []}), ('concurrent decrements converge', [[['inc', 'a', 8], ['sync', 'a', 'b'], ['dec', 'a', 1], ['dec', 'b', 2], ['sync', 'a', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [5, 5, 5], 'rejected': []}), ('zero amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', 3], ['dec', 'b', 0], ['dec', 'b', 1]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rejected': [0, 2]}), ('repeated decrement slot is refreshed', [[['inc', 'c', 6], ['dec', 'c', 1], ['sync', 'c', 'a'], ['dec', 'c', 1], ['sync', 'c', 'a'], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [4, 4, 4], 'rejected': []}), ('second decrement cannot pass the floor', [[['inc', 'a', 4], ['dec', 'a', 3], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [1, 0, 0], 'rejected': [2]}), ('one-way sync does not pull from the receiver', [[['inc', 'a', 3], ['inc', 'b', 3], ['dec', 'b', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [3, 5, 0], 'rejected': []}), ('mixed history', [[['inc', 'a', 3], ['dec', 'a', 1], ['sync', 'a', 'b'], ['inc', 'b', 3], ['dec', 'b', 2], ['sync', 'b', 'a'], ['sync', 'a', 'c'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [3, 3, 3], 'rejected': []})],
    4: [('decrement to exactly zero is allowed', [[['inc', 'a', 4], ['dec', 'a', 4]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rejected': []}), ('decrement beyond local view is rejected', [[['inc', 'a', 4], ['dec', 'b', 1], ['dec', 'a', 5]], ['a', 'b', 'c']], {'values': [4, 0, 0], 'rejected': [1, 2]}), ('decrement funded by learned increments', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'b', 5], ['sync', 'b', 'a'], ['sync', 'b', 'c'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [1, 1, 1], 'rejected': []}), ('concurrent decrements converge', [[['inc', 'a', 10], ['sync', 'a', 'b'], ['dec', 'a', 1], ['dec', 'b', 2], ['sync', 'a', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [7, 7, 7], 'rejected': []}), ('zero amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', 3], ['dec', 'b', 0], ['dec', 'b', 1]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rejected': [0, 2]}), ('repeated decrement slot is refreshed', [[['inc', 'c', 7], ['dec', 'c', 1], ['sync', 'c', 'a'], ['dec', 'c', 1], ['sync', 'c', 'a'], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [5, 5, 5], 'rejected': []}), ('second decrement cannot pass the floor', [[['inc', 'a', 5], ['dec', 'a', 4], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [1, 0, 0], 'rejected': [2]}), ('one-way sync does not pull from the receiver', [[['inc', 'a', 4], ['inc', 'b', 4], ['dec', 'b', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [4, 7, 0], 'rejected': []}), ('mixed history', [[['inc', 'a', 3], ['dec', 'a', 1], ['sync', 'a', 'b'], ['inc', 'b', 4], ['dec', 'b', 2], ['sync', 'b', 'a'], ['sync', 'a', 'c'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [4, 4, 4], 'rejected': []})],
    5: [('decrement to exactly zero is allowed', [[['inc', 'a', 5], ['dec', 'a', 5]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rejected': []}), ('decrement beyond local view is rejected', [[['inc', 'a', 5], ['dec', 'b', 1], ['dec', 'a', 6]], ['a', 'b', 'c']], {'values': [5, 0, 0], 'rejected': [1, 2]}), ('decrement funded by learned increments', [[['inc', 'a', 7], ['sync', 'a', 'b'], ['dec', 'b', 6], ['sync', 'b', 'a'], ['sync', 'b', 'c'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [1, 1, 1], 'rejected': []}), ('concurrent decrements converge', [[['inc', 'a', 12], ['sync', 'a', 'b'], ['dec', 'a', 1], ['dec', 'b', 2], ['sync', 'a', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [9, 9, 9], 'rejected': []}), ('zero amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', 3], ['dec', 'b', 0], ['dec', 'b', 1]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rejected': [0, 2]}), ('repeated decrement slot is refreshed', [[['inc', 'c', 8], ['dec', 'c', 1], ['sync', 'c', 'a'], ['dec', 'c', 1], ['sync', 'c', 'a'], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [6, 6, 6], 'rejected': []}), ('second decrement cannot pass the floor', [[['inc', 'a', 6], ['dec', 'a', 5], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [1, 0, 0], 'rejected': [2]}), ('one-way sync does not pull from the receiver', [[['inc', 'a', 5], ['inc', 'b', 5], ['dec', 'b', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [5, 9, 0], 'rejected': []}), ('mixed history', [[['inc', 'a', 3], ['dec', 'a', 1], ['sync', 'a', 'b'], ['inc', 'b', 5], ['dec', 'b', 2], ['sync', 'b', 'a'], ['sync', 'a', 'c'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [5, 5, 5], 'rejected': []})],
}[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):
    pos = {r: {} for r in replicas}
    neg = {r: {} for r in replicas}
    rejected = []
    def value(r):
        return sum(pos[r].values()) - sum(neg[r].values())
    for i, ev in enumerate(events):
        kind = ev[0]
        if kind == 'sync':
            s, d = ev[1], ev[2]
            for k, v in pos[s].items():
                pos[d][k] = max(pos[d].get(k, 0), v)
            for k, v in neg[s].items():
                neg[d][k] = max(neg[d].get(k, 0), v)
            for k, v in neg[d].items():
                neg[s][k] = max(neg[s].get(k, 0), v)
            continue
        r, amt = ev[1], ev[2]
        if amt <= 0:
            rejected.append(i)
            continue
        if kind == 'inc':
            pos[r][r] = pos[r].get(r, 0) + amt
        else:
            if value(r) < amt:
                rejected.append(i)
                continue
            neg[r][r] = neg[r].get(r, 0) + amt
    return {'values': [value(r) for r in replicas], 'rejected': rejected}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('decrement to exactly zero is allowed', [[['inc', 'a', 1], ['dec', 'a', 1]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rejected': []}), ('decrement beyond local view is rejected', [[['inc', 'a', 1], ['dec', 'b', 1], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [1, 0, 0], 'rejected': [1, 2]}), ('decrement funded by learned increments', [[['inc', 'a', 3], ['sync', 'a', 'b'], ['dec', 'b', 2], ['sync', 'b', 'a'], ['sync', 'b', 'c'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [1, 1, 1], 'rejected': []}), ('concurrent decrements converge', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['dec', 'a', 1], ['dec', 'b', 2], ['sync', 'a', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [1, 1, 1], 'rejected': []}), ('zero amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', 3], ['dec', 'b', 0], ['dec', 'b', 1]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rejected': [0, 2]}), ('repeated decrement slot is refreshed', [[['inc', 'c', 4], ['dec', 'c', 1], ['sync', 'c', 'a'], ['dec', 'c', 1], ['sync', 'c', 'a'], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [2, 2, 2], 'rejected': []}), ('second decrement cannot pass the floor', [[['inc', 'a', 2], ['dec', 'a', 1], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [1, 0, 0], 'rejected': [2]}), ('one-way sync does not pull from the receiver', [[['inc', 'a', 1], ['inc', 'b', 1], ['dec', 'b', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [1, 1, 0], 'rejected': []}), ('mixed history', [[['inc', 'a', 3], ['dec', 'a', 1], ['sync', 'a', 'b'], ['inc', 'b', 1], ['dec', 'b', 2], ['sync', 'b', 'a'], ['sync', 'a', 'c'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [1, 1, 1], 'rejected': []})],
    2: [('decrement to exactly zero is allowed', [[['inc', 'a', 2], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rejected': []}), ('decrement beyond local view is rejected', [[['inc', 'a', 2], ['dec', 'b', 1], ['dec', 'a', 3]], ['a', 'b', 'c']], {'values': [2, 0, 0], 'rejected': [1, 2]}), ('decrement funded by learned increments', [[['inc', 'a', 4], ['sync', 'a', 'b'], ['dec', 'b', 3], ['sync', 'b', 'a'], ['sync', 'b', 'c'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [1, 1, 1], 'rejected': []}), ('concurrent decrements converge', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'a', 1], ['dec', 'b', 2], ['sync', 'a', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [3, 3, 3], 'rejected': []}), ('zero amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', 3], ['dec', 'b', 0], ['dec', 'b', 1]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rejected': [0, 2]}), ('repeated decrement slot is refreshed', [[['inc', 'c', 5], ['dec', 'c', 1], ['sync', 'c', 'a'], ['dec', 'c', 1], ['sync', 'c', 'a'], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [3, 3, 3], 'rejected': []}), ('second decrement cannot pass the floor', [[['inc', 'a', 3], ['dec', 'a', 2], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [1, 0, 0], 'rejected': [2]}), ('one-way sync does not pull from the receiver', [[['inc', 'a', 2], ['inc', 'b', 2], ['dec', 'b', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [2, 3, 0], 'rejected': []}), ('mixed history', [[['inc', 'a', 3], ['dec', 'a', 1], ['sync', 'a', 'b'], ['inc', 'b', 2], ['dec', 'b', 2], ['sync', 'b', 'a'], ['sync', 'a', 'c'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [2, 2, 2], 'rejected': []})],
    3: [('decrement to exactly zero is allowed', [[['inc', 'a', 3], ['dec', 'a', 3]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rejected': []}), ('decrement beyond local view is rejected', [[['inc', 'a', 3], ['dec', 'b', 1], ['dec', 'a', 4]], ['a', 'b', 'c']], {'values': [3, 0, 0], 'rejected': [1, 2]}), ('decrement funded by learned increments', [[['inc', 'a', 5], ['sync', 'a', 'b'], ['dec', 'b', 4], ['sync', 'b', 'a'], ['sync', 'b', 'c'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [1, 1, 1], 'rejected': []}), ('concurrent decrements converge', [[['inc', 'a', 8], ['sync', 'a', 'b'], ['dec', 'a', 1], ['dec', 'b', 2], ['sync', 'a', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [5, 5, 5], 'rejected': []}), ('zero amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', 3], ['dec', 'b', 0], ['dec', 'b', 1]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rejected': [0, 2]}), ('repeated decrement slot is refreshed', [[['inc', 'c', 6], ['dec', 'c', 1], ['sync', 'c', 'a'], ['dec', 'c', 1], ['sync', 'c', 'a'], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [4, 4, 4], 'rejected': []}), ('second decrement cannot pass the floor', [[['inc', 'a', 4], ['dec', 'a', 3], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [1, 0, 0], 'rejected': [2]}), ('one-way sync does not pull from the receiver', [[['inc', 'a', 3], ['inc', 'b', 3], ['dec', 'b', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [3, 5, 0], 'rejected': []}), ('mixed history', [[['inc', 'a', 3], ['dec', 'a', 1], ['sync', 'a', 'b'], ['inc', 'b', 3], ['dec', 'b', 2], ['sync', 'b', 'a'], ['sync', 'a', 'c'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [3, 3, 3], 'rejected': []})],
    4: [('decrement to exactly zero is allowed', [[['inc', 'a', 4], ['dec', 'a', 4]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rejected': []}), ('decrement beyond local view is rejected', [[['inc', 'a', 4], ['dec', 'b', 1], ['dec', 'a', 5]], ['a', 'b', 'c']], {'values': [4, 0, 0], 'rejected': [1, 2]}), ('decrement funded by learned increments', [[['inc', 'a', 6], ['sync', 'a', 'b'], ['dec', 'b', 5], ['sync', 'b', 'a'], ['sync', 'b', 'c'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [1, 1, 1], 'rejected': []}), ('concurrent decrements converge', [[['inc', 'a', 10], ['sync', 'a', 'b'], ['dec', 'a', 1], ['dec', 'b', 2], ['sync', 'a', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [7, 7, 7], 'rejected': []}), ('zero amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', 3], ['dec', 'b', 0], ['dec', 'b', 1]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rejected': [0, 2]}), ('repeated decrement slot is refreshed', [[['inc', 'c', 7], ['dec', 'c', 1], ['sync', 'c', 'a'], ['dec', 'c', 1], ['sync', 'c', 'a'], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [5, 5, 5], 'rejected': []}), ('second decrement cannot pass the floor', [[['inc', 'a', 5], ['dec', 'a', 4], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [1, 0, 0], 'rejected': [2]}), ('one-way sync does not pull from the receiver', [[['inc', 'a', 4], ['inc', 'b', 4], ['dec', 'b', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [4, 7, 0], 'rejected': []}), ('mixed history', [[['inc', 'a', 3], ['dec', 'a', 1], ['sync', 'a', 'b'], ['inc', 'b', 4], ['dec', 'b', 2], ['sync', 'b', 'a'], ['sync', 'a', 'c'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [4, 4, 4], 'rejected': []})],
    5: [('decrement to exactly zero is allowed', [[['inc', 'a', 5], ['dec', 'a', 5]], ['a', 'b', 'c']], {'values': [0, 0, 0], 'rejected': []}), ('decrement beyond local view is rejected', [[['inc', 'a', 5], ['dec', 'b', 1], ['dec', 'a', 6]], ['a', 'b', 'c']], {'values': [5, 0, 0], 'rejected': [1, 2]}), ('decrement funded by learned increments', [[['inc', 'a', 7], ['sync', 'a', 'b'], ['dec', 'b', 6], ['sync', 'b', 'a'], ['sync', 'b', 'c'], ['sync', 'a', 'c']], ['a', 'b', 'c']], {'values': [1, 1, 1], 'rejected': []}), ('concurrent decrements converge', [[['inc', 'a', 12], ['sync', 'a', 'b'], ['dec', 'a', 1], ['dec', 'b', 2], ['sync', 'a', 'b'], ['sync', 'b', 'a'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [9, 9, 9], 'rejected': []}), ('zero amounts are rejected', [[['inc', 'a', 0], ['inc', 'b', 3], ['dec', 'b', 0], ['dec', 'b', 1]], ['a', 'b', 'c']], {'values': [0, 2, 0], 'rejected': [0, 2]}), ('repeated decrement slot is refreshed', [[['inc', 'c', 8], ['dec', 'c', 1], ['sync', 'c', 'a'], ['dec', 'c', 1], ['sync', 'c', 'a'], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [6, 6, 6], 'rejected': []}), ('second decrement cannot pass the floor', [[['inc', 'a', 6], ['dec', 'a', 5], ['dec', 'a', 2]], ['a', 'b', 'c']], {'values': [1, 0, 0], 'rejected': [2]}), ('one-way sync does not pull from the receiver', [[['inc', 'a', 5], ['inc', 'b', 5], ['dec', 'b', 1], ['sync', 'a', 'b']], ['a', 'b', 'c']], {'values': [5, 9, 0], 'rejected': []}), ('mixed history', [[['inc', 'a', 3], ['dec', 'a', 1], ['sync', 'a', 'b'], ['inc', 'b', 5], ['dec', 'b', 2], ['sync', 'b', 'a'], ['sync', 'a', 'c'], ['sync', 'b', 'c']], ['a', 'b', 'c']], {'values': [5, 5, 5], 'rejected': []})],
}[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:
Receivers do not see the sender's decrements while the sender absorbs the receiver's.

Replicas keep a positive map and a negative map (replica->total). ["inc", r, k] and ["dec", r, k] need k > 0, otherwise the event index is rejected. A decrement is also rejected when r's locally observed value is below k. ["sync", src, dst] merges both maps of src into dst by pointwise maximum. Return values and rejected indices.

split: open-access


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]
            if (inc[1], inc[2]) > (reg[d][1], reg[d][2]):
                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)

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(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] = inc[1]
            if (inc[1], inc[2]) > (reg[d][1], reg[d][2]):
                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 write made after receiving a newer value loses to that older value on other replicas.

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(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] > 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] >= 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)

prompt:
Two concurrent writes with the same clock leave replicas permanently disagreeing.

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(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], reg[d][2]):
                reg[d] = [inc[0], clock[d], d]
    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], reg[d][2]):
                reg[d] = [inc[0], inc[1], d]
    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:
After relaying a value, a replica makes it win or lose ties it should not.

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