FAILURE MAP
← Case archive

FA-75031 / CRDT convergence / Open access

Causal delivery buffer: delivery adopts the sender's whole vector · case 01

The delivered vector moves backwards and old messages are accepted again.

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

ROOT CAUSE

Delivery replaces the delivered vector with the message vector, regressing entries where the receiver is ahead.

THE FAILURE

Delivery replaces the delivered vector with the message vector, regressing entries where the receiver is ahead.

Unsuccessful approach: Updating with the message vector still overwrites entries where the receiver has delivered more.

Case contract

A receiver starts with an empty delivered vector. An arrival [sender, vector, payload] is a duplicate when its sender entry is at or below the delivered entry or the same (sender, entry) is already buffered. Otherwise it is buffered; then, repeatedly, the oldest buffered message whose sender entry is exactly delivered+1 and whose other entries are all <= delivered is delivered, setting only the sender entry. Return delivered payloads, sorted pending payloads, duplicate count and the delivered vector.

Why this case matters

Operation-based CRDTs converge only if operations are delivered exactly once and in causal order.

1 / The failure

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

N = 1
observations = []
def solve(arrivals):
    local = {}
    delivered, buffer, dups = [], [], 0
    def ready(msg):
        s, vc = msg[0], msg[1]
        if vc.get(s, 0) != local.get(s, 0) + 1:
            return False
        return all(v <= local.get(k, 0) for k, v in vc.items() if k != s)
    for msg in arrivals:
        s, vc = msg[0], msg[1]
        if vc.get(s, 0) <= local.get(s, 0) or any(b[0] == s and b[1].get(s) == vc.get(s) for b in buffer):
            dups += 1
            continue
        buffer.append(msg)
        progress = True
        while progress:
            progress = False
            for b in buffer:
                if ready(b):
                    buffer.remove(b)
                    local = dict(b[1])
                    delivered.append(b[2])
                    progress = True
                    break
    return {'delivered': delivered, 'pending': sorted(b[2] for b in buffer), 'duplicates': dups, 'clock': sorted([k, v] for k, v in local.items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2']]], {'delivered': ['b1', 'b2'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 2]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    2: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3']]], {'delivered': ['b1', 'b2', 'b3'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 3]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 2, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    3: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4']]], {'delivered': ['b1', 'b2', 'b3', 'b4'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 4]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 3, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    4: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4'], ['b', {'b': 5}, 'b5']]], {'delivered': ['b1', 'b2', 'b3', 'b4', 'b5'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 5]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 4, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    5: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4'], ['b', {'b': 5}, 'b5'], ['b', {'b': 6}, 'b6']]], {'delivered': ['b1', 'b2', 'b3', 'b4', 'b5', 'b6'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 6]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 5, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
}[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 fixtureActualExpectedOutcome
in-order stream delivers immediately{'clock': [['a', 2], ['b', 1]], 'delivered': ['a1', 'a2', 'b1'], 'duplicates': 0, 'pending': []}{'clock': [['a', 2], ['b', 1]], 'delivered': ['a1', 'a2', 'b1'], 'duplicates': 0, 'pending': []}Passed
gap from one sender waits{'clock': [['b', 2]], 'delivered': ['b1', 'b2'], 'duplicates': 0, 'pending': ['a2']}{'clock': [['b', 2]], 'delivered': ['b1', 'b2'], 'duplicates': 0, 'pending': ['a2']}Passed
dependency on another sender waits{'clock': [['a', 1], ['b', 1]], 'delivered': ['a1', 'b1'], 'duplicates': 0, 'pending': []}{'clock': [['a', 1], ['b', 1]], 'delivered': ['a1', 'b1'], 'duplicates': 0, 'pending': []}Passed
dependency on an unseen sender waits{'clock': [['a', 1]], 'delivered': ['a1'], 'duplicates': 0, 'pending': ['b1']}{'clock': [['a', 1]], 'delivered': ['a1'], 'duplicates': 0, 'pending': ['b1']}Passed
buffer drains in cascade{'clock': [['a', 3], ['b', 1]], 'delivered': ['a1', 'a2', 'a3', 'b1'], 'duplicates': 0, 'pending': []}{'clock': [['a', 3], ['b', 1]], 'delivered': ['a1', 'a2', 'a3', 'b1'], 'duplicates': 0, 'pending': []}Passed
duplicate of a delivered message is discarded{'clock': [['a', 2]], 'delivered': ['a1', 'a2'], 'duplicates': 1, 'pending': []}{'clock': [['a', 2]], 'delivered': ['a1', 'a2'], 'duplicates': 1, 'pending': []}Passed
duplicate of a buffered message is discarded{'clock': [['a', 2]], 'delivered': ['a1', 'a2'], 'duplicates': 1, 'pending': []}{'clock': [['a', 2]], 'delivered': ['a1', 'a2'], 'duplicates': 1, 'pending': []}Passed
receiver ahead of a dependency keeps its clock{'clock': [['a', 3]], 'delivered': ['a1', 'a2', 'b1', 'a2', 'a3'], 'duplicates': 0, 'pending': []}{'clock': [['a', 3], ['b', 1]], 'delivered': ['a1', 'a2', 'b1', 'a3'], 'duplicates': 1, 'pending': []}Failed
scan restarts from the oldest buffered message{'clock': [['a', 1], ['b', 2]], 'delivered': ['c0', 'a1', 'b1', 'b2'], 'duplicates': 0, 'pending': ['c2']}{'clock': [['a', 1], ['b', 2], ['c', 2]], 'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'duplicates': 0, 'pending': []}Failed
empty arrival stream{'clock': [], 'delivered': [], 'duplicates': 0, 'pending': []}{'clock': [], 'delivered': [], 'duplicates': 0, 'pending': []}Passed

SHA-256 / f7df3281f99179110e5e445b896330749f269118438c302a15d944d27efe44e6

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(arrivals):
    local = {}
    delivered, buffer, dups = [], [], 0
    def ready(msg):
        s, vc = msg[0], msg[1]
        if vc.get(s, 0) != local.get(s, 0) + 1:
            return False
        return all(v <= local.get(k, 0) for k, v in vc.items() if k != s)
    for msg in arrivals:
        s, vc = msg[0], msg[1]
        if vc.get(s, 0) <= local.get(s, 0) or any(b[0] == s and b[1].get(s) == vc.get(s) for b in buffer):
            dups += 1
            continue
        buffer.append(msg)
        progress = True
        while progress:
            progress = False
            for b in buffer:
                if ready(b):
                    buffer.remove(b)
                    local.update(b[1])
                    delivered.append(b[2])
                    progress = True
                    break
    return {'delivered': delivered, 'pending': sorted(b[2] for b in buffer), 'duplicates': dups, 'clock': sorted([k, v] for k, v in local.items())}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2']]], {'delivered': ['b1', 'b2'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 2]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    2: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3']]], {'delivered': ['b1', 'b2', 'b3'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 3]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 2, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    3: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4']]], {'delivered': ['b1', 'b2', 'b3', 'b4'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 4]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 3, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    4: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4'], ['b', {'b': 5}, 'b5']]], {'delivered': ['b1', 'b2', 'b3', 'b4', 'b5'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 5]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 4, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
    5: [('in-order stream delivers immediately', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 2, 'b': 1}, 'b1']]], {'delivered': ['a1', 'a2', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 2], ['b', 1]]}), ('gap from one sender waits', [[['a', {'a': 2}, 'a2'], ['b', {'b': 1}, 'b1'], ['b', {'b': 2}, 'b2'], ['b', {'b': 3}, 'b3'], ['b', {'b': 4}, 'b4'], ['b', {'b': 5}, 'b5'], ['b', {'b': 6}, 'b6']]], {'delivered': ['b1', 'b2', 'b3', 'b4', 'b5', 'b6'], 'pending': ['a2'], 'duplicates': 0, 'clock': [['b', 6]]}), ('dependency on another sender waits', [[['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 1]]}), ('dependency on an unseen sender waits', [[['b', {'c': 1, 'b': 1}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1'], 'pending': ['b1'], 'duplicates': 0, 'clock': [['a', 1]]}), ('buffer drains in cascade', [[['a', {'a': 3}, 'a3'], ['a', {'a': 2}, 'a2'], ['b', {'b': 1, 'a': 3}, 'b1'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2', 'a3', 'b1'], 'pending': [], 'duplicates': 0, 'clock': [['a', 3], ['b', 1]]}), ('duplicate of a delivered message is discarded', [[['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 5, 'clock': [['a', 2]]}), ('duplicate of a buffered message is discarded', [[['a', {'a': 2}, 'a2'], ['a', {'a': 2}, 'a2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['a1', 'a2'], 'pending': [], 'duplicates': 1, 'clock': [['a', 2]]}), ('receiver ahead of a dependency keeps its clock', [[['a', {'a': 1}, 'a1'], ['a', {'a': 2}, 'a2'], ['b', {'a': 1, 'b': 1}, 'b1'], ['a', {'a': 2}, 'a2'], ['a', {'a': 3}, 'a3']]], {'delivered': ['a1', 'a2', 'b1', 'a3'], 'pending': [], 'duplicates': 1, 'clock': [['a', 3], ['b', 1]]}), ('scan restarts from the oldest buffered message', [[['b', {'b': 1, 'a': 1}, 'b1'], ['c', {'c': 1}, 'c0'], ['b', {'b': 2, 'a': 1}, 'b2'], ['c', {'c': 2, 'a': 1}, 'c2'], ['a', {'a': 1}, 'a1']]], {'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'pending': [], 'duplicates': 0, 'clock': [['a', 1], ['b', 2], ['c', 2]]}), ('empty arrival stream', [[]], {'delivered': [], 'pending': [], 'duplicates': 0, 'clock': []})],
}[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 fixtureActualExpectedOutcome
in-order stream delivers immediately{'clock': [['a', 2], ['b', 1]], 'delivered': ['a1', 'a2', 'b1'], 'duplicates': 0, 'pending': []}{'clock': [['a', 2], ['b', 1]], 'delivered': ['a1', 'a2', 'b1'], 'duplicates': 0, 'pending': []}Passed
gap from one sender waits{'clock': [['b', 2]], 'delivered': ['b1', 'b2'], 'duplicates': 0, 'pending': ['a2']}{'clock': [['b', 2]], 'delivered': ['b1', 'b2'], 'duplicates': 0, 'pending': ['a2']}Passed
dependency on another sender waits{'clock': [['a', 1], ['b', 1]], 'delivered': ['a1', 'b1'], 'duplicates': 0, 'pending': []}{'clock': [['a', 1], ['b', 1]], 'delivered': ['a1', 'b1'], 'duplicates': 0, 'pending': []}Passed
dependency on an unseen sender waits{'clock': [['a', 1]], 'delivered': ['a1'], 'duplicates': 0, 'pending': ['b1']}{'clock': [['a', 1]], 'delivered': ['a1'], 'duplicates': 0, 'pending': ['b1']}Passed
buffer drains in cascade{'clock': [['a', 3], ['b', 1]], 'delivered': ['a1', 'a2', 'a3', 'b1'], 'duplicates': 0, 'pending': []}{'clock': [['a', 3], ['b', 1]], 'delivered': ['a1', 'a2', 'a3', 'b1'], 'duplicates': 0, 'pending': []}Passed
duplicate of a delivered message is discarded{'clock': [['a', 2]], 'delivered': ['a1', 'a2'], 'duplicates': 1, 'pending': []}{'clock': [['a', 2]], 'delivered': ['a1', 'a2'], 'duplicates': 1, 'pending': []}Passed
duplicate of a buffered message is discarded{'clock': [['a', 2]], 'delivered': ['a1', 'a2'], 'duplicates': 1, 'pending': []}{'clock': [['a', 2]], 'delivered': ['a1', 'a2'], 'duplicates': 1, 'pending': []}Passed
receiver ahead of a dependency keeps its clock{'clock': [['a', 3], ['b', 1]], 'delivered': ['a1', 'a2', 'b1', 'a2', 'a3'], 'duplicates': 0, 'pending': []}{'clock': [['a', 3], ['b', 1]], 'delivered': ['a1', 'a2', 'b1', 'a3'], 'duplicates': 1, 'pending': []}Failed
scan restarts from the oldest buffered message{'clock': [['a', 1], ['b', 2], ['c', 2]], 'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'duplicates': 0, 'pending': []}{'clock': [['a', 1], ['b', 2], ['c', 2]], 'delivered': ['c0', 'a1', 'b1', 'b2', 'c2'], 'duplicates': 0, 'pending': []}Passed
empty arrival stream{'clock': [], 'delivered': [], 'duplicates': 0, 'pending': []}{'clock': [], 'delivered': [], 'duplicates': 0, 'pending': []}Passed

SHA-256 / b1bb391c8ff2e99ae88d7bc381518660bd70c0568fee386df254fcf073577bf7

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.

Sign in to the archive ↗

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

Case digest / 6dc7b54300f36251735350caac669aa604722f39296b1621191e552442b58c19