FAILURE MAP
← Case archive

FA-45861 / Bounded deques / Open access

Reservation reuses the first span as the wrapped span · case 01

Reservation reuses the first span as the wrapped span.

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

ROOT CAUSE

Wrapped remainder is confused with the already assigned contiguous count.

VERIFIED REPAIR

Restore the documented second span 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 = min(requested, free)
    tail = (head + size) % cap
    first = min(grant, cap - tail)
    second = 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, 1, 2][3, 5, 1, 2, 2]Failed
limited free space[2, 0, 2, 2, 0][2, 0, 2, 0, 0]Failed
empty shifted ring[4, 5, 1, 1, 2][4, 5, 1, 3, 2]Failed
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, 2, 3][2, 1, 2, 0, 3]Failed

SHA-256 / 8f9028d64ad88820ed8f20878744406dc0dc1778243d3c8ba522f027d1020ac6

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 = min(requested, free)
    tail = (head + size) % cap
    first = min(grant, cap - tail)
    second = 0 if first == grant else 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, 1, 2][3, 5, 1, 2, 2]Failed
limited free space[2, 0, 2, 0, 0][2, 0, 2, 0, 0]Passed
empty shifted ring[4, 5, 1, 1, 2][4, 5, 1, 3, 2]Failed
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 / e159171fb325cf4633fc579b3e4f34c79fd5582183437e2e3e42c8c2a84f8d8c

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

Case digest / 8f8924207ce2361fb64f8b1d501cd6cf71a97fd783ea0488a044261cde992395