FA-75331 / CRDT convergence / Open access

Delete set normalization: ranges are merged in arrival order · case 01

Unsorted delete sets normalize to overlapping or out-of-order ranges.

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

ROOT CAUSE

The per-client ranges are not sorted by clock before the linear merge.

VERIFIED REPAIR

Sort each client's ranges by start clock before merging.

Unsuccessful approach: Sorting by end clock still places a long early range after short ranges it contains.

Case contract

A delete set is a list of [client, clock, length] ranges, possibly unsorted, overlapping or adjacent. Normalize per client in client order: sort by clock and merge ranges that overlap or touch. Queries [client, clock] report whether the clock lies in a merged range (end exclusive). Return merged ranges and query answers.

Why this case matters

Sequence CRDTs ship deletions as compact range sets that every replica must normalize identically.

1 / The failure

Exit 1

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

N = 1
observations = []
def solve(ranges, queries):
    by = {}
    for c, clk, ln in ranges:
        by.setdefault(c, []).append([clk, ln])
    out = []
    for c in sorted(by):
        rs = list(by[c])
        merged = [rs[0][:]]
        for clk, ln in rs[1:]:
            last = merged[-1]
            if clk <= last[0] + last[1]:
                last[1] = max(last[1], clk + ln - last[0])
            else:
                merged.append([clk, ln])
        out.extend([c, a, b] for a, b in merged)
    hits = [any(c == q[0] and a <= q[1] < a + b for c, a, b in out) for q in queries]
    return {'ranges': out, 'hits': hits}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 4]], [[3, 9], [3, 10], [3, 4]]], {'ranges': [[3, 5, 6]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 1], [6, 2, 2], [5, 1, 1]], [[5, 1], [6, 0], [6, 3]]], {'ranges': [[5, 0, 2], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    2: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 5]], [[3, 10], [3, 11], [3, 4]]], {'ranges': [[3, 5, 7]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 2], [6, 2, 2], [5, 2, 1]], [[5, 2], [6, 0], [6, 3]]], {'ranges': [[5, 0, 3], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    3: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 6]], [[3, 11], [3, 12], [3, 4]]], {'ranges': [[3, 5, 8]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 3], [6, 2, 2], [5, 3, 1]], [[5, 3], [6, 0], [6, 3]]], {'ranges': [[5, 0, 4], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    4: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 7]], [[3, 12], [3, 13], [3, 4]]], {'ranges': [[3, 5, 9]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 4], [6, 2, 2], [5, 4, 1]], [[5, 4], [6, 0], [6, 3]]], {'ranges': [[5, 0, 5], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    5: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 8]], [[3, 13], [3, 14], [3, 4]]], {'ranges': [[3, 5, 10]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 5], [6, 2, 2], [5, 5, 1]], [[5, 5], [6, 0], [6, 3]]], {'ranges': [[5, 0, 6], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
}[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
adjacent ranges merge	`{'hits': [True, False], 'ranges': [[1, 0, 5]]}`	`{'hits': [True, False], 'ranges': [[1, 0, 5]]}`	Passed
one-clock gap stays split	`{'hits': [False, True], 'ranges': [[1, 0, 2], [1, 3, 1]]}`	`{'hits': [False, True], 'ranges': [[1, 0, 2], [1, 3, 1]]}`	Passed
contained range does not shrink	`{'hits': [True, False], 'ranges': [[2, 0, 10]]}`	`{'hits': [True, False], 'ranges': [[2, 0, 10]]}`	Passed
overlap extends	`{'hits': [True, True, False], 'ranges': [[3, 5, 6]]}`	`{'hits': [True, True, False], 'ranges': [[3, 5, 6]]}`	Passed
unsorted input	`{'hits': [True, False], 'ranges': [[4, 9, 2]]}`	`{'hits': [True, False], 'ranges': [[4, 0, 11]]}`	Failed
several clients	`{'hits': [True, False, True], 'ranges': [[5, 0, 2], [6, 1, 3]]}`	`{'hits': [True, False, True], 'ranges': [[5, 0, 2], [6, 1, 3]]}`	Passed
long range earlier start sorted after by end	`{'hits': [False, True], 'ranges': [[8, 0, 20], [8, 21, 2]]}`	`{'hits': [False, True], 'ranges': [[8, 0, 20], [8, 21, 2]]}`	Passed
empty input	`{'hits': [False], 'ranges': []}`	`{'hits': [False], 'ranges': []}`	Passed

SHA-256 / 318b2b99fa716ea1b0bb22e2ddddc9e5436740fb4363a52b08a7df3b8fde5b3d

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(ranges, queries):
    by = {}
    for c, clk, ln in ranges:
        by.setdefault(c, []).append([clk, ln])
    out = []
    for c in sorted(by):
        rs = sorted(by[c], key=lambda r: r[0] + r[1])
        merged = [rs[0][:]]
        for clk, ln in rs[1:]:
            last = merged[-1]
            if clk <= last[0] + last[1]:
                last[1] = max(last[1], clk + ln - last[0])
            else:
                merged.append([clk, ln])
        out.extend([c, a, b] for a, b in merged)
    hits = [any(c == q[0] and a <= q[1] < a + b for c, a, b in out) for q in queries]
    return {'ranges': out, 'hits': hits}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 4]], [[3, 9], [3, 10], [3, 4]]], {'ranges': [[3, 5, 6]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 1], [6, 2, 2], [5, 1, 1]], [[5, 1], [6, 0], [6, 3]]], {'ranges': [[5, 0, 2], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    2: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 5]], [[3, 10], [3, 11], [3, 4]]], {'ranges': [[3, 5, 7]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 2], [6, 2, 2], [5, 2, 1]], [[5, 2], [6, 0], [6, 3]]], {'ranges': [[5, 0, 3], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    3: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 6]], [[3, 11], [3, 12], [3, 4]]], {'ranges': [[3, 5, 8]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 3], [6, 2, 2], [5, 3, 1]], [[5, 3], [6, 0], [6, 3]]], {'ranges': [[5, 0, 4], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    4: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 7]], [[3, 12], [3, 13], [3, 4]]], {'ranges': [[3, 5, 9]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 4], [6, 2, 2], [5, 4, 1]], [[5, 4], [6, 0], [6, 3]]], {'ranges': [[5, 0, 5], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    5: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 8]], [[3, 13], [3, 14], [3, 4]]], {'ranges': [[3, 5, 10]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 5], [6, 2, 2], [5, 5, 1]], [[5, 5], [6, 0], [6, 3]]], {'ranges': [[5, 0, 6], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
}[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
adjacent ranges merge	`{'hits': [True, False], 'ranges': [[1, 0, 5]]}`	`{'hits': [True, False], 'ranges': [[1, 0, 5]]}`	Passed
one-clock gap stays split	`{'hits': [False, True], 'ranges': [[1, 0, 2], [1, 3, 1]]}`	`{'hits': [False, True], 'ranges': [[1, 0, 2], [1, 3, 1]]}`	Passed
contained range does not shrink	`{'hits': [True, False], 'ranges': [[2, 3, 7]]}`	`{'hits': [True, False], 'ranges': [[2, 0, 10]]}`	Failed
overlap extends	`{'hits': [True, True, False], 'ranges': [[3, 5, 6]]}`	`{'hits': [True, True, False], 'ranges': [[3, 5, 6]]}`	Passed
unsorted input	`{'hits': [True, False], 'ranges': [[4, 0, 11]]}`	`{'hits': [True, False], 'ranges': [[4, 0, 11]]}`	Passed
several clients	`{'hits': [True, False, True], 'ranges': [[5, 0, 2], [6, 1, 3]]}`	`{'hits': [True, False, True], 'ranges': [[5, 0, 2], [6, 1, 3]]}`	Passed
long range earlier start sorted after by end	`{'hits': [False, True], 'ranges': [[8, 5, 15], [8, 21, 2]]}`	`{'hits': [False, True], 'ranges': [[8, 0, 20], [8, 21, 2]]}`	Failed
empty input	`{'hits': [False], 'ranges': []}`	`{'hits': [False], 'ranges': []}`	Passed

SHA-256 / 2ac787ee9009ba9b0462f60194f4b53cef7155a277f97dd763a39a7e6b3f0c7a

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(ranges, queries):
    by = {}
    for c, clk, ln in ranges:
        by.setdefault(c, []).append([clk, ln])
    out = []
    for c in sorted(by):
        rs = sorted(by[c])
        merged = [rs[0][:]]
        for clk, ln in rs[1:]:
            last = merged[-1]
            if clk <= last[0] + last[1]:
                last[1] = max(last[1], clk + ln - last[0])
            else:
                merged.append([clk, ln])
        out.extend([c, a, b] for a, b in merged)
    hits = [any(c == q[0] and a <= q[1] < a + b for c, a, b in out) for q in queries]
    return {'ranges': out, 'hits': hits}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 4]], [[3, 9], [3, 10], [3, 4]]], {'ranges': [[3, 5, 6]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 1], [6, 2, 2], [5, 1, 1]], [[5, 1], [6, 0], [6, 3]]], {'ranges': [[5, 0, 2], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    2: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 5]], [[3, 10], [3, 11], [3, 4]]], {'ranges': [[3, 5, 7]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 2], [6, 2, 2], [5, 2, 1]], [[5, 2], [6, 0], [6, 3]]], {'ranges': [[5, 0, 3], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    3: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 6]], [[3, 11], [3, 12], [3, 4]]], {'ranges': [[3, 5, 8]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 3], [6, 2, 2], [5, 3, 1]], [[5, 3], [6, 0], [6, 3]]], {'ranges': [[5, 0, 4], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    4: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 7]], [[3, 12], [3, 13], [3, 4]]], {'ranges': [[3, 5, 9]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 4], [6, 2, 2], [5, 4, 1]], [[5, 4], [6, 0], [6, 3]]], {'ranges': [[5, 0, 5], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
    5: [('adjacent ranges merge', [[[1, 0, 2], [1, 2, 3]], [[1, 4], [1, 5]]], {'ranges': [[1, 0, 5]], 'hits': [True, False]}), ('one-clock gap stays split', [[[1, 0, 2], [1, 3, 1]], [[1, 2], [1, 3]]], {'ranges': [[1, 0, 2], [1, 3, 1]], 'hits': [False, True]}), ('contained range does not shrink', [[[2, 0, 10], [2, 3, 2]], [[2, 9], [2, 10]]], {'ranges': [[2, 0, 10]], 'hits': [True, False]}), ('overlap extends', [[[3, 5, 4], [3, 7, 8]], [[3, 13], [3, 14], [3, 4]]], {'ranges': [[3, 5, 10]], 'hits': [True, True, False]}), ('unsorted input', [[[4, 9, 2], [4, 0, 3], [4, 3, 6]], [[4, 10], [4, 11]]], {'ranges': [[4, 0, 11]], 'hits': [True, False]}), ('several clients', [[[6, 1, 1], [5, 0, 5], [6, 2, 2], [5, 5, 1]], [[5, 5], [6, 0], [6, 3]]], {'ranges': [[5, 0, 6], [6, 1, 3]], 'hits': [True, False, True]}), ('long range earlier start sorted after by end', [[[8, 0, 20], [8, 5, 1], [8, 21, 2]], [[8, 20], [8, 21]]], {'ranges': [[8, 0, 20], [8, 21, 2]], 'hits': [False, True]}), ('empty input', [[], [[1, 0]]], {'ranges': [], 'hits': [False]})],
}[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
adjacent ranges merge	`{'hits': [True, False], 'ranges': [[1, 0, 5]]}`	`{'hits': [True, False], 'ranges': [[1, 0, 5]]}`	Passed
one-clock gap stays split	`{'hits': [False, True], 'ranges': [[1, 0, 2], [1, 3, 1]]}`	`{'hits': [False, True], 'ranges': [[1, 0, 2], [1, 3, 1]]}`	Passed
contained range does not shrink	`{'hits': [True, False], 'ranges': [[2, 0, 10]]}`	`{'hits': [True, False], 'ranges': [[2, 0, 10]]}`	Passed
overlap extends	`{'hits': [True, True, False], 'ranges': [[3, 5, 6]]}`	`{'hits': [True, True, False], 'ranges': [[3, 5, 6]]}`	Passed
unsorted input	`{'hits': [True, False], 'ranges': [[4, 0, 11]]}`	`{'hits': [True, False], 'ranges': [[4, 0, 11]]}`	Passed
several clients	`{'hits': [True, False, True], 'ranges': [[5, 0, 2], [6, 1, 3]]}`	`{'hits': [True, False, True], 'ranges': [[5, 0, 2], [6, 1, 3]]}`	Passed
long range earlier start sorted after by end	`{'hits': [False, True], 'ranges': [[8, 0, 20], [8, 21, 2]]}`	`{'hits': [False, True], 'ranges': [[8, 0, 20], [8, 21, 2]]}`	Passed
empty input	`{'hits': [False], 'ranges': []}`	`{'hits': [False], 'ranges': []}`	Passed

SHA-256 / d56fbc60856d774d390799787a14c39164ac12816ab600995fab894f7065f355

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:05.410732+00:00.

Case digest / f1c0bd7364a06c17475a0b92e1931f01ea865b83dfd90deb531a08175dc5d948