FA-47331 / Bounded deques / Open access
New deque reservation records all free slots instead of its granted request · case 01
New deque reservation records all free slots instead of its granted request.
ROOT CAUSE
Admission computes a requested grant correctly, but the permit record stores the entire available budget and overcharges unrelated future producers.
VERIFIED REPAIR
Use the corrected transition: active=claims+([['new',want]] if accepted else [])
Unsuccessful approach: The attempted transition still violates the stated contract: active=claims+([['new',want if want==0 else available]] if accepted else [])
Case contract
Bounded deque capacity includes live items and outstanding insertion permits. Grant a new permit only if it fits, then cancel one named permit and report the remaining permits and capacity.
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):
cap,size,claims,want,cancel=x
reserved=sum(c[1] for c in claims)
available=cap-size-reserved
accepted=want<=available
active=claims+([['new',available]] if accepted else [])
active=[c for c in active if c[0]!=cancel]
free=cap-size-sum(c[1] for c in active)
return [active,accepted,free]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('reserved blocks grant', solve([8,3,[["a",3]],3,"none"]), {1: [[['a', 3]], False, 2], 2: [[['a', 3]], False, 2], 3: [[['a', 3]], False, 2], 4: [[['a', 3]], False, 2], 5: [[['a', 3]], False, 2]}[N])
check('cancel existing', solve([9,2,[["a",2],["b",1]],2,"a"]), {1: [[['b', 1], ['new', 2]], True, 4], 2: [[['b', 1], ['new', 2]], True, 4], 3: [[['b', 1], ['new', 2]], True, 4], 4: [[['b', 1], ['new', 2]], True, 4], 5: [[['b', 1], ['new', 2]], True, 4]}[N])
check('cancel new', solve([7,2,[["a",1]],3,"new"]), {1: [[['a', 1]], True, 4], 2: [[['a', 1]], True, 4], 3: [[['a', 1]], True, 4], 4: [[['a', 1]], True, 4], 5: [[['a', 1]], True, 4]}[N])
check('exact available', solve([6,2,[["a",1]],3,"none"]), {1: [[['a', 1], ['new', 3]], True, 0], 2: [[['a', 1], ['new', 3]], True, 0], 3: [[['a', 1], ['new', 3]], True, 0], 4: [[['a', 1], ['new', 3]], True, 0], 5: [[['a', 1], ['new', 3]], True, 0]}[N])
check('no claims', solve([N+4,N,[],2,"none"]), {1: [[['new', 2]], True, 2], 2: [[['new', 2]], True, 2], 3: [[['new', 2]], True, 2], 4: [[['new', 2]], True, 2], 5: [[['new', 2]], True, 2]}[N])
check('zero permit', solve([4,4,[],0,"none"]), {1: [[['new', 0]], True, 0], 2: [[['new', 0]], True, 0], 3: [[['new', 0]], True, 0], 4: [[['new', 0]], True, 0], 5: [[['new', 0]], True, 0]}[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 |
|---|---|---|---|
| reserved blocks grant | [[['a', 3]], False, 2] | [[['a', 3]], False, 2] | Passed |
| cancel existing | [[['b', 1], ['new', 4]], True, 2] | [[['b', 1], ['new', 2]], True, 4] | Failed |
| cancel new | [[['a', 1]], True, 4] | [[['a', 1]], True, 4] | Passed |
| exact available | [[['a', 1], ['new', 3]], True, 0] | [[['a', 1], ['new', 3]], True, 0] | Passed |
| no claims | [[['new', 4]], True, 0] | [[['new', 2]], True, 2] | Failed |
| zero permit | [[['new', 0]], True, 0] | [[['new', 0]], True, 0] | Passed |
SHA-256 / a9db9474a7b3e52254735668a55c37d7a9208fbf91b1f6bc03897cf4e50ad575
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
cap,size,claims,want,cancel=x
reserved=sum(c[1] for c in claims)
available=cap-size-reserved
accepted=want<=available
active=claims+([['new',want if want==0 else available]] if accepted else [])
active=[c for c in active if c[0]!=cancel]
free=cap-size-sum(c[1] for c in active)
return [active,accepted,free]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('reserved blocks grant', solve([8,3,[["a",3]],3,"none"]), {1: [[['a', 3]], False, 2], 2: [[['a', 3]], False, 2], 3: [[['a', 3]], False, 2], 4: [[['a', 3]], False, 2], 5: [[['a', 3]], False, 2]}[N])
check('cancel existing', solve([9,2,[["a",2],["b",1]],2,"a"]), {1: [[['b', 1], ['new', 2]], True, 4], 2: [[['b', 1], ['new', 2]], True, 4], 3: [[['b', 1], ['new', 2]], True, 4], 4: [[['b', 1], ['new', 2]], True, 4], 5: [[['b', 1], ['new', 2]], True, 4]}[N])
check('cancel new', solve([7,2,[["a",1]],3,"new"]), {1: [[['a', 1]], True, 4], 2: [[['a', 1]], True, 4], 3: [[['a', 1]], True, 4], 4: [[['a', 1]], True, 4], 5: [[['a', 1]], True, 4]}[N])
check('exact available', solve([6,2,[["a",1]],3,"none"]), {1: [[['a', 1], ['new', 3]], True, 0], 2: [[['a', 1], ['new', 3]], True, 0], 3: [[['a', 1], ['new', 3]], True, 0], 4: [[['a', 1], ['new', 3]], True, 0], 5: [[['a', 1], ['new', 3]], True, 0]}[N])
check('no claims', solve([N+4,N,[],2,"none"]), {1: [[['new', 2]], True, 2], 2: [[['new', 2]], True, 2], 3: [[['new', 2]], True, 2], 4: [[['new', 2]], True, 2], 5: [[['new', 2]], True, 2]}[N])
check('zero permit', solve([4,4,[],0,"none"]), {1: [[['new', 0]], True, 0], 2: [[['new', 0]], True, 0], 3: [[['new', 0]], True, 0], 4: [[['new', 0]], True, 0], 5: [[['new', 0]], True, 0]}[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 |
|---|---|---|---|
| reserved blocks grant | [[['a', 3]], False, 2] | [[['a', 3]], False, 2] | Passed |
| cancel existing | [[['b', 1], ['new', 4]], True, 2] | [[['b', 1], ['new', 2]], True, 4] | Failed |
| cancel new | [[['a', 1]], True, 4] | [[['a', 1]], True, 4] | Passed |
| exact available | [[['a', 1], ['new', 3]], True, 0] | [[['a', 1], ['new', 3]], True, 0] | Passed |
| no claims | [[['new', 4]], True, 0] | [[['new', 2]], True, 2] | Failed |
| zero permit | [[['new', 0]], True, 0] | [[['new', 0]], True, 0] | Passed |
SHA-256 / a07e79e5af0c6a27932e87513b18e9c2e0d1f549c70341742be5fd65548473f7
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
cap,size,claims,want,cancel=x
reserved=sum(c[1] for c in claims)
available=cap-size-reserved
accepted=want<=available
active=claims+([['new',want]] if accepted else [])
active=[c for c in active if c[0]!=cancel]
free=cap-size-sum(c[1] for c in active)
return [active,accepted,free]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('reserved blocks grant', solve([8,3,[["a",3]],3,"none"]), {1: [[['a', 3]], False, 2], 2: [[['a', 3]], False, 2], 3: [[['a', 3]], False, 2], 4: [[['a', 3]], False, 2], 5: [[['a', 3]], False, 2]}[N])
check('cancel existing', solve([9,2,[["a",2],["b",1]],2,"a"]), {1: [[['b', 1], ['new', 2]], True, 4], 2: [[['b', 1], ['new', 2]], True, 4], 3: [[['b', 1], ['new', 2]], True, 4], 4: [[['b', 1], ['new', 2]], True, 4], 5: [[['b', 1], ['new', 2]], True, 4]}[N])
check('cancel new', solve([7,2,[["a",1]],3,"new"]), {1: [[['a', 1]], True, 4], 2: [[['a', 1]], True, 4], 3: [[['a', 1]], True, 4], 4: [[['a', 1]], True, 4], 5: [[['a', 1]], True, 4]}[N])
check('exact available', solve([6,2,[["a",1]],3,"none"]), {1: [[['a', 1], ['new', 3]], True, 0], 2: [[['a', 1], ['new', 3]], True, 0], 3: [[['a', 1], ['new', 3]], True, 0], 4: [[['a', 1], ['new', 3]], True, 0], 5: [[['a', 1], ['new', 3]], True, 0]}[N])
check('no claims', solve([N+4,N,[],2,"none"]), {1: [[['new', 2]], True, 2], 2: [[['new', 2]], True, 2], 3: [[['new', 2]], True, 2], 4: [[['new', 2]], True, 2], 5: [[['new', 2]], True, 2]}[N])
check('zero permit', solve([4,4,[],0,"none"]), {1: [[['new', 0]], True, 0], 2: [[['new', 0]], True, 0], 3: [[['new', 0]], True, 0], 4: [[['new', 0]], True, 0], 5: [[['new', 0]], True, 0]}[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 |
|---|---|---|---|
| reserved blocks grant | [[['a', 3]], False, 2] | [[['a', 3]], False, 2] | Passed |
| cancel existing | [[['b', 1], ['new', 2]], True, 4] | [[['b', 1], ['new', 2]], True, 4] | Passed |
| cancel new | [[['a', 1]], True, 4] | [[['a', 1]], True, 4] | Passed |
| exact available | [[['a', 1], ['new', 3]], True, 0] | [[['a', 1], ['new', 3]], True, 0] | Passed |
| no claims | [[['new', 2]], True, 2] | [[['new', 2]], True, 2] | Passed |
| zero permit | [[['new', 0]], True, 0] | [[['new', 0]], True, 0] | Passed |
SHA-256 / 423b4b3e95cad39705d3868532901e2268a8591564c2b541dcda6fc3ca23216e
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:40.360639+00:00.
Case digest / 941792218d0335b52ad81b0969010090f2ff4b63d979c5f4973b016e5f896dfa