FA-74891 / CRDT convergence / Open access

LWW register with Lamport stamps: receive does not advance the local clock · case 01

A write made after receiving a newer value loses to that older value on other replicas.

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

ROOT CAUSE

Delivery never folds the incoming clock into the receiver's Lamport clock, so causally later writes get smaller stamps.

VERIFIED REPAIR

On every delivery set the receiver's clock to the maximum of its own and the incoming stamp clock.

Unsuccessful approach: Assigning the incoming clock outright moves the receiver's clock backwards when it is ahead.

Case contract

Each replica holds a register [value, clock, writer] and a Lamport clock, all starting at [None, 0, ""] and 0. ["set", r, v] increments r's clock and stamps v with (clock, r). ["send", s, d] delivers s's register to d: d's clock becomes max(own, incoming clock) and d adopts the incoming register when (clock, writer) is lexicographically larger. Return values and clocks per replica.

Why this case matters

Last-writer-wins registers need total, replica-independent stamp ordering to converge.

1 / The failure

Exit 1

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

N = 1
observations = []
def solve(events, replicas):
    clock = {r: 0 for r in replicas}
    reg = {r: [None, 0, ''] for r in replicas}
    for ev in events:
        if ev[0] == 'set':
            r = ev[1]
            clock[r] += 1
            reg[r] = [ev[2], clock[r], r]
        else:
            s, d = ev[1], ev[2]
            inc = reg[s]
            if (inc[1], inc[2]) > (reg[d][1], reg[d][2]):
                reg[d] = list(inc)
    return {'values': [reg[r][0] for r in replicas], 'clocks': [clock[r] for r in replicas]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x1'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q1'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s0', 's0', 's0'], 'clocks': [2, 2, 2]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 4, 4]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv1'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv1', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    2: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x2'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q2'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s1', 's1', 's1'], 'clocks': [3, 3, 3]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 5, 5]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv2'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv2', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    3: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x3'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q3'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['set', 'a', 's2'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s2', 's2', 's2'], 'clocks': [4, 4, 4]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['set', 'b', 'b4'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 6, 6]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv3'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv3', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    4: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x4'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q4'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['set', 'a', 's2'], ['set', 'a', 's3'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s3', 's3', 's3'], 'clocks': [5, 5, 5]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['set', 'b', 'b4'], ['set', 'b', 'b5'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 7, 7]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv4'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv4', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    5: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x5'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q5'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['set', 'a', 's2'], ['set', 'a', 's3'], ['set', 'a', 's4'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s4', 's4', 's4'], 'clocks': [6, 6, 6]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['set', 'b', 'b4'], ['set', 'b', 'b5'], ['set', 'b', 'b6'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 8, 8]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv5'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv5', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
later local write after receive wins	`{'clocks': [2, 1, 0], 'values': ['a2', 'b1', None]}`	`{'clocks': [3, 3, 0], 'values': ['b1', 'b1', None]}`	Failed
equal stamps break toward larger replica id	`{'clocks': [1, 1, 0], 'values': ['y', 'y', None]}`	`{'clocks': [1, 1, 0], 'values': ['y', 'y', None]}`	Passed
equal stamps other direction	`{'clocks': [1, 0, 1], 'values': ['p', None, 'p']}`	`{'clocks': [1, 0, 1], 'values': ['p', None, 'p']}`	Passed
older state is ignored	`{'clocks': [2, 1, 0], 'values': ['s0', 's0', 's0']}`	`{'clocks': [2, 2, 2], 'values': ['s0', 's0', 's0']}`	Failed
ring gossip converges	`{'clocks': [1, 1, 1], 'values': ['C', 'C', 'C']}`	`{'clocks': [1, 1, 1], 'values': ['C', 'C', 'C']}`	Passed
empty send	`{'clocks': [0, 0, 0], 'values': [None, None, None]}`	`{'clocks': [0, 0, 0], 'values': [None, None, None]}`	Passed
receiving from an empty replica keeps the clock	`{'clocks': [0, 4, 0], 'values': [None, 'last', 'last']}`	`{'clocks': [0, 4, 4], 'values': [None, 'last', 'last']}`	Failed
adopted value keeps its writer identity	`{'clocks': [1, 1, 0], 'values': ['mv1', 'zv', 'zv']}`	`{'clocks': [1, 1, 1], 'values': ['mv1', 'zv', 'zv']}`	Failed

SHA-256 / 62e1da3e2b6b779609df88a1c7bd07d5cf145af7139417fa29b56ba6c7af0676

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(events, replicas):
    clock = {r: 0 for r in replicas}
    reg = {r: [None, 0, ''] for r in replicas}
    for ev in events:
        if ev[0] == 'set':
            r = ev[1]
            clock[r] += 1
            reg[r] = [ev[2], clock[r], r]
        else:
            s, d = ev[1], ev[2]
            inc = reg[s]
            clock[d] = inc[1]
            if (inc[1], inc[2]) > (reg[d][1], reg[d][2]):
                reg[d] = list(inc)
    return {'values': [reg[r][0] for r in replicas], 'clocks': [clock[r] for r in replicas]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x1'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q1'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s0', 's0', 's0'], 'clocks': [2, 2, 2]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 4, 4]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv1'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv1', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    2: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x2'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q2'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s1', 's1', 's1'], 'clocks': [3, 3, 3]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 5, 5]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv2'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv2', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    3: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x3'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q3'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['set', 'a', 's2'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s2', 's2', 's2'], 'clocks': [4, 4, 4]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['set', 'b', 'b4'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 6, 6]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv3'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv3', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    4: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x4'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q4'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['set', 'a', 's2'], ['set', 'a', 's3'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s3', 's3', 's3'], 'clocks': [5, 5, 5]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['set', 'b', 'b4'], ['set', 'b', 'b5'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 7, 7]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv4'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv4', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    5: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x5'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q5'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['set', 'a', 's2'], ['set', 'a', 's3'], ['set', 'a', 's4'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s4', 's4', 's4'], 'clocks': [6, 6, 6]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['set', 'b', 'b4'], ['set', 'b', 'b5'], ['set', 'b', 'b6'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 8, 8]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv5'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv5', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
later local write after receive wins	`{'clocks': [3, 3, 0], 'values': ['b1', 'b1', None]}`	`{'clocks': [3, 3, 0], 'values': ['b1', 'b1', None]}`	Passed
equal stamps break toward larger replica id	`{'clocks': [1, 1, 0], 'values': ['y', 'y', None]}`	`{'clocks': [1, 1, 0], 'values': ['y', 'y', None]}`	Passed
equal stamps other direction	`{'clocks': [1, 0, 1], 'values': ['p', None, 'p']}`	`{'clocks': [1, 0, 1], 'values': ['p', None, 'p']}`	Passed
older state is ignored	`{'clocks': [2, 2, 1], 'values': ['s0', 's0', 's0']}`	`{'clocks': [2, 2, 2], 'values': ['s0', 's0', 's0']}`	Failed
ring gossip converges	`{'clocks': [1, 1, 1], 'values': ['C', 'C', 'C']}`	`{'clocks': [1, 1, 1], 'values': ['C', 'C', 'C']}`	Passed
empty send	`{'clocks': [0, 0, 0], 'values': [None, None, None]}`	`{'clocks': [0, 0, 0], 'values': [None, None, None]}`	Passed
receiving from an empty replica keeps the clock	`{'clocks': [0, 1, 1], 'values': [None, 'last', 'last']}`	`{'clocks': [0, 4, 4], 'values': [None, 'last', 'last']}`	Failed
adopted value keeps its writer identity	`{'clocks': [1, 1, 1], 'values': ['mv1', 'zv', 'zv']}`	`{'clocks': [1, 1, 1], 'values': ['mv1', 'zv', 'zv']}`	Passed

SHA-256 / b4404553e994a6af35d4cec7dac6678a96ef8c84dcd1b7892c7de3ae93ef7a93

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(events, replicas):
    clock = {r: 0 for r in replicas}
    reg = {r: [None, 0, ''] for r in replicas}
    for ev in events:
        if ev[0] == 'set':
            r = ev[1]
            clock[r] += 1
            reg[r] = [ev[2], clock[r], r]
        else:
            s, d = ev[1], ev[2]
            inc = reg[s]
            clock[d] = max(clock[d], inc[1])
            if (inc[1], inc[2]) > (reg[d][1], reg[d][2]):
                reg[d] = list(inc)
    return {'values': [reg[r][0] for r in replicas], 'clocks': [clock[r] for r in replicas]}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
    1: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x1'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q1'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s0', 's0', 's0'], 'clocks': [2, 2, 2]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 4, 4]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv1'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv1', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    2: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x2'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q2'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s1', 's1', 's1'], 'clocks': [3, 3, 3]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 5, 5]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv2'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv2', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    3: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x3'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q3'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['set', 'a', 's2'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s2', 's2', 's2'], 'clocks': [4, 4, 4]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['set', 'b', 'b4'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 6, 6]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv3'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv3', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    4: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x4'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q4'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['set', 'a', 's2'], ['set', 'a', 's3'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s3', 's3', 's3'], 'clocks': [5, 5, 5]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['set', 'b', 'b4'], ['set', 'b', 'b5'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 7, 7]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv4'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv4', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
    5: [('later local write after receive wins', [[['set', 'a', 'a1'], ['set', 'a', 'a2'], ['send', 'a', 'b'], ['set', 'b', 'b1'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['b1', 'b1', None], 'clocks': [3, 3, 0]}), ('equal stamps break toward larger replica id', [[['set', 'a', 'x5'], ['set', 'b', 'y'], ['send', 'a', 'b'], ['send', 'b', 'a']], ['a', 'b', 'c']], {'values': ['y', 'y', None], 'clocks': [1, 1, 0]}), ('equal stamps other direction', [[['set', 'c', 'p'], ['set', 'a', 'q5'], ['send', 'c', 'a'], ['send', 'a', 'c']], ['a', 'b', 'c']], {'values': ['p', None, 'p'], 'clocks': [1, 0, 1]}), ('older state is ignored', [[['set', 'a', 'old'], ['set', 'a', 's0'], ['set', 'a', 's1'], ['set', 'a', 's2'], ['set', 'a', 's3'], ['set', 'a', 's4'], ['send', 'a', 'c'], ['set', 'b', 'bb'], ['send', 'b', 'c'], ['send', 'c', 'b']], ['a', 'b', 'c']], {'values': ['s4', 's4', 's4'], 'clocks': [6, 6, 6]}), ('ring gossip converges', [[['set', 'a', 'A'], ['set', 'b', 'B'], ['set', 'c', 'C'], ['send', 'a', 'b'], ['send', 'b', 'c'], ['send', 'c', 'a'], ['send', 'a', 'b']], ['a', 'b', 'c']], {'values': ['C', 'C', 'C'], 'clocks': [1, 1, 1]}), ('empty send', [[['send', 'a', 'b']], ['a', 'b', 'c']], {'values': [None, None, None], 'clocks': [0, 0, 0]}), ('receiving from an empty replica keeps the clock', [[['set', 'b', 'b0'], ['set', 'b', 'b1'], ['set', 'b', 'b2'], ['set', 'b', 'b3'], ['set', 'b', 'b4'], ['set', 'b', 'b5'], ['set', 'b', 'b6'], ['send', 'a', 'b'], ['set', 'b', 'last'], ['send', 'b', 'c']], ['a', 'b', 'c']], {'values': [None, 'last', 'last'], 'clocks': [0, 8, 8]}), ('adopted value keeps its writer identity', [[['set', 'z', 'zv'], ['send', 'z', 'a'], ['set', 'm', 'mv5'], ['send', 'm', 'a'], ['send', 'a', 'z']], ['m', 'z', 'a']], {'values': ['mv5', 'zv', 'zv'], 'clocks': [1, 1, 1]})],
}[N]
for label, args, expected in cases:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
later local write after receive wins	`{'clocks': [3, 3, 0], 'values': ['b1', 'b1', None]}`	`{'clocks': [3, 3, 0], 'values': ['b1', 'b1', None]}`	Passed
equal stamps break toward larger replica id	`{'clocks': [1, 1, 0], 'values': ['y', 'y', None]}`	`{'clocks': [1, 1, 0], 'values': ['y', 'y', None]}`	Passed
equal stamps other direction	`{'clocks': [1, 0, 1], 'values': ['p', None, 'p']}`	`{'clocks': [1, 0, 1], 'values': ['p', None, 'p']}`	Passed
older state is ignored	`{'clocks': [2, 2, 2], 'values': ['s0', 's0', 's0']}`	`{'clocks': [2, 2, 2], 'values': ['s0', 's0', 's0']}`	Passed
ring gossip converges	`{'clocks': [1, 1, 1], 'values': ['C', 'C', 'C']}`	`{'clocks': [1, 1, 1], 'values': ['C', 'C', 'C']}`	Passed
empty send	`{'clocks': [0, 0, 0], 'values': [None, None, None]}`	`{'clocks': [0, 0, 0], 'values': [None, None, None]}`	Passed
receiving from an empty replica keeps the clock	`{'clocks': [0, 4, 4], 'values': [None, 'last', 'last']}`	`{'clocks': [0, 4, 4], 'values': [None, 'last', 'last']}`	Passed
adopted value keeps its writer identity	`{'clocks': [1, 1, 1], 'values': ['mv1', 'zv', 'zv']}`	`{'clocks': [1, 1, 1], 'values': ['mv1', 'zv', 'zv']}`	Passed

SHA-256 / bf405250f968c1bcc4c251b7e2636839565da6d46cdd77d65e43d7d06d7017ed

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

Case digest / 04567f2aa74e6b9314aba169bad4def303e162234b438d7bd2e33961c376e1b4