FA-74926 / CRDT convergence / Open access
LWW element set with add bias: a delayed local add lowers the stored timestamp · case 01
An old add delivered late makes a newer element lose to an intermediate remove.
ROOT CAUSE
Local operations overwrite the stored timestamp even when the incoming timestamp is older.
VERIFIED REPAIR
Record a local timestamp only when it exceeds the stored one.
Unsuccessful approach: Keeping the first recorded timestamp ignores a later, newer add for the same element.
Case contract
Each replica keeps add and remove timestamp maps. ["add"|"rem", r, e, t] records t when it exceeds the stored timestamp. ["merge", s, d] folds both maps of s into d by maximum. An element is a member when it has an add timestamp that is greater than or equal to its remove timestamp (ties favour add). Return sorted members per replica.
Why this case matters
LWW element sets resolve add/remove races by timestamp and need a deterministic tie bias.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ops, replicas):
A = {r: {} for r in replicas}
R = {r: {} for r in replicas}
for op in ops:
if op[0] == 'merge':
s, d = op[1], op[2]
for src, dst in ((A[s], A[d]), (R[s], R[d])):
for e, t in src.items():
if t > dst.get(e, -1):
dst[e] = t
else:
kind, r, e, t = op
table = A[r] if kind == 'add' else R[r]
table[e] = t
def members(r):
return sorted(e for e, t in A[r].items() if t >= R[r].get(e, -1))
return [members(r) for r in replicas]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 1], ['rem', 'a', 'x', 1]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 2], ['rem', 'b', 'x', 2], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 6], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 3], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 5], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 5], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 1], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 2], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
2: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 2], ['rem', 'a', 'x', 2]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 3], ['rem', 'b', 'x', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 7], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 4], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 6], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 6], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 2], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 3], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
3: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 3], ['rem', 'a', 'x', 3]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 4], ['rem', 'b', 'x', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 8], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 5], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 7], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 6], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 7], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 3], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 4], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
4: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 4], ['rem', 'a', 'x', 4]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 5], ['rem', 'b', 'x', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 9], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 6], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 8], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 7], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 8], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 4], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 5], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
5: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 5], ['rem', 'a', 'x', 5]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 6], ['rem', 'b', 'x', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 6], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 10], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 7], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 9], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 8], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 9], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 5], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 6], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
}[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 |
|---|---|---|---|
| add and remove at the same timestamp keep the element | [['x'], []] | [['x'], []] | Passed |
| tie arriving through merge keeps the element | [['x'], ['x']] | [['x'], ['x']] | Passed |
| newer remove hides the element everywhere | [[], []] | [[], []] | Passed |
| older merged add does not lower the timestamp | [['z'], []] | [['z'], []] | Passed |
| out-of-order local add keeps the maximum | [[], []] | [['w'], []] | Failed |
| first add seen does not pin the timestamp | [['q'], ['q']] | [['q'], ['q']] | Passed |
| later local add supersedes an earlier one | [['u'], []] | [['u'], []] | Passed |
| merge only pushes from source | [['k'], ['k', 'm']] | [['k'], ['k', 'm']] | Passed |
| removes propagate without adds | [[], []] | [[], []] | Passed |
SHA-256 / 48a59c8ed19f2d9ecaf399abf1707cff957baa4b3f32f71201f43d7b8c533de2
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ops, replicas):
A = {r: {} for r in replicas}
R = {r: {} for r in replicas}
for op in ops:
if op[0] == 'merge':
s, d = op[1], op[2]
for src, dst in ((A[s], A[d]), (R[s], R[d])):
for e, t in src.items():
if t > dst.get(e, -1):
dst[e] = t
else:
kind, r, e, t = op
table = A[r] if kind == 'add' else R[r]
if e not in table:
table[e] = t
def members(r):
return sorted(e for e, t in A[r].items() if t >= R[r].get(e, -1))
return [members(r) for r in replicas]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 1], ['rem', 'a', 'x', 1]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 2], ['rem', 'b', 'x', 2], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 6], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 3], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 5], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 5], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 1], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 2], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
2: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 2], ['rem', 'a', 'x', 2]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 3], ['rem', 'b', 'x', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 7], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 4], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 6], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 6], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 2], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 3], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
3: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 3], ['rem', 'a', 'x', 3]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 4], ['rem', 'b', 'x', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 8], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 5], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 7], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 6], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 7], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 3], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 4], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
4: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 4], ['rem', 'a', 'x', 4]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 5], ['rem', 'b', 'x', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 9], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 6], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 8], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 7], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 8], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 4], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 5], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
5: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 5], ['rem', 'a', 'x', 5]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 6], ['rem', 'b', 'x', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 6], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 10], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 7], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 9], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 8], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 9], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 5], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 6], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
}[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 |
|---|---|---|---|
| add and remove at the same timestamp keep the element | [['x'], []] | [['x'], []] | Passed |
| tie arriving through merge keeps the element | [['x'], ['x']] | [['x'], ['x']] | Passed |
| newer remove hides the element everywhere | [[], []] | [[], []] | Passed |
| older merged add does not lower the timestamp | [['z'], []] | [['z'], []] | Passed |
| out-of-order local add keeps the maximum | [['w'], []] | [['w'], []] | Passed |
| first add seen does not pin the timestamp | [['q'], ['q']] | [['q'], ['q']] | Passed |
| later local add supersedes an earlier one | [[], []] | [['u'], []] | Failed |
| merge only pushes from source | [['k'], ['k', 'm']] | [['k'], ['k', 'm']] | Passed |
| removes propagate without adds | [[], []] | [[], []] | Passed |
SHA-256 / c6fbf042d7ef7243b707fbf2299156dc764cf04cf108cc321a025c3f10eaa18f
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ops, replicas):
A = {r: {} for r in replicas}
R = {r: {} for r in replicas}
for op in ops:
if op[0] == 'merge':
s, d = op[1], op[2]
for src, dst in ((A[s], A[d]), (R[s], R[d])):
for e, t in src.items():
if t > dst.get(e, -1):
dst[e] = t
else:
kind, r, e, t = op
table = A[r] if kind == 'add' else R[r]
if t > table.get(e, -1):
table[e] = t
def members(r):
return sorted(e for e, t in A[r].items() if t >= R[r].get(e, -1))
return [members(r) for r in replicas]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 1], ['rem', 'a', 'x', 1]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 2], ['rem', 'b', 'x', 2], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 6], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 3], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 5], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 5], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 1], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 2], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
2: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 2], ['rem', 'a', 'x', 2]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 3], ['rem', 'b', 'x', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 7], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 4], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 6], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 6], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 2], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 3], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
3: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 3], ['rem', 'a', 'x', 3]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 4], ['rem', 'b', 'x', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 8], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 5], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 7], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 6], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 7], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 3], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 4], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
4: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 4], ['rem', 'a', 'x', 4]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 5], ['rem', 'b', 'x', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 9], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 6], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 8], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 7], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 8], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 4], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 5], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
5: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 5], ['rem', 'a', 'x', 5]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 6], ['rem', 'b', 'x', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 6], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 10], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 7], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 9], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 8], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 9], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 5], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 6], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
}[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 |
|---|---|---|---|
| add and remove at the same timestamp keep the element | [['x'], []] | [['x'], []] | Passed |
| tie arriving through merge keeps the element | [['x'], ['x']] | [['x'], ['x']] | Passed |
| newer remove hides the element everywhere | [[], []] | [[], []] | Passed |
| older merged add does not lower the timestamp | [['z'], []] | [['z'], []] | Passed |
| out-of-order local add keeps the maximum | [['w'], []] | [['w'], []] | Passed |
| first add seen does not pin the timestamp | [['q'], ['q']] | [['q'], ['q']] | Passed |
| later local add supersedes an earlier one | [['u'], []] | [['u'], []] | Passed |
| merge only pushes from source | [['k'], ['k', 'm']] | [['k'], ['k', 'm']] | Passed |
| removes propagate without adds | [[], []] | [[], []] | Passed |
SHA-256 / dfc95ba445a038b2aabfdf160543c263f7233e9bccc8bd7cbab3bb6c5cc468ec
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:01.145506+00:00.
Case digest / c8f16c53f448fc77693d5116bf21708dcf9a7a6d6c39eb069d1629c08a6b4993