FA-75096 / CRDT convergence / Open access

Replicated growable array: tombstones stop the concurrent-sibling skip · case 01

A replica that already deleted a concurrent insert orders a new insert differently from one that did not.

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

ROOT CAUSE

The skip loop stops at deleted elements, so tombstone state changes the integration position.

THE FAILURE

The skip loop stops at deleted elements, so tombstone state changes the integration position.

Unsuccessful approach: Always skipping tombstones moves the new insert past smaller deleted ids that must stay after it.

Case contract

A sequence of [id, char, deleted] where id = (counter, replica). ["ins", id, after, ch] finds the element with id `after` (head when None or unknown), moves one past it, then skips every following element whose id is greater than the new id before inserting. ["del", id] marks the element deleted but keeps it. Return visible text and the number of slots including tombstones.

Why this case matters

RGA orders concurrent insertions deterministically so that every causally valid delivery order yields the same text.

1 / The failure

Exit 1

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

N = 1
observations = []
def solve(ops):
    seq = []
    for op in ops:
        if op[0] == 'ins':
            nid, after, ch = tuple(op[1]), op[2], op[3]
            if after is None:
                pos = 0
            else:
                pos = next((i for i, e in enumerate(seq) if e[0] == tuple(after)), -1) + 1
            while pos < len(seq) and seq[pos][0] > nid and not seq[pos][2]:
                pos += 1
            seq.insert(pos, [nid, ch, False])
        else:
            for e in seq:
                if e[0] == tuple(op[1]):
                    e[2] = True
    return {'text': ''.join(e[1] for e in seq if not e[2]), 'slots': len(seq)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [1, 'a'], 'Z'], ['del', [5, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [6, 'd'], [5, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [5, 'c'], [1, 'a'], 'm'], ['ins', [6, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [3, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c']]], {'text': 'abc', 'slots': 3}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    2: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [6, 'b'], [1, 'a'], 'Z'], ['del', [6, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [7, 'd'], [6, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [6, 'c'], [1, 'a'], 'm'], ['ins', [7, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [4, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd']]], {'text': 'abcd', 'slots': 4}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    3: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [7, 'b'], [1, 'a'], 'Z'], ['del', [7, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [8, 'd'], [7, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [7, 'c'], [1, 'a'], 'm'], ['ins', [8, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [5, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e']]], {'text': 'abcde', 'slots': 5}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    4: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [8, 'b'], [1, 'a'], 'Z'], ['del', [8, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [9, 'd'], [8, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [8, 'c'], [1, 'a'], 'm'], ['ins', [9, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [6, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f']]], {'text': 'abcdef', 'slots': 6}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    5: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [9, 'b'], [1, 'a'], 'Z'], ['del', [9, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [10, 'd'], [9, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [9, 'c'], [1, 'a'], 'm'], ['ins', [10, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [7, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f'], ['ins', [7, 'a'], [6, 'a'], 'g']]], {'text': 'abcdefg', 'slots': 7}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
}[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
concurrent inserts at one position, order a	`{'slots': 4, 'text': 'HiYX'}`	`{'slots': 4, 'text': 'HiYX'}`	Passed
concurrent inserts at one position, order b	`{'slots': 4, 'text': 'HiYX'}`	`{'slots': 4, 'text': 'HiYX'}`	Passed
insert after a deleted character	`{'slots': 3, 'text': 'H!'}`	`{'slots': 3, 'text': 'H!'}`	Passed
concurrent head inserts	`{'slots': 3, 'text': 'cba'}`	`{'slots': 3, 'text': 'cba'}`	Passed
insert skips a larger concurrent subtree	`{'slots': 5, 'text': 'HiQRP'}`	`{'slots': 5, 'text': 'HiQRP'}`	Passed
skip continues past a larger tombstone	`{'slots': 5, 'text': 'HyWi'}`	`{'slots': 5, 'text': 'HWyi'}`	Failed
smaller tombstone stays after the new insert	`{'slots': 5, 'text': 'HmWi'}`	`{'slots': 5, 'text': 'HmWi'}`	Passed
several larger head inserts are skipped	`{'slots': 3, 'text': 'xyz'}`	`{'slots': 3, 'text': 'xyz'}`	Passed
sequential typing	`{'slots': 3, 'text': 'abc'}`	`{'slots': 3, 'text': 'abc'}`	Passed
deleting keeps the slot	`{'slots': 2, 'text': ''}`	`{'slots': 2, 'text': ''}`	Passed

SHA-256 / 4aacf3318ab21f537fc16908cfac3601805f9eafbcbac21a2ffcbf4d650f400b

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(ops):
    seq = []
    for op in ops:
        if op[0] == 'ins':
            nid, after, ch = tuple(op[1]), op[2], op[3]
            if after is None:
                pos = 0
            else:
                pos = next((i for i, e in enumerate(seq) if e[0] == tuple(after)), -1) + 1
            while pos < len(seq) and (seq[pos][0] > nid or seq[pos][2]):
                pos += 1
            seq.insert(pos, [nid, ch, False])
        else:
            for e in seq:
                if e[0] == tuple(op[1]):
                    e[2] = True
    return {'text': ''.join(e[1] for e in seq if not e[2]), 'slots': len(seq)}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [1, 'a'], 'Z'], ['del', [5, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [6, 'd'], [5, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [5, 'c'], [1, 'a'], 'm'], ['ins', [6, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [3, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c']]], {'text': 'abc', 'slots': 3}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    2: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [6, 'b'], [1, 'a'], 'Z'], ['del', [6, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [7, 'd'], [6, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [6, 'c'], [1, 'a'], 'm'], ['ins', [7, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [4, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd']]], {'text': 'abcd', 'slots': 4}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    3: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [7, 'b'], [1, 'a'], 'Z'], ['del', [7, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [8, 'd'], [7, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [7, 'c'], [1, 'a'], 'm'], ['ins', [8, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [5, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e']]], {'text': 'abcde', 'slots': 5}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    4: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [8, 'b'], [1, 'a'], 'Z'], ['del', [8, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [9, 'd'], [8, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [8, 'c'], [1, 'a'], 'm'], ['ins', [9, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [6, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f']]], {'text': 'abcdef', 'slots': 6}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
    5: [('concurrent inserts at one position, order a', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'a'], [2, 'a'], 'X'], ['ins', [3, 'b'], [2, 'a'], 'Y']]], {'text': 'HiYX', 'slots': 4}), ('concurrent inserts at one position, order b', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [2, 'a'], 'Y'], ['ins', [3, 'a'], [2, 'a'], 'X']]], {'text': 'HiYX', 'slots': 4}), ('insert after a deleted character', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [2, 'a']], ['ins', [3, 'b'], [2, 'a'], '!']]], {'text': 'H!', 'slots': 3}), ('concurrent head inserts', [[['ins', [1, 'b'], None, 'b'], ['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], None, 'c']]], {'text': 'cba', 'slots': 3}), ('insert skips a larger concurrent subtree', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [5, 'b'], [2, 'a'], 'Q'], ['ins', [6, 'b'], [5, 'b'], 'R'], ['ins', [4, 'a'], [2, 'a'], 'P']]], {'text': 'HiQRP', 'slots': 5}), ('skip continues past a larger tombstone', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [9, 'b'], [1, 'a'], 'Z'], ['del', [9, 'b']], ['ins', [3, 'c'], [1, 'a'], 'y'], ['ins', [10, 'd'], [9, 'b'], 'W']]], {'text': 'HWyi', 'slots': 5}), ('smaller tombstone stays after the new insert', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['ins', [3, 'b'], [1, 'a'], 'k'], ['del', [3, 'b']], ['ins', [9, 'c'], [1, 'a'], 'm'], ['ins', [10, 'd'], [3, 'b'], 'W']]], {'text': 'HmWi', 'slots': 5}), ('several larger head inserts are skipped', [[['ins', [7, 'a'], None, 'x'], ['ins', [2, 'b'], None, 'y'], ['ins', [1, 'c'], None, 'z']]], {'text': 'xyz', 'slots': 3}), ('sequential typing', [[['ins', [1, 'a'], None, 'a'], ['ins', [2, 'a'], [1, 'a'], 'b'], ['ins', [3, 'a'], [2, 'a'], 'c'], ['ins', [4, 'a'], [3, 'a'], 'd'], ['ins', [5, 'a'], [4, 'a'], 'e'], ['ins', [6, 'a'], [5, 'a'], 'f'], ['ins', [7, 'a'], [6, 'a'], 'g']]], {'text': 'abcdefg', 'slots': 7}), ('deleting keeps the slot', [[['ins', [1, 'a'], None, 'H'], ['ins', [2, 'a'], [1, 'a'], 'i'], ['del', [1, 'a']], ['del', [2, 'a']]]], {'text': '', 'slots': 2})],
}[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
concurrent inserts at one position, order a	`{'slots': 4, 'text': 'HiYX'}`	`{'slots': 4, 'text': 'HiYX'}`	Passed
concurrent inserts at one position, order b	`{'slots': 4, 'text': 'HiYX'}`	`{'slots': 4, 'text': 'HiYX'}`	Passed
insert after a deleted character	`{'slots': 3, 'text': 'H!'}`	`{'slots': 3, 'text': 'H!'}`	Passed
concurrent head inserts	`{'slots': 3, 'text': 'cba'}`	`{'slots': 3, 'text': 'cba'}`	Passed
insert skips a larger concurrent subtree	`{'slots': 5, 'text': 'HiQRP'}`	`{'slots': 5, 'text': 'HiQRP'}`	Passed
skip continues past a larger tombstone	`{'slots': 5, 'text': 'HWyi'}`	`{'slots': 5, 'text': 'HWyi'}`	Passed
smaller tombstone stays after the new insert	`{'slots': 5, 'text': 'HWmi'}`	`{'slots': 5, 'text': 'HmWi'}`	Failed
several larger head inserts are skipped	`{'slots': 3, 'text': 'xyz'}`	`{'slots': 3, 'text': 'xyz'}`	Passed
sequential typing	`{'slots': 3, 'text': 'abc'}`	`{'slots': 3, 'text': 'abc'}`	Passed
deleting keeps the slot	`{'slots': 2, 'text': ''}`	`{'slots': 2, 'text': ''}`	Passed

SHA-256 / 858b153cc21076d66b989bc9401f77ca29d5c87731fa9a93f67fecccc8294239

HELD IN THE MEMBER ARCHIVE

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

This mechanism has 10 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:03.009210+00:00.

Case digest / d8a1eaab5ffeb7271254741a4a90159f372b88aa3b7b6b425d24ca4c1abf3479