FA-74901 / CRDT convergence / Open access
LWW register with Lamport stamps: an adopted value is re-stamped as a local write · case 01
After relaying a value, a replica makes it win or lose ties it should not.
ROOT CAUSE
The receiver re-stamps the adopted value with its own clock and identity.
VERIFIED REPAIR
Adopt the incoming register together with its original clock and writer.
Unsuccessful approach: Keeping the incoming clock but substituting the local writer id still changes tie-breaks downstream.
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]
clock[d] = max(clock[d], inc[1])
if (inc[1], inc[2]) > (reg[d][1], reg[d][2]):
reg[d] = [inc[0], clock[d], d]
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', 'B', 'C']} | {'clocks': [1, 1, 1], 'values': ['C', 'C', 'C']} | Failed |
| 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', 'mv1']} | {'clocks': [1, 1, 1], 'values': ['mv1', 'zv', 'zv']} | Failed |
SHA-256 / 259f170bba8e53f6f3579d6d7ea452ab75b6ff0dfb4e22ecbf31e116c10bb37a
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] = max(clock[d], inc[1])
if (inc[1], inc[2]) > (reg[d][1], reg[d][2]):
reg[d] = [inc[0], inc[1], d]
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', 'B', 'C']} | {'clocks': [1, 1, 1], 'values': ['C', 'C', 'C']} | Failed |
| 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', 'mv1']} | {'clocks': [1, 1, 1], 'values': ['mv1', 'zv', 'zv']} | Failed |
SHA-256 / fa5e496207be15b1ce8a7da02ce42813f58bf94278a7c78b5039aa4ce84df4fa
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.957435+00:00.
Case digest / c714f060b20773999b1f166b832c65ed3182b4b7f69a4052f63945a6f17e2826