FA-75006 / CRDT convergence / Open access
Delta causal context join: cloud entries already covered by the vector are kept · case 01
The cloud grows without bound with dots the vector already summarizes.
ROOT CAUSE
Compaction never removes cloud entries at or below the vector entry.
VERIFIED REPAIR
Prune every cloud entry whose counter is at or below the vector entry.
Unsuccessful approach: Pruning only entries strictly below the vector keeps the entry equal to it.
Case contract
A state is {"dots": [[element, replica, n]], "vv": {replica: n}, "cloud": [[replica, n]]}. A context covers (r, n) when n <= vv[r] or [r, n] is in the cloud. Join keeps dots present in both states plus dots of one state not covered by the other's context; contexts join by vector maximum and cloud union, then the cloud is compacted: an entry equal to vv[r]+1 advances vv[r], entries at or below vv[r] are pruned. Return elements, dots, vector and cloud, all sorted.
Why this case matters
Delta-state add-wins sets rely on causal contexts to tell removals from unseen additions.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(a, b):
def covered(c, rep, n):
return n <= c['vv'].get(rep, 0) or [rep, n] in c['cloud']
da = {tuple(x) for x in a['dots']}
db = {tuple(x) for x in b['dots']}
dots = (da & db) | {x for x in da if not covered(b, x[1], x[2])} | {x for x in db if not covered(a, x[1], x[2])}
vv = dict(a['vv'])
for rep, n in b['vv'].items():
vv[rep] = max(vv.get(rep, 0), n)
cloud = {tuple(x) for x in a['cloud']} | {tuple(x) for x in b['cloud']}
changed = True
while changed:
changed = False
for rep, n in sorted(cloud):
if n == vv.get(rep, 0) + 1:
vv[rep] = n
cloud.discard((rep, n))
changed = True
return {'elements': sorted({x[0] for x in dots}), 'dots': sorted([list(x) for x in dots]), 'vv': sorted([k, v] for k, v in vv.items()), 'cloud': sorted([list(x) for x in cloud])}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 1]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 3]], 'vv': {'c': 1}, 'cloud': [['c', 3]]}, {'dots': [['w', 'c', 2]], 'vv': {'c': 1}, 'cloud': [['c', 2]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 2], ['z', 'c', 3]], 'vv': [['c', 3]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 5]], 'vv': {}, 'cloud': [['a', 5]]}], {'elements': ['q'], 'dots': [['q', 'a', 5]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 5]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 1]], 'vv': {'a': 2, 'b': 1}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['r'], 'dots': [['r', 'a', 4]], 'vv': [['a', 4], ['b', 1]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 3}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 4]]}], {'elements': [], 'dots': [], 'vv': [['a', 4]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 1], ['k', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 1]], 'vv': [['a', 1], ['b', 1]], 'cloud': []})],
2: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [], 'vv': {'a': 2}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 2]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 4]], 'vv': {'c': 2}, 'cloud': [['c', 4]]}, {'dots': [['w', 'c', 3]], 'vv': {'c': 2}, 'cloud': [['c', 3]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 3], ['z', 'c', 4]], 'vv': [['c', 4]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 6]], 'vv': {}, 'cloud': [['a', 6]]}], {'elements': ['q'], 'dots': [['q', 'a', 6]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 6]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 2]], 'vv': {'a': 2, 'b': 2}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 2], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 2]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 4}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 5]]}], {'elements': [], 'dots': [], 'vv': [['a', 5]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 2], ['k', 'b', 1]], 'vv': {'a': 2, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 2]], 'vv': [['a', 2], ['b', 1]], 'cloud': []})],
3: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 3]], 'vv': {'a': 3}, 'cloud': []}, {'dots': [], 'vv': {'a': 3}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 3]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 5]], 'vv': {'c': 3}, 'cloud': [['c', 5]]}, {'dots': [['w', 'c', 4]], 'vv': {'c': 3}, 'cloud': [['c', 4]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 4], ['z', 'c', 5]], 'vv': [['c', 5]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 7]], 'vv': {}, 'cloud': [['a', 7]]}], {'elements': ['q'], 'dots': [['q', 'a', 7]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 7]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 3]], 'vv': {'a': 2, 'b': 3}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 3], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 3]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 5}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 6]]}], {'elements': [], 'dots': [], 'vv': [['a', 6]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 3], ['k', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 3]], 'vv': [['a', 3], ['b', 1]], 'cloud': []})],
4: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 4]], 'vv': {'a': 4}, 'cloud': []}, {'dots': [], 'vv': {'a': 4}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 4]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 6]], 'vv': {'c': 4}, 'cloud': [['c', 6]]}, {'dots': [['w', 'c', 5]], 'vv': {'c': 4}, 'cloud': [['c', 5]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 5], ['z', 'c', 6]], 'vv': [['c', 6]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 8]], 'vv': {}, 'cloud': [['a', 8]]}], {'elements': ['q'], 'dots': [['q', 'a', 8]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 8]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 4]], 'vv': {'a': 2, 'b': 4}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 4], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 4]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 6}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 7]]}], {'elements': [], 'dots': [], 'vv': [['a', 7]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 4], ['k', 'b', 1]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 4]], 'vv': [['a', 4], ['b', 1]], 'cloud': []})],
5: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 5]], 'vv': {'a': 5}, 'cloud': []}, {'dots': [], 'vv': {'a': 5}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 5]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 7]], 'vv': {'c': 5}, 'cloud': [['c', 7]]}, {'dots': [['w', 'c', 6]], 'vv': {'c': 5}, 'cloud': [['c', 6]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 6], ['z', 'c', 7]], 'vv': [['c', 7]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 9]], 'vv': {}, 'cloud': [['a', 9]]}], {'elements': ['q'], 'dots': [['q', 'a', 9]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 9]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 5]], 'vv': {'a': 2, 'b': 5}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 5], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 5]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 7}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 8]]}], {'elements': [], 'dots': [], 'vv': [['a', 8]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 5], ['k', 'b', 1]], 'vv': {'a': 5, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 5]], 'vv': [['a', 5], ['b', 1]], 'cloud': []})],
}[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 |
|---|---|---|---|
| dot unseen by the peer survives | {'cloud': [], 'dots': [['x', 'a', 1]], 'elements': ['x'], 'vv': [['a', 1]]} | {'cloud': [], 'dots': [['x', 'a', 1]], 'elements': ['x'], 'vv': [['a', 1]]} | Passed |
| dot removed by the peer is dropped | {'cloud': [], 'dots': [['y', 'a', 2]], 'elements': ['y'], 'vv': [['a', 2]]} | {'cloud': [], 'dots': [['y', 'a', 2]], 'elements': ['y'], 'vv': [['a', 2]]} | Passed |
| dot covered only by the peer cloud is dropped | {'cloud': [['a', 3]], 'dots': [['y', 'b', 1]], 'elements': ['y'], 'vv': [['a', 3], ['b', 1]]} | {'cloud': [], 'dots': [['y', 'b', 1]], 'elements': ['y'], 'vv': [['a', 3], ['b', 1]]} | Failed |
| dot at the vector boundary is covered | {'cloud': [], 'dots': [], 'elements': [], 'vv': [['a', 1]]} | {'cloud': [], 'dots': [], 'elements': [], 'vv': [['a', 1]]} | Passed |
| cloud compacts into the vector | {'cloud': [], 'dots': [['w', 'c', 2], ['z', 'c', 3]], 'elements': ['w', 'z'], 'vv': [['c', 3]]} | {'cloud': [], 'dots': [['w', 'c', 2], ['z', 'c', 3]], 'elements': ['w', 'z'], 'vv': [['c', 3]]} | Passed |
| gaps stay in the cloud | {'cloud': [['a', 3], ['a', 5]], 'dots': [['q', 'a', 5]], 'elements': ['q'], 'vv': [['a', 1]]} | {'cloud': [['a', 3], ['a', 5]], 'dots': [['q', 'a', 5]], 'elements': ['q'], 'vv': [['a', 1]]} | Passed |
| vectors join by maximum | {'cloud': [], 'dots': [['r', 'a', 4]], 'elements': ['r'], 'vv': [['a', 4], ['b', 1]]} | {'cloud': [], 'dots': [['r', 'a', 4]], 'elements': ['r'], 'vv': [['a', 4], ['b', 1]]} | Passed |
| cloud entries for a fresh replica compact from zero | {'cloud': [], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'elements': ['m'], 'vv': [['d', 2]]} | {'cloud': [], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'elements': ['m'], 'vv': [['d', 2]]} | Passed |
| cloud entries already under the vector are pruned | {'cloud': [['a', 2]], 'dots': [], 'elements': [], 'vv': [['a', 4]]} | {'cloud': [], 'dots': [], 'elements': [], 'vv': [['a', 4]]} | Failed |
| peer-only dot unseen locally survives | {'cloud': [], 'dots': [['k', 'a', 1]], 'elements': ['k'], 'vv': [['a', 1], ['b', 1]]} | {'cloud': [], 'dots': [['k', 'a', 1]], 'elements': ['k'], 'vv': [['a', 1], ['b', 1]]} | Passed |
SHA-256 / c01e06ba79d466c7c67aad62417fc2ffd9f93c9c4c2727b258cb74d7cbeabbcf
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(a, b):
def covered(c, rep, n):
return n <= c['vv'].get(rep, 0) or [rep, n] in c['cloud']
da = {tuple(x) for x in a['dots']}
db = {tuple(x) for x in b['dots']}
dots = (da & db) | {x for x in da if not covered(b, x[1], x[2])} | {x for x in db if not covered(a, x[1], x[2])}
vv = dict(a['vv'])
for rep, n in b['vv'].items():
vv[rep] = max(vv.get(rep, 0), n)
cloud = {tuple(x) for x in a['cloud']} | {tuple(x) for x in b['cloud']}
changed = True
while changed:
changed = False
for rep, n in sorted(cloud):
if n == vv.get(rep, 0) + 1:
vv[rep] = n
cloud.discard((rep, n))
changed = True
elif n < vv.get(rep, 0):
cloud.discard((rep, n))
changed = True
return {'elements': sorted({x[0] for x in dots}), 'dots': sorted([list(x) for x in dots]), 'vv': sorted([k, v] for k, v in vv.items()), 'cloud': sorted([list(x) for x in cloud])}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 1]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 3]], 'vv': {'c': 1}, 'cloud': [['c', 3]]}, {'dots': [['w', 'c', 2]], 'vv': {'c': 1}, 'cloud': [['c', 2]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 2], ['z', 'c', 3]], 'vv': [['c', 3]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 5]], 'vv': {}, 'cloud': [['a', 5]]}], {'elements': ['q'], 'dots': [['q', 'a', 5]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 5]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 1]], 'vv': {'a': 2, 'b': 1}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['r'], 'dots': [['r', 'a', 4]], 'vv': [['a', 4], ['b', 1]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 3}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 4]]}], {'elements': [], 'dots': [], 'vv': [['a', 4]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 1], ['k', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 1]], 'vv': [['a', 1], ['b', 1]], 'cloud': []})],
2: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [], 'vv': {'a': 2}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 2]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 4]], 'vv': {'c': 2}, 'cloud': [['c', 4]]}, {'dots': [['w', 'c', 3]], 'vv': {'c': 2}, 'cloud': [['c', 3]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 3], ['z', 'c', 4]], 'vv': [['c', 4]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 6]], 'vv': {}, 'cloud': [['a', 6]]}], {'elements': ['q'], 'dots': [['q', 'a', 6]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 6]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 2]], 'vv': {'a': 2, 'b': 2}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 2], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 2]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 4}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 5]]}], {'elements': [], 'dots': [], 'vv': [['a', 5]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 2], ['k', 'b', 1]], 'vv': {'a': 2, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 2]], 'vv': [['a', 2], ['b', 1]], 'cloud': []})],
3: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 3]], 'vv': {'a': 3}, 'cloud': []}, {'dots': [], 'vv': {'a': 3}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 3]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 5]], 'vv': {'c': 3}, 'cloud': [['c', 5]]}, {'dots': [['w', 'c', 4]], 'vv': {'c': 3}, 'cloud': [['c', 4]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 4], ['z', 'c', 5]], 'vv': [['c', 5]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 7]], 'vv': {}, 'cloud': [['a', 7]]}], {'elements': ['q'], 'dots': [['q', 'a', 7]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 7]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 3]], 'vv': {'a': 2, 'b': 3}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 3], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 3]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 5}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 6]]}], {'elements': [], 'dots': [], 'vv': [['a', 6]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 3], ['k', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 3]], 'vv': [['a', 3], ['b', 1]], 'cloud': []})],
4: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 4]], 'vv': {'a': 4}, 'cloud': []}, {'dots': [], 'vv': {'a': 4}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 4]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 6]], 'vv': {'c': 4}, 'cloud': [['c', 6]]}, {'dots': [['w', 'c', 5]], 'vv': {'c': 4}, 'cloud': [['c', 5]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 5], ['z', 'c', 6]], 'vv': [['c', 6]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 8]], 'vv': {}, 'cloud': [['a', 8]]}], {'elements': ['q'], 'dots': [['q', 'a', 8]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 8]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 4]], 'vv': {'a': 2, 'b': 4}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 4], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 4]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 6}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 7]]}], {'elements': [], 'dots': [], 'vv': [['a', 7]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 4], ['k', 'b', 1]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 4]], 'vv': [['a', 4], ['b', 1]], 'cloud': []})],
5: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 5]], 'vv': {'a': 5}, 'cloud': []}, {'dots': [], 'vv': {'a': 5}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 5]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 7]], 'vv': {'c': 5}, 'cloud': [['c', 7]]}, {'dots': [['w', 'c', 6]], 'vv': {'c': 5}, 'cloud': [['c', 6]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 6], ['z', 'c', 7]], 'vv': [['c', 7]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 9]], 'vv': {}, 'cloud': [['a', 9]]}], {'elements': ['q'], 'dots': [['q', 'a', 9]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 9]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 5]], 'vv': {'a': 2, 'b': 5}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 5], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 5]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 7}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 8]]}], {'elements': [], 'dots': [], 'vv': [['a', 8]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 5], ['k', 'b', 1]], 'vv': {'a': 5, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 5]], 'vv': [['a', 5], ['b', 1]], 'cloud': []})],
}[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 |
|---|---|---|---|
| dot unseen by the peer survives | {'cloud': [], 'dots': [['x', 'a', 1]], 'elements': ['x'], 'vv': [['a', 1]]} | {'cloud': [], 'dots': [['x', 'a', 1]], 'elements': ['x'], 'vv': [['a', 1]]} | Passed |
| dot removed by the peer is dropped | {'cloud': [], 'dots': [['y', 'a', 2]], 'elements': ['y'], 'vv': [['a', 2]]} | {'cloud': [], 'dots': [['y', 'a', 2]], 'elements': ['y'], 'vv': [['a', 2]]} | Passed |
| dot covered only by the peer cloud is dropped | {'cloud': [['a', 3]], 'dots': [['y', 'b', 1]], 'elements': ['y'], 'vv': [['a', 3], ['b', 1]]} | {'cloud': [], 'dots': [['y', 'b', 1]], 'elements': ['y'], 'vv': [['a', 3], ['b', 1]]} | Failed |
| dot at the vector boundary is covered | {'cloud': [], 'dots': [], 'elements': [], 'vv': [['a', 1]]} | {'cloud': [], 'dots': [], 'elements': [], 'vv': [['a', 1]]} | Passed |
| cloud compacts into the vector | {'cloud': [], 'dots': [['w', 'c', 2], ['z', 'c', 3]], 'elements': ['w', 'z'], 'vv': [['c', 3]]} | {'cloud': [], 'dots': [['w', 'c', 2], ['z', 'c', 3]], 'elements': ['w', 'z'], 'vv': [['c', 3]]} | Passed |
| gaps stay in the cloud | {'cloud': [['a', 3], ['a', 5]], 'dots': [['q', 'a', 5]], 'elements': ['q'], 'vv': [['a', 1]]} | {'cloud': [['a', 3], ['a', 5]], 'dots': [['q', 'a', 5]], 'elements': ['q'], 'vv': [['a', 1]]} | Passed |
| vectors join by maximum | {'cloud': [], 'dots': [['r', 'a', 4]], 'elements': ['r'], 'vv': [['a', 4], ['b', 1]]} | {'cloud': [], 'dots': [['r', 'a', 4]], 'elements': ['r'], 'vv': [['a', 4], ['b', 1]]} | Passed |
| cloud entries for a fresh replica compact from zero | {'cloud': [], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'elements': ['m'], 'vv': [['d', 2]]} | {'cloud': [], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'elements': ['m'], 'vv': [['d', 2]]} | Passed |
| cloud entries already under the vector are pruned | {'cloud': [], 'dots': [], 'elements': [], 'vv': [['a', 4]]} | {'cloud': [], 'dots': [], 'elements': [], 'vv': [['a', 4]]} | Passed |
| peer-only dot unseen locally survives | {'cloud': [], 'dots': [['k', 'a', 1]], 'elements': ['k'], 'vv': [['a', 1], ['b', 1]]} | {'cloud': [], 'dots': [['k', 'a', 1]], 'elements': ['k'], 'vv': [['a', 1], ['b', 1]]} | Passed |
SHA-256 / f5a592039adba888f4343f56cf5437a4cc1999a4199bfb7e06cdf06c540958b6
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(a, b):
def covered(c, rep, n):
return n <= c['vv'].get(rep, 0) or [rep, n] in c['cloud']
da = {tuple(x) for x in a['dots']}
db = {tuple(x) for x in b['dots']}
dots = (da & db) | {x for x in da if not covered(b, x[1], x[2])} | {x for x in db if not covered(a, x[1], x[2])}
vv = dict(a['vv'])
for rep, n in b['vv'].items():
vv[rep] = max(vv.get(rep, 0), n)
cloud = {tuple(x) for x in a['cloud']} | {tuple(x) for x in b['cloud']}
changed = True
while changed:
changed = False
for rep, n in sorted(cloud):
if n == vv.get(rep, 0) + 1:
vv[rep] = n
cloud.discard((rep, n))
changed = True
elif n <= vv.get(rep, 0):
cloud.discard((rep, n))
changed = True
return {'elements': sorted({x[0] for x in dots}), 'dots': sorted([list(x) for x in dots]), 'vv': sorted([k, v] for k, v in vv.items()), 'cloud': sorted([list(x) for x in cloud])}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 1]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 3]], 'vv': {'c': 1}, 'cloud': [['c', 3]]}, {'dots': [['w', 'c', 2]], 'vv': {'c': 1}, 'cloud': [['c', 2]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 2], ['z', 'c', 3]], 'vv': [['c', 3]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 5]], 'vv': {}, 'cloud': [['a', 5]]}], {'elements': ['q'], 'dots': [['q', 'a', 5]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 5]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 1]], 'vv': {'a': 2, 'b': 1}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['r'], 'dots': [['r', 'a', 4]], 'vv': [['a', 4], ['b', 1]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 3}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 4]]}], {'elements': [], 'dots': [], 'vv': [['a', 4]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 1], ['k', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 1]], 'vv': [['a', 1], ['b', 1]], 'cloud': []})],
2: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [], 'vv': {'a': 2}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 2]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 4]], 'vv': {'c': 2}, 'cloud': [['c', 4]]}, {'dots': [['w', 'c', 3]], 'vv': {'c': 2}, 'cloud': [['c', 3]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 3], ['z', 'c', 4]], 'vv': [['c', 4]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 6]], 'vv': {}, 'cloud': [['a', 6]]}], {'elements': ['q'], 'dots': [['q', 'a', 6]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 6]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 2]], 'vv': {'a': 2, 'b': 2}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 2], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 2]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 4}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 5]]}], {'elements': [], 'dots': [], 'vv': [['a', 5]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 2], ['k', 'b', 1]], 'vv': {'a': 2, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 2]], 'vv': [['a', 2], ['b', 1]], 'cloud': []})],
3: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 3]], 'vv': {'a': 3}, 'cloud': []}, {'dots': [], 'vv': {'a': 3}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 3]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 5]], 'vv': {'c': 3}, 'cloud': [['c', 5]]}, {'dots': [['w', 'c', 4]], 'vv': {'c': 3}, 'cloud': [['c', 4]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 4], ['z', 'c', 5]], 'vv': [['c', 5]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 7]], 'vv': {}, 'cloud': [['a', 7]]}], {'elements': ['q'], 'dots': [['q', 'a', 7]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 7]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 3]], 'vv': {'a': 2, 'b': 3}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 3], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 3]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 5}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 6]]}], {'elements': [], 'dots': [], 'vv': [['a', 6]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 3], ['k', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 3]], 'vv': [['a', 3], ['b', 1]], 'cloud': []})],
4: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 4]], 'vv': {'a': 4}, 'cloud': []}, {'dots': [], 'vv': {'a': 4}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 4]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 6]], 'vv': {'c': 4}, 'cloud': [['c', 6]]}, {'dots': [['w', 'c', 5]], 'vv': {'c': 4}, 'cloud': [['c', 5]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 5], ['z', 'c', 6]], 'vv': [['c', 6]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 8]], 'vv': {}, 'cloud': [['a', 8]]}], {'elements': ['q'], 'dots': [['q', 'a', 8]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 8]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 4]], 'vv': {'a': 2, 'b': 4}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 4], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 4]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 6}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 7]]}], {'elements': [], 'dots': [], 'vv': [['a', 7]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 4], ['k', 'b', 1]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 4]], 'vv': [['a', 4], ['b', 1]], 'cloud': []})],
5: [('dot unseen by the peer survives', [{'dots': [['x', 'a', 1]], 'vv': {'a': 1}, 'cloud': []}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['x'], 'dots': [['x', 'a', 1]], 'vv': [['a', 1]], 'cloud': []}), ('dot removed by the peer is dropped', [{'dots': [['x', 'a', 1], ['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}, {'dots': [['y', 'a', 2]], 'vv': {'a': 2}, 'cloud': []}], {'elements': ['y'], 'dots': [['y', 'a', 2]], 'vv': [['a', 2]], 'cloud': []}), ('dot covered only by the peer cloud is dropped', [{'dots': [['x', 'a', 3], ['y', 'b', 1]], 'vv': {'a': 3, 'b': 1}, 'cloud': []}, {'dots': [['y', 'b', 1]], 'vv': {'a': 1, 'b': 1}, 'cloud': [['a', 3]]}], {'elements': ['y'], 'dots': [['y', 'b', 1]], 'vv': [['a', 3], ['b', 1]], 'cloud': []}), ('dot at the vector boundary is covered', [{'dots': [['x', 'a', 5]], 'vv': {'a': 5}, 'cloud': []}, {'dots': [], 'vv': {'a': 5}, 'cloud': []}], {'elements': [], 'dots': [], 'vv': [['a', 5]], 'cloud': []}), ('cloud compacts into the vector', [{'dots': [['z', 'c', 7]], 'vv': {'c': 5}, 'cloud': [['c', 7]]}, {'dots': [['w', 'c', 6]], 'vv': {'c': 5}, 'cloud': [['c', 6]]}], {'elements': ['w', 'z'], 'dots': [['w', 'c', 6], ['z', 'c', 7]], 'vv': [['c', 7]], 'cloud': []}), ('gaps stay in the cloud', [{'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 3]]}, {'dots': [['q', 'a', 9]], 'vv': {}, 'cloud': [['a', 9]]}], {'elements': ['q'], 'dots': [['q', 'a', 9]], 'vv': [['a', 1]], 'cloud': [['a', 3], ['a', 9]]}), ('vectors join by maximum', [{'dots': [['p', 'b', 5]], 'vv': {'a': 2, 'b': 5}, 'cloud': []}, {'dots': [['r', 'a', 4]], 'vv': {'a': 4, 'b': 1}, 'cloud': []}], {'elements': ['p', 'r'], 'dots': [['p', 'b', 5], ['r', 'a', 4]], 'vv': [['a', 4], ['b', 5]], 'cloud': []}), ('cloud entries for a fresh replica compact from zero', [{'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': {}, 'cloud': [['d', 1], ['d', 2]]}, {'dots': [], 'vv': {}, 'cloud': []}], {'elements': ['m'], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'vv': [['d', 2]], 'cloud': []}), ('cloud entries already under the vector are pruned', [{'dots': [], 'vv': {'a': 7}, 'cloud': []}, {'dots': [], 'vv': {'a': 1}, 'cloud': [['a', 2], ['a', 8]]}], {'elements': [], 'dots': [], 'vv': [['a', 8]], 'cloud': []}), ('peer-only dot unseen locally survives', [{'dots': [], 'vv': {'b': 1}, 'cloud': []}, {'dots': [['k', 'a', 5], ['k', 'b', 1]], 'vv': {'a': 5, 'b': 1}, 'cloud': []}], {'elements': ['k'], 'dots': [['k', 'a', 5]], 'vv': [['a', 5], ['b', 1]], 'cloud': []})],
}[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 |
|---|---|---|---|
| dot unseen by the peer survives | {'cloud': [], 'dots': [['x', 'a', 1]], 'elements': ['x'], 'vv': [['a', 1]]} | {'cloud': [], 'dots': [['x', 'a', 1]], 'elements': ['x'], 'vv': [['a', 1]]} | Passed |
| dot removed by the peer is dropped | {'cloud': [], 'dots': [['y', 'a', 2]], 'elements': ['y'], 'vv': [['a', 2]]} | {'cloud': [], 'dots': [['y', 'a', 2]], 'elements': ['y'], 'vv': [['a', 2]]} | Passed |
| dot covered only by the peer cloud is dropped | {'cloud': [], 'dots': [['y', 'b', 1]], 'elements': ['y'], 'vv': [['a', 3], ['b', 1]]} | {'cloud': [], 'dots': [['y', 'b', 1]], 'elements': ['y'], 'vv': [['a', 3], ['b', 1]]} | Passed |
| dot at the vector boundary is covered | {'cloud': [], 'dots': [], 'elements': [], 'vv': [['a', 1]]} | {'cloud': [], 'dots': [], 'elements': [], 'vv': [['a', 1]]} | Passed |
| cloud compacts into the vector | {'cloud': [], 'dots': [['w', 'c', 2], ['z', 'c', 3]], 'elements': ['w', 'z'], 'vv': [['c', 3]]} | {'cloud': [], 'dots': [['w', 'c', 2], ['z', 'c', 3]], 'elements': ['w', 'z'], 'vv': [['c', 3]]} | Passed |
| gaps stay in the cloud | {'cloud': [['a', 3], ['a', 5]], 'dots': [['q', 'a', 5]], 'elements': ['q'], 'vv': [['a', 1]]} | {'cloud': [['a', 3], ['a', 5]], 'dots': [['q', 'a', 5]], 'elements': ['q'], 'vv': [['a', 1]]} | Passed |
| vectors join by maximum | {'cloud': [], 'dots': [['r', 'a', 4]], 'elements': ['r'], 'vv': [['a', 4], ['b', 1]]} | {'cloud': [], 'dots': [['r', 'a', 4]], 'elements': ['r'], 'vv': [['a', 4], ['b', 1]]} | Passed |
| cloud entries for a fresh replica compact from zero | {'cloud': [], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'elements': ['m'], 'vv': [['d', 2]]} | {'cloud': [], 'dots': [['m', 'd', 1], ['m', 'd', 2]], 'elements': ['m'], 'vv': [['d', 2]]} | Passed |
| cloud entries already under the vector are pruned | {'cloud': [], 'dots': [], 'elements': [], 'vv': [['a', 4]]} | {'cloud': [], 'dots': [], 'elements': [], 'vv': [['a', 4]]} | Passed |
| peer-only dot unseen locally survives | {'cloud': [], 'dots': [['k', 'a', 1]], 'elements': ['k'], 'vv': [['a', 1], ['b', 1]]} | {'cloud': [], 'dots': [['k', 'a', 1]], 'elements': ['k'], 'vv': [['a', 1], ['b', 1]]} | Passed |
SHA-256 / 131b85b5338e7bf0799694cc70f58c7453da629e11cfbed9157920d1c184e82a
Verification & scope
A deterministic, bounded teaching model of one replicated data type with stipulated operation and merge rules; it is not a production CRDT library and makes no claim of conformance to any specific published design. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:49:02.152165+00:00.
Case digest / 716ce49269f1ceb24341f8ec2c61cca29d63ff8892989ba24551cea52cddfcde