FA-46591 / Bounded deques / Open access

Retirement receipt records the replacement handle generation · case 01

Retirement receipt records the replacement handle generation.

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

ROOT CAUSE

Retirement receipt records the replacement handle generation.

VERIFIED REPAIR

Restore the documented old generation invariant in slot-retirement.

Unsuccessful approach: The partial repair still applies the incorrect transition to an admitted boundary or multi-element case.

Case contract

Retire one occupied deque slot. Clear its payload, advance that slot generation, append its index to the free list, decrement live count and invalidate the retired [index,generation] handle.

Why this case matters

Controlled bounded deque implementation model with explicit storage and lifecycle observations.

1 / The failure

Exit 1

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

N = 1
observations = []
def solve(x):
    slots,index,generations,free,live=x
    storage=slots[:]
    storage[index]=None
    versions=generations[:]
    versions[index]+=1
    available=free+[index]
    count=live-1
    old_handle=[index,versions[index]]
    valid=False
    return [storage,versions,available,count,old_handle,valid,len(available)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,None],1,[2,4,0],[2],2]), {1: [[1, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2], 2: [[2, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2], 3: [[3, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2], 4: [[4, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2], 5: [[5, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2]}[N])
check('1', solve([[N],0,[N],[],1]), {1: [[None], [2], [0], 0, [0, 1], False, 1], 2: [[None], [3], [0], 0, [0, 2], False, 1], 3: [[None], [4], [0], 0, [0, 3], False, 1], 4: [[None], [5], [0], 0, [0, 4], False, 1], 5: [[None], [6], [0], 0, [0, 5], False, 1]}[N])
check('2', solve([[None,N,None,N+1],3,[1,2,3,4],[0,2],2]), {1: [[None, 1, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3], 2: [[None, 2, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3], 3: [[None, 3, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3], 4: [[None, 4, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3], 5: [[None, 5, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3]}[N])
check('3', solve([[N,N+1,N+2],0,[N,N+1,N+2],[],3]), {1: [[None, 2, 3], [2, 2, 3], [0], 2, [0, 1], False, 1], 2: [[None, 3, 4], [3, 3, 4], [0], 2, [0, 2], False, 1], 3: [[None, 4, 5], [4, 4, 5], [0], 2, [0, 3], False, 1], 4: [[None, 5, 6], [5, 5, 6], [0], 2, [0, 4], False, 1], 5: [[None, 6, 7], [6, 6, 7], [0], 2, [0, 5], False, 1]}[N])
check('4', solve([[N,None,N+1],2,[3,0,7],[1],2]), {1: [[1, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2], 2: [[2, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2], 3: [[3, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2], 4: [[4, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2], 5: [[5, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2]}[N])
check('5', solve([[None,N],1,[4,N],[0],1]), {1: [[None, None], [4, 2], [0, 1], 0, [1, 1], False, 2], 2: [[None, None], [4, 3], [0, 1], 0, [1, 2], False, 2], 3: [[None, None], [4, 4], [0, 1], 0, [1, 3], False, 2], 4: [[None, None], [4, 5], [0, 1], 0, [1, 4], False, 2], 5: [[None, None], [4, 6], [0, 1], 0, [1, 5], False, 2]}[N])
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
0	`[[1, None, None], [2, 5, 0], [2, 1], 1, [1, 5], False, 2]`	`[[1, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2]`	Failed
1	`[[None], [2], [0], 0, [0, 2], False, 1]`	`[[None], [2], [0], 0, [0, 1], False, 1]`	Failed
2	`[[None, 1, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 5], False, 3]`	`[[None, 1, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3]`	Failed
3	`[[None, 2, 3], [2, 2, 3], [0], 2, [0, 2], False, 1]`	`[[None, 2, 3], [2, 2, 3], [0], 2, [0, 1], False, 1]`	Failed
4	`[[1, None, None], [3, 0, 8], [1, 2], 1, [2, 8], False, 2]`	`[[1, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2]`	Failed
5	`[[None, None], [4, 2], [0, 1], 0, [1, 2], False, 2]`	`[[None, None], [4, 2], [0, 1], 0, [1, 1], False, 2]`	Failed

SHA-256 / 2cca71926b3af0b2aeaea13b8670acbe4ac9726b2970a4666206d3b3cebd5c70

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(x):
    slots,index,generations,free,live=x
    storage=slots[:]
    storage[index]=None
    versions=generations[:]
    versions[index]+=1
    available=free+[index]
    count=live-1
    old_handle=[index,generations[index] if live==1 else versions[index]]
    valid=False
    return [storage,versions,available,count,old_handle,valid,len(available)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,None],1,[2,4,0],[2],2]), {1: [[1, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2], 2: [[2, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2], 3: [[3, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2], 4: [[4, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2], 5: [[5, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2]}[N])
check('1', solve([[N],0,[N],[],1]), {1: [[None], [2], [0], 0, [0, 1], False, 1], 2: [[None], [3], [0], 0, [0, 2], False, 1], 3: [[None], [4], [0], 0, [0, 3], False, 1], 4: [[None], [5], [0], 0, [0, 4], False, 1], 5: [[None], [6], [0], 0, [0, 5], False, 1]}[N])
check('2', solve([[None,N,None,N+1],3,[1,2,3,4],[0,2],2]), {1: [[None, 1, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3], 2: [[None, 2, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3], 3: [[None, 3, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3], 4: [[None, 4, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3], 5: [[None, 5, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3]}[N])
check('3', solve([[N,N+1,N+2],0,[N,N+1,N+2],[],3]), {1: [[None, 2, 3], [2, 2, 3], [0], 2, [0, 1], False, 1], 2: [[None, 3, 4], [3, 3, 4], [0], 2, [0, 2], False, 1], 3: [[None, 4, 5], [4, 4, 5], [0], 2, [0, 3], False, 1], 4: [[None, 5, 6], [5, 5, 6], [0], 2, [0, 4], False, 1], 5: [[None, 6, 7], [6, 6, 7], [0], 2, [0, 5], False, 1]}[N])
check('4', solve([[N,None,N+1],2,[3,0,7],[1],2]), {1: [[1, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2], 2: [[2, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2], 3: [[3, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2], 4: [[4, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2], 5: [[5, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2]}[N])
check('5', solve([[None,N],1,[4,N],[0],1]), {1: [[None, None], [4, 2], [0, 1], 0, [1, 1], False, 2], 2: [[None, None], [4, 3], [0, 1], 0, [1, 2], False, 2], 3: [[None, None], [4, 4], [0, 1], 0, [1, 3], False, 2], 4: [[None, None], [4, 5], [0, 1], 0, [1, 4], False, 2], 5: [[None, None], [4, 6], [0, 1], 0, [1, 5], False, 2]}[N])
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
0	`[[1, None, None], [2, 5, 0], [2, 1], 1, [1, 5], False, 2]`	`[[1, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2]`	Failed
1	`[[None], [2], [0], 0, [0, 1], False, 1]`	`[[None], [2], [0], 0, [0, 1], False, 1]`	Passed
2	`[[None, 1, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 5], False, 3]`	`[[None, 1, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3]`	Failed
3	`[[None, 2, 3], [2, 2, 3], [0], 2, [0, 2], False, 1]`	`[[None, 2, 3], [2, 2, 3], [0], 2, [0, 1], False, 1]`	Failed
4	`[[1, None, None], [3, 0, 8], [1, 2], 1, [2, 8], False, 2]`	`[[1, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2]`	Failed
5	`[[None, None], [4, 2], [0, 1], 0, [1, 1], False, 2]`	`[[None, None], [4, 2], [0, 1], 0, [1, 1], False, 2]`	Passed

SHA-256 / bfaff52e4527002ed92935951a917f528aa799bda9523be97d1c91882e9eac00

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(x):
    slots,index,generations,free,live=x
    storage=slots[:]
    storage[index]=None
    versions=generations[:]
    versions[index]+=1
    available=free+[index]
    count=live-1
    old_handle=[index,generations[index]]
    valid=False
    return [storage,versions,available,count,old_handle,valid,len(available)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N,N+1,None],1,[2,4,0],[2],2]), {1: [[1, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2], 2: [[2, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2], 3: [[3, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2], 4: [[4, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2], 5: [[5, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2]}[N])
check('1', solve([[N],0,[N],[],1]), {1: [[None], [2], [0], 0, [0, 1], False, 1], 2: [[None], [3], [0], 0, [0, 2], False, 1], 3: [[None], [4], [0], 0, [0, 3], False, 1], 4: [[None], [5], [0], 0, [0, 4], False, 1], 5: [[None], [6], [0], 0, [0, 5], False, 1]}[N])
check('2', solve([[None,N,None,N+1],3,[1,2,3,4],[0,2],2]), {1: [[None, 1, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3], 2: [[None, 2, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3], 3: [[None, 3, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3], 4: [[None, 4, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3], 5: [[None, 5, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3]}[N])
check('3', solve([[N,N+1,N+2],0,[N,N+1,N+2],[],3]), {1: [[None, 2, 3], [2, 2, 3], [0], 2, [0, 1], False, 1], 2: [[None, 3, 4], [3, 3, 4], [0], 2, [0, 2], False, 1], 3: [[None, 4, 5], [4, 4, 5], [0], 2, [0, 3], False, 1], 4: [[None, 5, 6], [5, 5, 6], [0], 2, [0, 4], False, 1], 5: [[None, 6, 7], [6, 6, 7], [0], 2, [0, 5], False, 1]}[N])
check('4', solve([[N,None,N+1],2,[3,0,7],[1],2]), {1: [[1, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2], 2: [[2, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2], 3: [[3, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2], 4: [[4, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2], 5: [[5, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2]}[N])
check('5', solve([[None,N],1,[4,N],[0],1]), {1: [[None, None], [4, 2], [0, 1], 0, [1, 1], False, 2], 2: [[None, None], [4, 3], [0, 1], 0, [1, 2], False, 2], 3: [[None, None], [4, 4], [0, 1], 0, [1, 3], False, 2], 4: [[None, None], [4, 5], [0, 1], 0, [1, 4], False, 2], 5: [[None, None], [4, 6], [0, 1], 0, [1, 5], False, 2]}[N])
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
0	`[[1, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2]`	`[[1, None, None], [2, 5, 0], [2, 1], 1, [1, 4], False, 2]`	Passed
1	`[[None], [2], [0], 0, [0, 1], False, 1]`	`[[None], [2], [0], 0, [0, 1], False, 1]`	Passed
2	`[[None, 1, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3]`	`[[None, 1, None, None], [1, 2, 3, 5], [0, 2, 3], 1, [3, 4], False, 3]`	Passed
3	`[[None, 2, 3], [2, 2, 3], [0], 2, [0, 1], False, 1]`	`[[None, 2, 3], [2, 2, 3], [0], 2, [0, 1], False, 1]`	Passed
4	`[[1, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2]`	`[[1, None, None], [3, 0, 8], [1, 2], 1, [2, 7], False, 2]`	Passed
5	`[[None, None], [4, 2], [0, 1], 0, [1, 1], False, 2]`	`[[None, None], [4, 2], [0, 1], 0, [1, 1], False, 2]`	Passed

SHA-256 / 768e3326329a06f4119bc7c40a4546dedc9537a32ac6880808f3eefa5fe60850

Verification & scope

Offline finite deterministic model; no claim of production implementation or concurrent memory-model conformance. 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:44:33.579576+00:00.

Case digest / 3903f9efd28f5ae3ac49677f6a51240d99c478dd97d7b1658b8621782f0c89d7