FAILURE MAP
← Case archive

FA-46971 / Bounded deques / Open access

Deque borrow release reverses deferred reclamation order · case 01

Deque borrow release reverses deferred reclamation order.

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

ROOT CAUSE

Deque borrow release reverses deferred reclamation order.

VERIFIED REPAIR

Restore the documented retire order 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[::-1] 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, [], [5, 4], 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 / d0269fb95853608a42eb65585c4a83f1dd62a6e038d409d0174003078484df2f

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 len(retired)<2 else retired[::-1]) 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, [], [5, 4], 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 / 7e15236e33af14ff12118b21a7e4f5a16a4ac422c6ba0109b77bbfdde1e4bb76

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

Case digest / 7e1327b3435eb5e65ce0a786cecc62bd9b1f15ae340c92c79437f9d614248fe1