FA-46121 / Bounded deques / Open access

Weighted overflow evicts the newest entry first · case 01

Weighted overflow evicts the newest entry first.

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

ROOT CAUSE

Weighted overflow evicts the newest entry first.

VERIFIED REPAIR

Restore the documented oldest choice invariant in weighted-eviction.

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

Case contract

Deque entries have nonnegative weights. Evict the shortest oldest prefix sufficient to satisfy the weight budget; preserve zero-weight entries unless preceding a required eviction. Return survivors, releases, weight and free budget.

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):
    items,budget=x
    keep=items[:]
    weight=sum(v[1] for v in keep)
    dropped=[]
    while weight>budget and keep:
        victim=keep.pop()
        dropped.append(victim)
        weight-=victim[1]
    return [keep,dropped,weight,budget-weight]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('multiple evictions', solve([[[N,3],[N+1,4],[N+2,2]],3]), {1: [[[3, 2]], [[1, 3], [2, 4]], 2, 1], 2: [[[4, 2]], [[2, 3], [3, 4]], 2, 1], 3: [[[5, 2]], [[3, 3], [4, 4]], 2, 1], 4: [[[6, 2]], [[4, 3], [5, 4]], 2, 1], 5: [[[7, 2]], [[5, 3], [6, 4]], 2, 1]}[N])
check('exact budget', solve([[[N,2],[N+1,3]],5]), {1: [[[1, 2], [2, 3]], [], 5, 0], 2: [[[2, 2], [3, 3]], [], 5, 0], 3: [[[3, 2], [4, 3]], [], 5, 0], 4: [[[4, 2], [5, 3]], [], 5, 0], 5: [[[5, 2], [6, 3]], [], 5, 0]}[N])
check('zero weights', solve([[[N,0],[N+1,4],[N+2,0]],0]), {1: [[[3, 0]], [[1, 0], [2, 4]], 0, 0], 2: [[[4, 0]], [[2, 0], [3, 4]], 0, 0], 3: [[[5, 0]], [[3, 0], [4, 4]], 0, 0], 4: [[[6, 0]], [[4, 0], [5, 4]], 0, 0], 5: [[[7, 0]], [[5, 0], [6, 4]], 0, 0]}[N])
check('empty', solve([[],4]), {1: [[], [], 0, 4], 2: [[], [], 0, 4], 3: [[], [], 0, 4], 4: [[], [], 0, 4], 5: [[], [], 0, 4]}[N])
check('retain suffix', solve([[[N,2],[N+1,1],[N+2,3]],4]), {1: [[[2, 1], [3, 3]], [[1, 2]], 4, 0], 2: [[[3, 1], [4, 3]], [[2, 2]], 4, 0], 3: [[[4, 1], [5, 3]], [[3, 2]], 4, 0], 4: [[[5, 1], [6, 3]], [[4, 2]], 4, 0], 5: [[[6, 1], [7, 3]], [[5, 2]], 4, 0]}[N])
check('heavy singleton', solve([[[N,8]],2]), {1: [[], [[1, 8]], 0, 2], 2: [[], [[2, 8]], 0, 2], 3: [[], [[3, 8]], 0, 2], 4: [[], [[4, 8]], 0, 2], 5: [[], [[5, 8]], 0, 2]}[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
multiple evictions	`[[[1, 3]], [[3, 2], [2, 4]], 3, 0]`	`[[[3, 2]], [[1, 3], [2, 4]], 2, 1]`	Failed
exact budget	`[[[1, 2], [2, 3]], [], 5, 0]`	`[[[1, 2], [2, 3]], [], 5, 0]`	Passed
zero weights	`[[[1, 0]], [[3, 0], [2, 4]], 0, 0]`	`[[[3, 0]], [[1, 0], [2, 4]], 0, 0]`	Failed
empty	`[[], [], 0, 4]`	`[[], [], 0, 4]`	Passed
retain suffix	`[[[1, 2], [2, 1]], [[3, 3]], 3, 1]`	`[[[2, 1], [3, 3]], [[1, 2]], 4, 0]`	Failed
heavy singleton	`[[], [[1, 8]], 0, 2]`	`[[], [[1, 8]], 0, 2]`	Passed

SHA-256 / a40ce5664584d103d904ae56e3de96da37f30cf8e7141126e37160748a0f47da

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(x):
    items,budget=x
    keep=items[:]
    weight=sum(v[1] for v in keep)
    dropped=[]
    while weight>budget and keep:
        victim=keep.pop(0 if len(keep)==1 else -1)
        dropped.append(victim)
        weight-=victim[1]
    return [keep,dropped,weight,budget-weight]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('multiple evictions', solve([[[N,3],[N+1,4],[N+2,2]],3]), {1: [[[3, 2]], [[1, 3], [2, 4]], 2, 1], 2: [[[4, 2]], [[2, 3], [3, 4]], 2, 1], 3: [[[5, 2]], [[3, 3], [4, 4]], 2, 1], 4: [[[6, 2]], [[4, 3], [5, 4]], 2, 1], 5: [[[7, 2]], [[5, 3], [6, 4]], 2, 1]}[N])
check('exact budget', solve([[[N,2],[N+1,3]],5]), {1: [[[1, 2], [2, 3]], [], 5, 0], 2: [[[2, 2], [3, 3]], [], 5, 0], 3: [[[3, 2], [4, 3]], [], 5, 0], 4: [[[4, 2], [5, 3]], [], 5, 0], 5: [[[5, 2], [6, 3]], [], 5, 0]}[N])
check('zero weights', solve([[[N,0],[N+1,4],[N+2,0]],0]), {1: [[[3, 0]], [[1, 0], [2, 4]], 0, 0], 2: [[[4, 0]], [[2, 0], [3, 4]], 0, 0], 3: [[[5, 0]], [[3, 0], [4, 4]], 0, 0], 4: [[[6, 0]], [[4, 0], [5, 4]], 0, 0], 5: [[[7, 0]], [[5, 0], [6, 4]], 0, 0]}[N])
check('empty', solve([[],4]), {1: [[], [], 0, 4], 2: [[], [], 0, 4], 3: [[], [], 0, 4], 4: [[], [], 0, 4], 5: [[], [], 0, 4]}[N])
check('retain suffix', solve([[[N,2],[N+1,1],[N+2,3]],4]), {1: [[[2, 1], [3, 3]], [[1, 2]], 4, 0], 2: [[[3, 1], [4, 3]], [[2, 2]], 4, 0], 3: [[[4, 1], [5, 3]], [[3, 2]], 4, 0], 4: [[[5, 1], [6, 3]], [[4, 2]], 4, 0], 5: [[[6, 1], [7, 3]], [[5, 2]], 4, 0]}[N])
check('heavy singleton', solve([[[N,8]],2]), {1: [[], [[1, 8]], 0, 2], 2: [[], [[2, 8]], 0, 2], 3: [[], [[3, 8]], 0, 2], 4: [[], [[4, 8]], 0, 2], 5: [[], [[5, 8]], 0, 2]}[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
multiple evictions	`[[[1, 3]], [[3, 2], [2, 4]], 3, 0]`	`[[[3, 2]], [[1, 3], [2, 4]], 2, 1]`	Failed
exact budget	`[[[1, 2], [2, 3]], [], 5, 0]`	`[[[1, 2], [2, 3]], [], 5, 0]`	Passed
zero weights	`[[[1, 0]], [[3, 0], [2, 4]], 0, 0]`	`[[[3, 0]], [[1, 0], [2, 4]], 0, 0]`	Failed
empty	`[[], [], 0, 4]`	`[[], [], 0, 4]`	Passed
retain suffix	`[[[1, 2], [2, 1]], [[3, 3]], 3, 1]`	`[[[2, 1], [3, 3]], [[1, 2]], 4, 0]`	Failed
heavy singleton	`[[], [[1, 8]], 0, 2]`	`[[], [[1, 8]], 0, 2]`	Passed

SHA-256 / b78f051bf66d51723d8b618e0427423fb603866878340b767970448b5f1463c6

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(x):
    items,budget=x
    keep=items[:]
    weight=sum(v[1] for v in keep)
    dropped=[]
    while weight>budget and keep:
        victim=keep.pop(0)
        dropped.append(victim)
        weight-=victim[1]
    return [keep,dropped,weight,budget-weight]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('multiple evictions', solve([[[N,3],[N+1,4],[N+2,2]],3]), {1: [[[3, 2]], [[1, 3], [2, 4]], 2, 1], 2: [[[4, 2]], [[2, 3], [3, 4]], 2, 1], 3: [[[5, 2]], [[3, 3], [4, 4]], 2, 1], 4: [[[6, 2]], [[4, 3], [5, 4]], 2, 1], 5: [[[7, 2]], [[5, 3], [6, 4]], 2, 1]}[N])
check('exact budget', solve([[[N,2],[N+1,3]],5]), {1: [[[1, 2], [2, 3]], [], 5, 0], 2: [[[2, 2], [3, 3]], [], 5, 0], 3: [[[3, 2], [4, 3]], [], 5, 0], 4: [[[4, 2], [5, 3]], [], 5, 0], 5: [[[5, 2], [6, 3]], [], 5, 0]}[N])
check('zero weights', solve([[[N,0],[N+1,4],[N+2,0]],0]), {1: [[[3, 0]], [[1, 0], [2, 4]], 0, 0], 2: [[[4, 0]], [[2, 0], [3, 4]], 0, 0], 3: [[[5, 0]], [[3, 0], [4, 4]], 0, 0], 4: [[[6, 0]], [[4, 0], [5, 4]], 0, 0], 5: [[[7, 0]], [[5, 0], [6, 4]], 0, 0]}[N])
check('empty', solve([[],4]), {1: [[], [], 0, 4], 2: [[], [], 0, 4], 3: [[], [], 0, 4], 4: [[], [], 0, 4], 5: [[], [], 0, 4]}[N])
check('retain suffix', solve([[[N,2],[N+1,1],[N+2,3]],4]), {1: [[[2, 1], [3, 3]], [[1, 2]], 4, 0], 2: [[[3, 1], [4, 3]], [[2, 2]], 4, 0], 3: [[[4, 1], [5, 3]], [[3, 2]], 4, 0], 4: [[[5, 1], [6, 3]], [[4, 2]], 4, 0], 5: [[[6, 1], [7, 3]], [[5, 2]], 4, 0]}[N])
check('heavy singleton', solve([[[N,8]],2]), {1: [[], [[1, 8]], 0, 2], 2: [[], [[2, 8]], 0, 2], 3: [[], [[3, 8]], 0, 2], 4: [[], [[4, 8]], 0, 2], 5: [[], [[5, 8]], 0, 2]}[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
multiple evictions	`[[[3, 2]], [[1, 3], [2, 4]], 2, 1]`	`[[[3, 2]], [[1, 3], [2, 4]], 2, 1]`	Passed
exact budget	`[[[1, 2], [2, 3]], [], 5, 0]`	`[[[1, 2], [2, 3]], [], 5, 0]`	Passed
zero weights	`[[[3, 0]], [[1, 0], [2, 4]], 0, 0]`	`[[[3, 0]], [[1, 0], [2, 4]], 0, 0]`	Passed
empty	`[[], [], 0, 4]`	`[[], [], 0, 4]`	Passed
retain suffix	`[[[2, 1], [3, 3]], [[1, 2]], 4, 0]`	`[[[2, 1], [3, 3]], [[1, 2]], 4, 0]`	Passed
heavy singleton	`[[], [[1, 8]], 0, 2]`	`[[], [[1, 8]], 0, 2]`	Passed

SHA-256 / 057455ee2271685ee13d84aee6fd213f48ad858c337a2c8eea74ebcc1dc97eb8

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

Case digest / 8be81b25dd28bdd2682fbb5e0fbb206e7ec6f43ef533af507745e6b2a1fd8a16