FAILURE MAP
← Case archive

FA-45851 / Bounded deques / Open access

Reservation starts at the head instead of the write cursor · case 01

Reservation starts at the head instead of the write cursor.

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

ROOT CAUSE

The read cursor is substituted for the end of the occupied arc.

VERIFIED REPAIR

Restore the documented tail origin 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
    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, 4, 2, 1, 2][3, 5, 1, 2, 2]Failed
limited free space[2, 2, 2, 0, 0][2, 0, 2, 0, 0]Failed
empty shifted ring[4, 5, 1, 3, 2][4, 5, 1, 3, 2]Passed
empty request[0, 1, 0, 0, 4][0, 3, 0, 0, 4]Failed
full ring[0, 2, 0, 0, 0][0, 2, 0, 0, 0]Passed
contiguous grant[2, 0, 2, 0, 3][2, 1, 2, 0, 3]Failed

SHA-256 / 552ca8321389679488a60922a833f5f483e43d8202034f601a7a1853a601b682

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 + 1) % cap if size == 1 else head
    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, 2, 2, 0, 0][2, 0, 2, 0, 0]Failed
empty shifted ring[4, 5, 1, 3, 2][4, 5, 1, 3, 2]Passed
empty request[0, 1, 0, 0, 4][0, 3, 0, 0, 4]Failed
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 / f5be97ce9de96942de6a80e581220d59afb23a30b2f54068b9f15db9fbd7ba89

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

Case digest / 6a864f96baaf1391da234bfa381dee6d7e5d4a53a6b4922624f7356bd2d6b9f0