FA-75256 / CRDT convergence / Open access

Causal length set: adding a present element toggles it off · case 01

A duplicate add removes the element.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

Add increments the causal length unconditionally, flipping parity when the element is already present.

THE FAILURE

Add increments the causal length unconditionally, flipping parity when the element is already present.

Unsuccessful approach: Allowing only the very first add ignores later re-adds after a remove.

Case contract

Each replica maps elements to a causal length. An element is present when its length is odd. ["add", r, e] increments the length only when it is even; ["rem", r, e] increments it only when it is odd. ["merge", s, d] takes the per-element maximum. Return per replica the sorted members and the sorted [element, length] pairs.

Why this case matters

Causal-length sets encode an element's add/remove history as a single counter whose parity is its membership.

1 / The failure

Exit 1

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

N = 1
observations = []
def solve(ops, replicas):
    L = {r: {} for r in replicas}
    for op in ops:
        if op[0] == 'add':
            r, e = op[1], op[2]
            L[r][e] = L[r].get(e, 0) + 1
        elif op[0] == 'rem':
            r, e = op[1], op[2]
            if L[r].get(e, 0) % 2 == 1:
                L[r][e] = L[r][e] + 1
        else:
            s, d = op[1], op[2]
            for e, ln in L[s].items():
                L[d][e] = max(L[d].get(e, 0), ln)
    return [[sorted(e for e, ln in L[r].items() if ln % 2 == 1), sorted([e, ln] for e, ln in L[r].items())] for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('add then remove', [[['add', 'a', 'x'], ['rem', 'a', 'x']], ['a', 'b']], [[[], [['x', 2]]], [[], []]]), ('re-add after remove', [[['add', 'a', 'x'], ['rem', 'a', 'x'], ['add', 'a', 'x']], ['a', 'b']], [[['x'], [['x', 3]]], [[], []]]), ('adding a present element is a no-op', [[['add', 'a', 'y'], ['add', 'a', 'y']], ['a', 'b']], [[['y'], [['y', 1]]], [[], []]]), ('removing an absent element is a no-op', [[['rem', 'a', 'z'], ['rem', 'b', 'z'], ['add', 'b', 'w'], ['rem', 'b', 'w'], ['rem', 'b', 'w']], ['a', 'b']], [[[], []], [[], [['w', 2]]]]), ('concurrent adds merge to present', [[['add', 'a', 'k'], ['add', 'b', 'k'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['k'], [['k', 1]]], [['k'], [['k', 1]]]]), ('removal propagates by merge', [[['add', 'a', 'r'], ['merge', 'a', 'b'], ['rem', 'b', 'r'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['r', 2]]], [[], [['r', 2]]]]), ('longer history wins', [[['add', 'a', 'h'], ['merge', 'a', 'b'], ['rem', 'a', 'h'], ['add', 'a', 'h'], ['rem', 'a', 'h'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['h', 4]]], [[], [['h', 4]]]]), ('stale present copy does not revive', [[['add', 'a', 'q'], ['merge', 'a', 'b'], ['rem', 'a', 'q'], ['merge', 'b', 'a'], ['add', 'b', 'e0']], ['a', 'b']], [[[], [['q', 2]]], [['e0', 'q'], [['e0', 1], ['q', 1]]]])],
    2: [('add then remove', [[['add', 'a', 'x'], ['rem', 'a', 'x']], ['a', 'b']], [[[], [['x', 2]]], [[], []]]), ('re-add after remove', [[['add', 'a', 'x'], ['rem', 'a', 'x'], ['add', 'a', 'x']], ['a', 'b']], [[['x'], [['x', 3]]], [[], []]]), ('adding a present element is a no-op', [[['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y']], ['a', 'b']], [[['y'], [['y', 1]]], [[], []]]), ('removing an absent element is a no-op', [[['rem', 'a', 'z'], ['rem', 'b', 'z'], ['add', 'b', 'w'], ['rem', 'b', 'w'], ['rem', 'b', 'w']], ['a', 'b']], [[[], []], [[], [['w', 2]]]]), ('concurrent adds merge to present', [[['add', 'a', 'k'], ['add', 'b', 'k'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['k'], [['k', 1]]], [['k'], [['k', 1]]]]), ('removal propagates by merge', [[['add', 'a', 'r'], ['merge', 'a', 'b'], ['rem', 'b', 'r'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['r', 2]]], [[], [['r', 2]]]]), ('longer history wins', [[['add', 'a', 'h'], ['merge', 'a', 'b'], ['rem', 'a', 'h'], ['add', 'a', 'h'], ['rem', 'a', 'h'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['h', 4]]], [[], [['h', 4]]]]), ('stale present copy does not revive', [[['add', 'a', 'q'], ['merge', 'a', 'b'], ['rem', 'a', 'q'], ['merge', 'b', 'a'], ['add', 'b', 'e0'], ['add', 'b', 'e1']], ['a', 'b']], [[[], [['q', 2]]], [['e0', 'e1', 'q'], [['e0', 1], ['e1', 1], ['q', 1]]]])],
    3: [('add then remove', [[['add', 'a', 'x'], ['rem', 'a', 'x']], ['a', 'b']], [[[], [['x', 2]]], [[], []]]), ('re-add after remove', [[['add', 'a', 'x'], ['rem', 'a', 'x'], ['add', 'a', 'x']], ['a', 'b']], [[['x'], [['x', 3]]], [[], []]]), ('adding a present element is a no-op', [[['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y']], ['a', 'b']], [[['y'], [['y', 1]]], [[], []]]), ('removing an absent element is a no-op', [[['rem', 'a', 'z'], ['rem', 'b', 'z'], ['add', 'b', 'w'], ['rem', 'b', 'w'], ['rem', 'b', 'w']], ['a', 'b']], [[[], []], [[], [['w', 2]]]]), ('concurrent adds merge to present', [[['add', 'a', 'k'], ['add', 'b', 'k'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['k'], [['k', 1]]], [['k'], [['k', 1]]]]), ('removal propagates by merge', [[['add', 'a', 'r'], ['merge', 'a', 'b'], ['rem', 'b', 'r'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['r', 2]]], [[], [['r', 2]]]]), ('longer history wins', [[['add', 'a', 'h'], ['merge', 'a', 'b'], ['rem', 'a', 'h'], ['add', 'a', 'h'], ['rem', 'a', 'h'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['h', 4]]], [[], [['h', 4]]]]), ('stale present copy does not revive', [[['add', 'a', 'q'], ['merge', 'a', 'b'], ['rem', 'a', 'q'], ['merge', 'b', 'a'], ['add', 'b', 'e0'], ['add', 'b', 'e1'], ['add', 'b', 'e2']], ['a', 'b']], [[[], [['q', 2]]], [['e0', 'e1', 'e2', 'q'], [['e0', 1], ['e1', 1], ['e2', 1], ['q', 1]]]])],
    4: [('add then remove', [[['add', 'a', 'x'], ['rem', 'a', 'x']], ['a', 'b']], [[[], [['x', 2]]], [[], []]]), ('re-add after remove', [[['add', 'a', 'x'], ['rem', 'a', 'x'], ['add', 'a', 'x']], ['a', 'b']], [[['x'], [['x', 3]]], [[], []]]), ('adding a present element is a no-op', [[['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y']], ['a', 'b']], [[['y'], [['y', 1]]], [[], []]]), ('removing an absent element is a no-op', [[['rem', 'a', 'z'], ['rem', 'b', 'z'], ['add', 'b', 'w'], ['rem', 'b', 'w'], ['rem', 'b', 'w']], ['a', 'b']], [[[], []], [[], [['w', 2]]]]), ('concurrent adds merge to present', [[['add', 'a', 'k'], ['add', 'b', 'k'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['k'], [['k', 1]]], [['k'], [['k', 1]]]]), ('removal propagates by merge', [[['add', 'a', 'r'], ['merge', 'a', 'b'], ['rem', 'b', 'r'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['r', 2]]], [[], [['r', 2]]]]), ('longer history wins', [[['add', 'a', 'h'], ['merge', 'a', 'b'], ['rem', 'a', 'h'], ['add', 'a', 'h'], ['rem', 'a', 'h'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['h', 4]]], [[], [['h', 4]]]]), ('stale present copy does not revive', [[['add', 'a', 'q'], ['merge', 'a', 'b'], ['rem', 'a', 'q'], ['merge', 'b', 'a'], ['add', 'b', 'e0'], ['add', 'b', 'e1'], ['add', 'b', 'e2'], ['add', 'b', 'e3']], ['a', 'b']], [[[], [['q', 2]]], [['e0', 'e1', 'e2', 'e3', 'q'], [['e0', 1], ['e1', 1], ['e2', 1], ['e3', 1], ['q', 1]]]])],
    5: [('add then remove', [[['add', 'a', 'x'], ['rem', 'a', 'x']], ['a', 'b']], [[[], [['x', 2]]], [[], []]]), ('re-add after remove', [[['add', 'a', 'x'], ['rem', 'a', 'x'], ['add', 'a', 'x']], ['a', 'b']], [[['x'], [['x', 3]]], [[], []]]), ('adding a present element is a no-op', [[['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y']], ['a', 'b']], [[['y'], [['y', 1]]], [[], []]]), ('removing an absent element is a no-op', [[['rem', 'a', 'z'], ['rem', 'b', 'z'], ['add', 'b', 'w'], ['rem', 'b', 'w'], ['rem', 'b', 'w']], ['a', 'b']], [[[], []], [[], [['w', 2]]]]), ('concurrent adds merge to present', [[['add', 'a', 'k'], ['add', 'b', 'k'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['k'], [['k', 1]]], [['k'], [['k', 1]]]]), ('removal propagates by merge', [[['add', 'a', 'r'], ['merge', 'a', 'b'], ['rem', 'b', 'r'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['r', 2]]], [[], [['r', 2]]]]), ('longer history wins', [[['add', 'a', 'h'], ['merge', 'a', 'b'], ['rem', 'a', 'h'], ['add', 'a', 'h'], ['rem', 'a', 'h'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['h', 4]]], [[], [['h', 4]]]]), ('stale present copy does not revive', [[['add', 'a', 'q'], ['merge', 'a', 'b'], ['rem', 'a', 'q'], ['merge', 'b', 'a'], ['add', 'b', 'e0'], ['add', 'b', 'e1'], ['add', 'b', 'e2'], ['add', 'b', 'e3'], ['add', 'b', 'e4']], ['a', 'b']], [[[], [['q', 2]]], [['e0', 'e1', 'e2', 'e3', 'e4', 'q'], [['e0', 1], ['e1', 1], ['e2', 1], ['e3', 1], ['e4', 1], ['q', 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)

Boundary fixture	Actual	Expected	Outcome
add then remove	`[[[], [['x', 2]]], [[], []]]`	`[[[], [['x', 2]]], [[], []]]`	Passed
re-add after remove	`[[['x'], [['x', 3]]], [[], []]]`	`[[['x'], [['x', 3]]], [[], []]]`	Passed
adding a present element is a no-op	`[[[], [['y', 2]]], [[], []]]`	`[[['y'], [['y', 1]]], [[], []]]`	Failed
removing an absent element is a no-op	`[[[], []], [[], [['w', 2]]]]`	`[[[], []], [[], [['w', 2]]]]`	Passed
concurrent adds merge to present	`[[['k'], [['k', 1]]], [['k'], [['k', 1]]]]`	`[[['k'], [['k', 1]]], [['k'], [['k', 1]]]]`	Passed
removal propagates by merge	`[[[], [['r', 2]]], [[], [['r', 2]]]]`	`[[[], [['r', 2]]], [[], [['r', 2]]]]`	Passed
longer history wins	`[[[], [['h', 4]]], [[], [['h', 4]]]]`	`[[[], [['h', 4]]], [[], [['h', 4]]]]`	Passed
stale present copy does not revive	`[[[], [['q', 2]]], [['e0', 'q'], [['e0', 1], ['q', 1]]]]`	`[[[], [['q', 2]]], [['e0', 'q'], [['e0', 1], ['q', 1]]]]`	Passed

SHA-256 / d5750f6e44f90024d3e23d5b947247870748e7132c7fc2002c4276ee749d5bf6

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(ops, replicas):
    L = {r: {} for r in replicas}
    for op in ops:
        if op[0] == 'add':
            r, e = op[1], op[2]
            if L[r].get(e, 0) == 0:
                L[r][e] = L[r].get(e, 0) + 1
        elif op[0] == 'rem':
            r, e = op[1], op[2]
            if L[r].get(e, 0) % 2 == 1:
                L[r][e] = L[r][e] + 1
        else:
            s, d = op[1], op[2]
            for e, ln in L[s].items():
                L[d][e] = max(L[d].get(e, 0), ln)
    return [[sorted(e for e, ln in L[r].items() if ln % 2 == 1), sorted([e, ln] for e, ln in L[r].items())] for r in replicas]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('add then remove', [[['add', 'a', 'x'], ['rem', 'a', 'x']], ['a', 'b']], [[[], [['x', 2]]], [[], []]]), ('re-add after remove', [[['add', 'a', 'x'], ['rem', 'a', 'x'], ['add', 'a', 'x']], ['a', 'b']], [[['x'], [['x', 3]]], [[], []]]), ('adding a present element is a no-op', [[['add', 'a', 'y'], ['add', 'a', 'y']], ['a', 'b']], [[['y'], [['y', 1]]], [[], []]]), ('removing an absent element is a no-op', [[['rem', 'a', 'z'], ['rem', 'b', 'z'], ['add', 'b', 'w'], ['rem', 'b', 'w'], ['rem', 'b', 'w']], ['a', 'b']], [[[], []], [[], [['w', 2]]]]), ('concurrent adds merge to present', [[['add', 'a', 'k'], ['add', 'b', 'k'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['k'], [['k', 1]]], [['k'], [['k', 1]]]]), ('removal propagates by merge', [[['add', 'a', 'r'], ['merge', 'a', 'b'], ['rem', 'b', 'r'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['r', 2]]], [[], [['r', 2]]]]), ('longer history wins', [[['add', 'a', 'h'], ['merge', 'a', 'b'], ['rem', 'a', 'h'], ['add', 'a', 'h'], ['rem', 'a', 'h'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['h', 4]]], [[], [['h', 4]]]]), ('stale present copy does not revive', [[['add', 'a', 'q'], ['merge', 'a', 'b'], ['rem', 'a', 'q'], ['merge', 'b', 'a'], ['add', 'b', 'e0']], ['a', 'b']], [[[], [['q', 2]]], [['e0', 'q'], [['e0', 1], ['q', 1]]]])],
    2: [('add then remove', [[['add', 'a', 'x'], ['rem', 'a', 'x']], ['a', 'b']], [[[], [['x', 2]]], [[], []]]), ('re-add after remove', [[['add', 'a', 'x'], ['rem', 'a', 'x'], ['add', 'a', 'x']], ['a', 'b']], [[['x'], [['x', 3]]], [[], []]]), ('adding a present element is a no-op', [[['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y']], ['a', 'b']], [[['y'], [['y', 1]]], [[], []]]), ('removing an absent element is a no-op', [[['rem', 'a', 'z'], ['rem', 'b', 'z'], ['add', 'b', 'w'], ['rem', 'b', 'w'], ['rem', 'b', 'w']], ['a', 'b']], [[[], []], [[], [['w', 2]]]]), ('concurrent adds merge to present', [[['add', 'a', 'k'], ['add', 'b', 'k'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['k'], [['k', 1]]], [['k'], [['k', 1]]]]), ('removal propagates by merge', [[['add', 'a', 'r'], ['merge', 'a', 'b'], ['rem', 'b', 'r'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['r', 2]]], [[], [['r', 2]]]]), ('longer history wins', [[['add', 'a', 'h'], ['merge', 'a', 'b'], ['rem', 'a', 'h'], ['add', 'a', 'h'], ['rem', 'a', 'h'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['h', 4]]], [[], [['h', 4]]]]), ('stale present copy does not revive', [[['add', 'a', 'q'], ['merge', 'a', 'b'], ['rem', 'a', 'q'], ['merge', 'b', 'a'], ['add', 'b', 'e0'], ['add', 'b', 'e1']], ['a', 'b']], [[[], [['q', 2]]], [['e0', 'e1', 'q'], [['e0', 1], ['e1', 1], ['q', 1]]]])],
    3: [('add then remove', [[['add', 'a', 'x'], ['rem', 'a', 'x']], ['a', 'b']], [[[], [['x', 2]]], [[], []]]), ('re-add after remove', [[['add', 'a', 'x'], ['rem', 'a', 'x'], ['add', 'a', 'x']], ['a', 'b']], [[['x'], [['x', 3]]], [[], []]]), ('adding a present element is a no-op', [[['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y']], ['a', 'b']], [[['y'], [['y', 1]]], [[], []]]), ('removing an absent element is a no-op', [[['rem', 'a', 'z'], ['rem', 'b', 'z'], ['add', 'b', 'w'], ['rem', 'b', 'w'], ['rem', 'b', 'w']], ['a', 'b']], [[[], []], [[], [['w', 2]]]]), ('concurrent adds merge to present', [[['add', 'a', 'k'], ['add', 'b', 'k'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['k'], [['k', 1]]], [['k'], [['k', 1]]]]), ('removal propagates by merge', [[['add', 'a', 'r'], ['merge', 'a', 'b'], ['rem', 'b', 'r'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['r', 2]]], [[], [['r', 2]]]]), ('longer history wins', [[['add', 'a', 'h'], ['merge', 'a', 'b'], ['rem', 'a', 'h'], ['add', 'a', 'h'], ['rem', 'a', 'h'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['h', 4]]], [[], [['h', 4]]]]), ('stale present copy does not revive', [[['add', 'a', 'q'], ['merge', 'a', 'b'], ['rem', 'a', 'q'], ['merge', 'b', 'a'], ['add', 'b', 'e0'], ['add', 'b', 'e1'], ['add', 'b', 'e2']], ['a', 'b']], [[[], [['q', 2]]], [['e0', 'e1', 'e2', 'q'], [['e0', 1], ['e1', 1], ['e2', 1], ['q', 1]]]])],
    4: [('add then remove', [[['add', 'a', 'x'], ['rem', 'a', 'x']], ['a', 'b']], [[[], [['x', 2]]], [[], []]]), ('re-add after remove', [[['add', 'a', 'x'], ['rem', 'a', 'x'], ['add', 'a', 'x']], ['a', 'b']], [[['x'], [['x', 3]]], [[], []]]), ('adding a present element is a no-op', [[['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y']], ['a', 'b']], [[['y'], [['y', 1]]], [[], []]]), ('removing an absent element is a no-op', [[['rem', 'a', 'z'], ['rem', 'b', 'z'], ['add', 'b', 'w'], ['rem', 'b', 'w'], ['rem', 'b', 'w']], ['a', 'b']], [[[], []], [[], [['w', 2]]]]), ('concurrent adds merge to present', [[['add', 'a', 'k'], ['add', 'b', 'k'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['k'], [['k', 1]]], [['k'], [['k', 1]]]]), ('removal propagates by merge', [[['add', 'a', 'r'], ['merge', 'a', 'b'], ['rem', 'b', 'r'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['r', 2]]], [[], [['r', 2]]]]), ('longer history wins', [[['add', 'a', 'h'], ['merge', 'a', 'b'], ['rem', 'a', 'h'], ['add', 'a', 'h'], ['rem', 'a', 'h'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['h', 4]]], [[], [['h', 4]]]]), ('stale present copy does not revive', [[['add', 'a', 'q'], ['merge', 'a', 'b'], ['rem', 'a', 'q'], ['merge', 'b', 'a'], ['add', 'b', 'e0'], ['add', 'b', 'e1'], ['add', 'b', 'e2'], ['add', 'b', 'e3']], ['a', 'b']], [[[], [['q', 2]]], [['e0', 'e1', 'e2', 'e3', 'q'], [['e0', 1], ['e1', 1], ['e2', 1], ['e3', 1], ['q', 1]]]])],
    5: [('add then remove', [[['add', 'a', 'x'], ['rem', 'a', 'x']], ['a', 'b']], [[[], [['x', 2]]], [[], []]]), ('re-add after remove', [[['add', 'a', 'x'], ['rem', 'a', 'x'], ['add', 'a', 'x']], ['a', 'b']], [[['x'], [['x', 3]]], [[], []]]), ('adding a present element is a no-op', [[['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y'], ['add', 'a', 'y']], ['a', 'b']], [[['y'], [['y', 1]]], [[], []]]), ('removing an absent element is a no-op', [[['rem', 'a', 'z'], ['rem', 'b', 'z'], ['add', 'b', 'w'], ['rem', 'b', 'w'], ['rem', 'b', 'w']], ['a', 'b']], [[[], []], [[], [['w', 2]]]]), ('concurrent adds merge to present', [[['add', 'a', 'k'], ['add', 'b', 'k'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['k'], [['k', 1]]], [['k'], [['k', 1]]]]), ('removal propagates by merge', [[['add', 'a', 'r'], ['merge', 'a', 'b'], ['rem', 'b', 'r'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['r', 2]]], [[], [['r', 2]]]]), ('longer history wins', [[['add', 'a', 'h'], ['merge', 'a', 'b'], ['rem', 'a', 'h'], ['add', 'a', 'h'], ['rem', 'a', 'h'], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[[], [['h', 4]]], [[], [['h', 4]]]]), ('stale present copy does not revive', [[['add', 'a', 'q'], ['merge', 'a', 'b'], ['rem', 'a', 'q'], ['merge', 'b', 'a'], ['add', 'b', 'e0'], ['add', 'b', 'e1'], ['add', 'b', 'e2'], ['add', 'b', 'e3'], ['add', 'b', 'e4']], ['a', 'b']], [[[], [['q', 2]]], [['e0', 'e1', 'e2', 'e3', 'e4', 'q'], [['e0', 1], ['e1', 1], ['e2', 1], ['e3', 1], ['e4', 1], ['q', 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)

Boundary fixture	Actual	Expected	Outcome
add then remove	`[[[], [['x', 2]]], [[], []]]`	`[[[], [['x', 2]]], [[], []]]`	Passed
re-add after remove	`[[[], [['x', 2]]], [[], []]]`	`[[['x'], [['x', 3]]], [[], []]]`	Failed
adding a present element is a no-op	`[[['y'], [['y', 1]]], [[], []]]`	`[[['y'], [['y', 1]]], [[], []]]`	Passed
removing an absent element is a no-op	`[[[], []], [[], [['w', 2]]]]`	`[[[], []], [[], [['w', 2]]]]`	Passed
concurrent adds merge to present	`[[['k'], [['k', 1]]], [['k'], [['k', 1]]]]`	`[[['k'], [['k', 1]]], [['k'], [['k', 1]]]]`	Passed
removal propagates by merge	`[[[], [['r', 2]]], [[], [['r', 2]]]]`	`[[[], [['r', 2]]], [[], [['r', 2]]]]`	Passed
longer history wins	`[[[], [['h', 2]]], [[], [['h', 2]]]]`	`[[[], [['h', 4]]], [[], [['h', 4]]]]`	Failed
stale present copy does not revive	`[[[], [['q', 2]]], [['e0', 'q'], [['e0', 1], ['q', 1]]]]`	`[[[], [['q', 2]]], [['e0', 'q'], [['e0', 1], ['q', 1]]]]`	Passed

SHA-256 / 32c3f5032185fd15a23b60ab5e6cd7fad36d1b0a2c3808e4aafabe8f2933c1e8

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 8 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Verification & scope

A deterministic, bounded teaching model of one replicated data type with stipulated operation and merge rules; it is not a production CRDT library and makes no claim of conformance to any specific published design. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:49:04.636977+00:00.

Case digest / d5bb167cd94e8053b86d475bbf0c80264f54369bb6d1a673f98dcf23eb0a0a96