FA-75211 / CRDT convergence / Open access
Fractional position allocation: the upper neighbour keeps constraining after the prefix diverges · case 01
Positions are allocated deeper than necessary or squeezed against digits that no longer bound them.
ROOT CAUSE
Once a digit strictly below q's digit is chosen, q still bounds deeper digits.
VERIFIED REPAIR
Stop consulting the upper neighbour as soon as the chosen digit is below its digit.
Unsuccessful approach: Releasing only after the lower neighbour is exhausted keeps the stale bound for longer lower neighbours.
Case contract
Starting from the given sorted positions, positions are digit lists in base 10 compared lexicographically and never ending in 0. Inserting at list index i allocates between the neighbours p (or [] at the start) and q (or [] at the end): walking depth d, lower digit a is p[d] or 0, upper digit b is q[d] while q still constrains (else 10); if b - a > 1 append (a+b)//2 and stop, else append a, and q stops constraining once a < b. Return positions as dotted strings in list order.
Why this case matters
Sequence CRDTs such as Logoot and LSEQ assign dense identifiers so that concurrent inserts never need renumbering.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(initial, inserts):
BASE = 10
lst = [list(p) for p in initial]
def between(p, q):
out = []
upper = True
d = 0
while True:
a = p[d] if d < len(p) else 0
b = q[d] if upper and d < len(q) else BASE
if b - a > 1:
out.append((a + b) // 2)
return out
out.append(a)
d += 1
for i in inserts:
p = lst[i - 1] if i > 0 else []
q = lst[i] if i < len(lst) else []
lst.insert(i, between(p, q))
return ['.'.join(str(x) for x in pos) for pos in lst]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4]], ['5', '7', '8', '9', '9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0]], ['0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2]], ['2', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1]], ['1.2.9', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
2: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5]], ['5', '7', '8', '9', '9.5', '9.7']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0]], ['0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1]], ['2', '3', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1]], ['1.2.9', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
3: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6]], ['5', '7', '8', '9', '9.5', '9.7', '9.8']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0]], ['0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3]], ['2', '3', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1]], ['1.2.9', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
4: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2]], ['2', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1]], ['1.2.9', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
5: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7, 8]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9', '9.9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.1', '0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2, 1]], ['2', '2.5', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1, 1]], ['1.2.9', '1.2.9.2', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
}[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 |
|---|---|---|---|
| first insert | ['5'] | ['5'] | Passed |
| append repeatedly | ['5', '7', '8', '9', '9.5'] | ['5', '7', '8', '9', '9.5'] | Passed |
| prepend repeatedly | ['0.2', '0.5', '1', '2', '5'] | ['0.2', '0.5', '1', '2', '5'] | Passed |
| insert between adjacent digits | ['5', '5.2', '5.5', '6', '7'] | ['5', '5.2', '5.5', '6', '7'] | Passed |
| insert after a deep position | ['5', '5.5', '5.6', '5.7', '6', '7'] | ['5', '5.5', '5.6', '5.7', '6', '7'] | Passed |
| mixed positions | ['2', '5', '7'] | ['2', '5', '7'] | Passed |
| upper neighbour stops constraining after divergence | ['3.7', '3.7.5', '4.8'] | ['3.7', '3.8', '4.8'] | Failed |
| deep upper neighbour after a one-digit step | ['2', '2.0.1', '2.0.2', '3.1.4'] | ['2', '2.2', '2.5', '3.1.4'] | Failed |
| long lower neighbour below a deep upper neighbour | ['1.2.9', '1.2.9.5', '2.0.5'] | ['1.2.9', '1.6', '2.0.5'] | Failed |
| open end after high digits | ['8', '9.9', '9.9.5', '9.9.7'] | ['8', '9.9', '9.9.5', '9.9.7'] | Passed |
SHA-256 / 01d57eecaf6f609be39804d93d139cb59e88dadeb4fa5020922e836765c0d218
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(initial, inserts):
BASE = 10
lst = [list(p) for p in initial]
def between(p, q):
out = []
upper = True
d = 0
while True:
a = p[d] if d < len(p) else 0
b = q[d] if upper and d < len(q) else BASE
if b - a > 1:
out.append((a + b) // 2)
return out
out.append(a)
if a < b and d + 1 >= len(p):
upper = False
d += 1
for i in inserts:
p = lst[i - 1] if i > 0 else []
q = lst[i] if i < len(lst) else []
lst.insert(i, between(p, q))
return ['.'.join(str(x) for x in pos) for pos in lst]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4]], ['5', '7', '8', '9', '9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0]], ['0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2]], ['2', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1]], ['1.2.9', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
2: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5]], ['5', '7', '8', '9', '9.5', '9.7']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0]], ['0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1]], ['2', '3', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1]], ['1.2.9', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
3: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6]], ['5', '7', '8', '9', '9.5', '9.7', '9.8']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0]], ['0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3]], ['2', '3', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1]], ['1.2.9', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
4: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2]], ['2', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1]], ['1.2.9', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
5: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7, 8]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9', '9.9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.1', '0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2, 1]], ['2', '2.5', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1, 1]], ['1.2.9', '1.2.9.2', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
}[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 |
|---|---|---|---|
| first insert | ['5'] | ['5'] | Passed |
| append repeatedly | ['5', '7', '8', '9', '9.5'] | ['5', '7', '8', '9', '9.5'] | Passed |
| prepend repeatedly | ['0.2', '0.5', '1', '2', '5'] | ['0.2', '0.5', '1', '2', '5'] | Passed |
| insert between adjacent digits | ['5', '5.2', '5.5', '6', '7'] | ['5', '5.2', '5.5', '6', '7'] | Passed |
| insert after a deep position | ['5', '5.5', '5.6', '5.7', '6', '7'] | ['5', '5.5', '5.6', '5.7', '6', '7'] | Passed |
| mixed positions | ['2', '5', '7'] | ['2', '5', '7'] | Passed |
| upper neighbour stops constraining after divergence | ['3.7', '3.7.5', '4.8'] | ['3.7', '3.8', '4.8'] | Failed |
| deep upper neighbour after a one-digit step | ['2', '2.2', '2.5', '3.1.4'] | ['2', '2.2', '2.5', '3.1.4'] | Passed |
| long lower neighbour below a deep upper neighbour | ['1.2.9', '1.2.9.5', '2.0.5'] | ['1.2.9', '1.6', '2.0.5'] | Failed |
| open end after high digits | ['8', '9.9', '9.9.5', '9.9.7'] | ['8', '9.9', '9.9.5', '9.9.7'] | Passed |
SHA-256 / 4c7318862f851e89b640dd274646cec6625f119ec661e121947c7f5a2bd3cf2f
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(initial, inserts):
BASE = 10
lst = [list(p) for p in initial]
def between(p, q):
out = []
upper = True
d = 0
while True:
a = p[d] if d < len(p) else 0
b = q[d] if upper and d < len(q) else BASE
if b - a > 1:
out.append((a + b) // 2)
return out
out.append(a)
if a < b:
upper = False
d += 1
for i in inserts:
p = lst[i - 1] if i > 0 else []
q = lst[i] if i < len(lst) else []
lst.insert(i, between(p, q))
return ['.'.join(str(x) for x in pos) for pos in lst]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4]], ['5', '7', '8', '9', '9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0]], ['0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2]], ['2', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1]], ['1.2.9', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
2: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5]], ['5', '7', '8', '9', '9.5', '9.7']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0]], ['0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1]], ['2', '3', '5', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1]], ['1.2.9', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
3: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6]], ['5', '7', '8', '9', '9.5', '9.7', '9.8']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0]], ['0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3]], ['2', '3', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1]], ['1.2.9', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
4: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2]], ['2', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1]], ['1.2.9', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
5: [('first insert', [[], [0]], ['5']), ('append repeatedly', [[], [0, 1, 2, 3, 4, 5, 6, 7, 8]], ['5', '7', '8', '9', '9.5', '9.7', '9.8', '9.9', '9.9.5']), ('prepend repeatedly', [[], [0, 0, 0, 0, 0, 0, 0, 0, 0]], ['0.0.1', '0.0.2', '0.0.5', '0.1', '0.2', '0.5', '1', '2', '5']), ('insert between adjacent digits', [[], [0, 1, 1, 1, 1]], ['5', '5.2', '5.5', '6', '7']), ('insert after a deep position', [[], [0, 1, 1, 1, 2, 2]], ['5', '5.5', '5.6', '5.7', '6', '7']), ('mixed positions', [[], [0, 0, 2, 1, 3, 2, 1]], ['2', '2.5', '3', '4', '5', '6', '7']), ('upper neighbour stops constraining after divergence', [[[3, 7], [4, 8]], [1]], ['3.7', '3.8', '4.8']), ('deep upper neighbour after a one-digit step', [[[2], [3, 1, 4]], [1, 1]], ['2', '2.2', '2.5', '3.1.4']), ('long lower neighbour below a deep upper neighbour', [[[1, 2, 9], [2, 0, 5]], [1, 1, 1, 1, 1]], ['1.2.9', '1.2.9.2', '1.2.9.5', '1.3', '1.4', '1.6', '2.0.5']), ('open end after high digits', [[[8], [9, 9]], [2, 3]], ['8', '9.9', '9.9.5', '9.9.7'])],
}[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 |
|---|---|---|---|
| first insert | ['5'] | ['5'] | Passed |
| append repeatedly | ['5', '7', '8', '9', '9.5'] | ['5', '7', '8', '9', '9.5'] | Passed |
| prepend repeatedly | ['0.2', '0.5', '1', '2', '5'] | ['0.2', '0.5', '1', '2', '5'] | Passed |
| insert between adjacent digits | ['5', '5.2', '5.5', '6', '7'] | ['5', '5.2', '5.5', '6', '7'] | Passed |
| insert after a deep position | ['5', '5.5', '5.6', '5.7', '6', '7'] | ['5', '5.5', '5.6', '5.7', '6', '7'] | Passed |
| mixed positions | ['2', '5', '7'] | ['2', '5', '7'] | Passed |
| upper neighbour stops constraining after divergence | ['3.7', '3.8', '4.8'] | ['3.7', '3.8', '4.8'] | Passed |
| deep upper neighbour after a one-digit step | ['2', '2.2', '2.5', '3.1.4'] | ['2', '2.2', '2.5', '3.1.4'] | Passed |
| long lower neighbour below a deep upper neighbour | ['1.2.9', '1.6', '2.0.5'] | ['1.2.9', '1.6', '2.0.5'] | Passed |
| open end after high digits | ['8', '9.9', '9.9.5', '9.9.7'] | ['8', '9.9', '9.9.5', '9.9.7'] | Passed |
SHA-256 / bd37b7eca55f08422e58136c50140f65844f3d387bad6d401573033c75ecb949
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.026155+00:00.
Case digest / 4c63969bb91b53ba97b7b563ad46597b391b66b30a892efe94534ae0fc8b1644