FAILURE MAP
← Case archive

FA-45846 / Bounded deques / Open access

Reservation exceeds the available slot budget · case 01

Reservation exceeds the available slot budget.

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

ROOT CAUSE

Only full rings are rejected; partially full rings can over-reserve.

VERIFIED REPAIR

Restore the documented grant clamp invariant in ring-reservation.

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

Case contract

Reserve up to requested free positions in a reject-on-full ring. Return [grant,tail,first-span,second-span,free-after]. Head and size are valid, capacity positive.

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, head, size, requested = x
    free = cap - size
    grant = requested
    tail = (head + size) % cap
    first = min(grant, cap - tail)
    second = grant - first
    return [grant, tail, first, second, free - grant]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('wrapped free region', solve([N+5, N+3, 1, 3]), [3,N+4,1,2,N+1])
check('limited free space', solve([N+5, 2, N+3, 4]), [2,0,2,0,0])
check('empty shifted ring', solve([N+5,N+4,0,4]), [4,N+4,1,3,N+1])
check('empty request', solve([N+5,1,2,0]), [0,3,0,0,N+3])
check('full ring', solve([N+5,2,N+5,3]), [0,2,0,0,0])
check('contiguous grant', solve([N+5,0,1,2]), [2,1,2,0,N+2])
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
wrapped free region[3, 5, 1, 2, 2][3, 5, 1, 2, 2]Passed
limited free space[4, 0, 4, 0, -2][2, 0, 2, 0, 0]Failed
empty shifted ring[4, 5, 1, 3, 2][4, 5, 1, 3, 2]Passed
empty request[0, 3, 0, 0, 4][0, 3, 0, 0, 4]Passed
full ring[3, 2, 3, 0, -3][0, 2, 0, 0, 0]Failed
contiguous grant[2, 1, 2, 0, 3][2, 1, 2, 0, 3]Passed

SHA-256 / 5ade01997e9dd44054f532a89c20420d664131670f1bb3e29fa20b0340e7c3aa

2 / The unsuccessful fix

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

N = 1
observations = []
def solve(x):
    cap, head, size, requested = x
    free = cap - size
    grant = 0 if free == 0 else requested
    tail = (head + size) % cap
    first = min(grant, cap - tail)
    second = grant - first
    return [grant, tail, first, second, free - grant]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('wrapped free region', solve([N+5, N+3, 1, 3]), [3,N+4,1,2,N+1])
check('limited free space', solve([N+5, 2, N+3, 4]), [2,0,2,0,0])
check('empty shifted ring', solve([N+5,N+4,0,4]), [4,N+4,1,3,N+1])
check('empty request', solve([N+5,1,2,0]), [0,3,0,0,N+3])
check('full ring', solve([N+5,2,N+5,3]), [0,2,0,0,0])
check('contiguous grant', solve([N+5,0,1,2]), [2,1,2,0,N+2])
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
wrapped free region[3, 5, 1, 2, 2][3, 5, 1, 2, 2]Passed
limited free space[4, 0, 4, 0, -2][2, 0, 2, 0, 0]Failed
empty shifted ring[4, 5, 1, 3, 2][4, 5, 1, 3, 2]Passed
empty request[0, 3, 0, 0, 4][0, 3, 0, 0, 4]Passed
full ring[0, 2, 0, 0, 0][0, 2, 0, 0, 0]Passed
contiguous grant[2, 1, 2, 0, 3][2, 1, 2, 0, 3]Passed

SHA-256 / 781d3e31ccd65cf1921f4dd3f3c87c692b6cae4935ef89574f43abec6372fc4c

3 / The verified repair

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

N = 1
observations = []
def solve(x):
    cap, head, size, requested = x
    free = cap - size
    grant = min(requested, free)
    tail = (head + size) % cap
    first = min(grant, cap - tail)
    second = grant - first
    return [grant, tail, first, second, free - grant]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('wrapped free region', solve([N+5, N+3, 1, 3]), [3,N+4,1,2,N+1])
check('limited free space', solve([N+5, 2, N+3, 4]), [2,0,2,0,0])
check('empty shifted ring', solve([N+5,N+4,0,4]), [4,N+4,1,3,N+1])
check('empty request', solve([N+5,1,2,0]), [0,3,0,0,N+3])
check('full ring', solve([N+5,2,N+5,3]), [0,2,0,0,0])
check('contiguous grant', solve([N+5,0,1,2]), [2,1,2,0,N+2])
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
wrapped free region[3, 5, 1, 2, 2][3, 5, 1, 2, 2]Passed
limited free space[2, 0, 2, 0, 0][2, 0, 2, 0, 0]Passed
empty shifted ring[4, 5, 1, 3, 2][4, 5, 1, 3, 2]Passed
empty request[0, 3, 0, 0, 4][0, 3, 0, 0, 4]Passed
full ring[0, 2, 0, 0, 0][0, 2, 0, 0, 0]Passed
contiguous grant[2, 1, 2, 0, 3][2, 1, 2, 0, 3]Passed

SHA-256 / 332a2660d47d9317be78811befb39cc107de6e34c3631bc80e3c9577273f7d39

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

Case digest / 60c06aaf97704a7b7ab1ca79b60df4695e9e69b2b0c0d55293cb5ba1b02a6641