FAILURE MAP
← Case archive

FA-46976 / Bounded deques / Open access

Deque borrow release retains already-reclaimed storage in its pending list · case 01

Deque borrow release retains already-reclaimed storage in its pending list.

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

ROOT CAUSE

Deque borrow release retains already-reclaimed storage in its pending list.

VERIFIED REPAIR

Restore the documented pending clear invariant in borrow-release.

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

Case contract

Release a unique deque borrow token. Retired storage is reclaimed only when both the owner and all borrowers are gone; unknown releases are idempotent. Return active pins, receipt, retired/reclaimed sets, reclamation epoch and owner state.

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):
    pins,token,owner,retired,epoch=x
    found=any(p[0]==token for p in pins)
    active=[p for p in pins if p[0]!=token]
    can_reclaim=not active and not owner
    reclaimed=retired[:] if can_reclaim else []
    pending=retired[:]
    version=epoch+(found and bool(reclaimed))
    return [active,found,pending,reclaimed,version,bool(active),owner]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[[1,N],[2,N+1]],1,False,[4,5],2]), {1: [[[2, 2]], True, [4, 5], [], 2, True, False], 2: [[[2, 3]], True, [4, 5], [], 2, True, False], 3: [[[2, 4]], True, [4, 5], [], 2, True, False], 4: [[[2, 5]], True, [4, 5], [], 2, True, False], 5: [[[2, 6]], True, [4, 5], [], 2, True, False]}[N])
check('1', solve([[[1,N]],1,False,[4,5],2]), {1: [[], True, [], [4, 5], 3, False, False], 2: [[], True, [], [4, 5], 3, False, False], 3: [[], True, [], [4, 5], 3, False, False], 4: [[], True, [], [4, 5], 3, False, False], 5: [[], True, [], [4, 5], 3, False, False]}[N])
check('2', solve([[[1,N]],1,True,[4],3]), {1: [[], True, [4], [], 3, False, True], 2: [[], True, [4], [], 3, False, True], 3: [[], True, [4], [], 3, False, True], 4: [[], True, [4], [], 3, False, True], 5: [[], True, [4], [], 3, False, True]}[N])
check('3', solve([[[1,N]],9,False,[4],1]), {1: [[[1, 1]], False, [4], [], 1, True, False], 2: [[[1, 2]], False, [4], [], 1, True, False], 3: [[[1, 3]], False, [4], [], 1, True, False], 4: [[[1, 4]], False, [4], [], 1, True, False], 5: [[[1, 5]], False, [4], [], 1, True, False]}[N])
check('4', solve([[],9,True,[],0]), {1: [[], False, [], [], 0, False, True], 2: [[], False, [], [], 0, False, True], 3: [[], False, [], [], 0, False, True], 4: [[], False, [], [], 0, False, True], 5: [[], False, [], [], 0, False, True]}[N])
check('5', solve([[[1,N],[2,N+1]],2,False,[],4]), {1: [[[1, 1]], True, [], [], 4, True, False], 2: [[[1, 2]], True, [], [], 4, True, False], 3: [[[1, 3]], True, [], [], 4, True, False], 4: [[[1, 4]], True, [], [], 4, True, False], 5: [[[1, 5]], True, [], [], 4, True, False]}[N])
check('pin identity differs from payload', solve([[[17,N],[18,N+1]],17,False,[4],3]), [[[18,N+1]],True,[4],[],3,True,False])
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 fixtureActualExpectedOutcome
0[[[2, 2]], True, [4, 5], [], 2, True, False][[[2, 2]], True, [4, 5], [], 2, True, False]Passed
1[[], True, [4, 5], [4, 5], 3, False, False][[], True, [], [4, 5], 3, False, False]Failed
2[[], True, [4], [], 3, False, True][[], True, [4], [], 3, False, True]Passed
3[[[1, 1]], False, [4], [], 1, True, False][[[1, 1]], False, [4], [], 1, True, False]Passed
4[[], False, [], [], 0, False, True][[], False, [], [], 0, False, True]Passed
5[[[1, 1]], True, [], [], 4, True, False][[[1, 1]], True, [], [], 4, True, False]Passed
pin identity differs from payload[[[18, 2]], True, [4], [], 3, True, False][[[18, 2]], True, [4], [], 3, True, False]Passed

SHA-256 / 20c4b5d729eee8b2ff6aef37adaae83d7a95f83f08045915cbc137a7ab764652

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(x):
    pins,token,owner,retired,epoch=x
    found=any(p[0]==token for p in pins)
    active=[p for p in pins if p[0]!=token]
    can_reclaim=not active and not owner
    reclaimed=retired[:] if can_reclaim else []
    pending=[] if len(reclaimed)==1 else retired[:]
    version=epoch+(found and bool(reclaimed))
    return [active,found,pending,reclaimed,version,bool(active),owner]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[[1,N],[2,N+1]],1,False,[4,5],2]), {1: [[[2, 2]], True, [4, 5], [], 2, True, False], 2: [[[2, 3]], True, [4, 5], [], 2, True, False], 3: [[[2, 4]], True, [4, 5], [], 2, True, False], 4: [[[2, 5]], True, [4, 5], [], 2, True, False], 5: [[[2, 6]], True, [4, 5], [], 2, True, False]}[N])
check('1', solve([[[1,N]],1,False,[4,5],2]), {1: [[], True, [], [4, 5], 3, False, False], 2: [[], True, [], [4, 5], 3, False, False], 3: [[], True, [], [4, 5], 3, False, False], 4: [[], True, [], [4, 5], 3, False, False], 5: [[], True, [], [4, 5], 3, False, False]}[N])
check('2', solve([[[1,N]],1,True,[4],3]), {1: [[], True, [4], [], 3, False, True], 2: [[], True, [4], [], 3, False, True], 3: [[], True, [4], [], 3, False, True], 4: [[], True, [4], [], 3, False, True], 5: [[], True, [4], [], 3, False, True]}[N])
check('3', solve([[[1,N]],9,False,[4],1]), {1: [[[1, 1]], False, [4], [], 1, True, False], 2: [[[1, 2]], False, [4], [], 1, True, False], 3: [[[1, 3]], False, [4], [], 1, True, False], 4: [[[1, 4]], False, [4], [], 1, True, False], 5: [[[1, 5]], False, [4], [], 1, True, False]}[N])
check('4', solve([[],9,True,[],0]), {1: [[], False, [], [], 0, False, True], 2: [[], False, [], [], 0, False, True], 3: [[], False, [], [], 0, False, True], 4: [[], False, [], [], 0, False, True], 5: [[], False, [], [], 0, False, True]}[N])
check('5', solve([[[1,N],[2,N+1]],2,False,[],4]), {1: [[[1, 1]], True, [], [], 4, True, False], 2: [[[1, 2]], True, [], [], 4, True, False], 3: [[[1, 3]], True, [], [], 4, True, False], 4: [[[1, 4]], True, [], [], 4, True, False], 5: [[[1, 5]], True, [], [], 4, True, False]}[N])
check('pin identity differs from payload', solve([[[17,N],[18,N+1]],17,False,[4],3]), [[[18,N+1]],True,[4],[],3,True,False])
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 fixtureActualExpectedOutcome
0[[[2, 2]], True, [4, 5], [], 2, True, False][[[2, 2]], True, [4, 5], [], 2, True, False]Passed
1[[], True, [4, 5], [4, 5], 3, False, False][[], True, [], [4, 5], 3, False, False]Failed
2[[], True, [4], [], 3, False, True][[], True, [4], [], 3, False, True]Passed
3[[[1, 1]], False, [4], [], 1, True, False][[[1, 1]], False, [4], [], 1, True, False]Passed
4[[], False, [], [], 0, False, True][[], False, [], [], 0, False, True]Passed
5[[[1, 1]], True, [], [], 4, True, False][[[1, 1]], True, [], [], 4, True, False]Passed
pin identity differs from payload[[[18, 2]], True, [4], [], 3, True, False][[[18, 2]], True, [4], [], 3, True, False]Passed

SHA-256 / 3e493db2c32bc3e821a620ac13c0089c785e81d09489664162a6cab4f30a07b2

3 / The verified repair

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

N = 1
observations = []
def solve(x):
    pins,token,owner,retired,epoch=x
    found=any(p[0]==token for p in pins)
    active=[p for p in pins if p[0]!=token]
    can_reclaim=not active and not owner
    reclaimed=retired[:] if can_reclaim else []
    pending=[] if reclaimed else retired[:]
    version=epoch+(found and bool(reclaimed))
    return [active,found,pending,reclaimed,version,bool(active),owner]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[[1,N],[2,N+1]],1,False,[4,5],2]), {1: [[[2, 2]], True, [4, 5], [], 2, True, False], 2: [[[2, 3]], True, [4, 5], [], 2, True, False], 3: [[[2, 4]], True, [4, 5], [], 2, True, False], 4: [[[2, 5]], True, [4, 5], [], 2, True, False], 5: [[[2, 6]], True, [4, 5], [], 2, True, False]}[N])
check('1', solve([[[1,N]],1,False,[4,5],2]), {1: [[], True, [], [4, 5], 3, False, False], 2: [[], True, [], [4, 5], 3, False, False], 3: [[], True, [], [4, 5], 3, False, False], 4: [[], True, [], [4, 5], 3, False, False], 5: [[], True, [], [4, 5], 3, False, False]}[N])
check('2', solve([[[1,N]],1,True,[4],3]), {1: [[], True, [4], [], 3, False, True], 2: [[], True, [4], [], 3, False, True], 3: [[], True, [4], [], 3, False, True], 4: [[], True, [4], [], 3, False, True], 5: [[], True, [4], [], 3, False, True]}[N])
check('3', solve([[[1,N]],9,False,[4],1]), {1: [[[1, 1]], False, [4], [], 1, True, False], 2: [[[1, 2]], False, [4], [], 1, True, False], 3: [[[1, 3]], False, [4], [], 1, True, False], 4: [[[1, 4]], False, [4], [], 1, True, False], 5: [[[1, 5]], False, [4], [], 1, True, False]}[N])
check('4', solve([[],9,True,[],0]), {1: [[], False, [], [], 0, False, True], 2: [[], False, [], [], 0, False, True], 3: [[], False, [], [], 0, False, True], 4: [[], False, [], [], 0, False, True], 5: [[], False, [], [], 0, False, True]}[N])
check('5', solve([[[1,N],[2,N+1]],2,False,[],4]), {1: [[[1, 1]], True, [], [], 4, True, False], 2: [[[1, 2]], True, [], [], 4, True, False], 3: [[[1, 3]], True, [], [], 4, True, False], 4: [[[1, 4]], True, [], [], 4, True, False], 5: [[[1, 5]], True, [], [], 4, True, False]}[N])
check('pin identity differs from payload', solve([[[17,N],[18,N+1]],17,False,[4],3]), [[[18,N+1]],True,[4],[],3,True,False])
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 fixtureActualExpectedOutcome
0[[[2, 2]], True, [4, 5], [], 2, True, False][[[2, 2]], True, [4, 5], [], 2, True, False]Passed
1[[], True, [], [4, 5], 3, False, False][[], True, [], [4, 5], 3, False, False]Passed
2[[], True, [4], [], 3, False, True][[], True, [4], [], 3, False, True]Passed
3[[[1, 1]], False, [4], [], 1, True, False][[[1, 1]], False, [4], [], 1, True, False]Passed
4[[], False, [], [], 0, False, True][[], False, [], [], 0, False, True]Passed
5[[[1, 1]], True, [], [], 4, True, False][[[1, 1]], True, [], [], 4, True, False]Passed
pin identity differs from payload[[[18, 2]], True, [4], [], 3, True, False][[[18, 2]], True, [4], [], 3, True, False]Passed

SHA-256 / dcbd3052aa1d8f3461cc96d7e19f675448e4c29c970ae15407bc7127f44713d2

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

Case digest / b45c7a90519d86d74a74c5b42014d7480091b6cc97c34b9ae009c8feb093b875