FA-261 / Runtime and resources / Open access

A cache evicts the entry it most recently served · case 01

Insertion order is mistaken for recency, or updating an existing value fails to refresh that recency.

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

ROOT CAUSE

Successful accesses and overwrites do not consistently move entries to the most-recent position.

VERIFIED REPAIR

Refresh recency on both successful reads and writes; evict only the least-recent entry after insertion.

Unsuccessful approach: Refreshing reads alone leaves an overwritten hot entry at the eviction end.

Case contract

Events are ['put',key,value] or ['get',key]; keys are strings and capacity is nonnegative. A get returns value or None, and only hits refresh recency. Every put refreshes its key. Capacity zero retains nothing. Return [read results,keys ordered least to most recent].

Why this case matters

Models cache bookkeeping independently of expiration or concurrent locking, covering the difference between recency after a read and recency after replacing an existing value.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
from collections import OrderedDict
N = 1
observations = []
def solve(capacity, events):
    cache, reads = OrderedDict(), []
    for event in events:
        kind, key = event[:2]
        if kind == 'get':
            reads.append(cache.get(key))
            if key in cache:
                pass
        elif capacity > 0:
            existed = key in cache
            cache[key] = event[2]
            pass
            while len(cache) > capacity:
                cache.popitem(last=False)
    return [reads, list(cache)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
keys = ['k'+str(i) for i in range(N+1)]
puts = [['put', key, i+N] for i, key in enumerate(keys)]
new = 'new'
check('hit moves oldest before eviction', solve(N+1, puts+[['get', keys[0]], ['put', new, 99]]), [[N], keys[2:]+[keys[0], new]])
check('overwrite is also recent', solve(N+1, puts+[['put', keys[0], 100], ['put', new, 99]]), [[], keys[2:]+[keys[0], new]])
check('miss leaves recency alone', solve(N+1, puts+[['get', 'absent']]), [[None], keys])
check('zero-capacity cache', solve(0, [['put', 'a', N], ['get', 'a']]), [[None], []])
check('single entry replacement', solve(1, [['put', 'a', N], ['put', 'b', N+1], ['get', 'a'], ['get', 'b']]), [[None, N+1], ['b']])
check('read observes overwrite', solve(1, [['put', 'a', N], ['put', 'a', N+1], ['get', 'a']]), [[N+1], ['a']])
check('empty cache history', solve(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
hit moves oldest before eviction	`[[1], ['k1', 'new']]`	`[[1], ['k0', 'new']]`	Failed
overwrite is also recent	`[[], ['k1', 'new']]`	`[[], ['k0', 'new']]`	Failed
miss leaves recency alone	`[[None], ['k0', 'k1']]`	`[[None], ['k0', 'k1']]`	Passed
zero-capacity cache	`[[None], []]`	`[[None], []]`	Passed
single entry replacement	`[[None, 2], ['b']]`	`[[None, 2], ['b']]`	Passed
read observes overwrite	`[[2], ['a']]`	`[[2], ['a']]`	Passed
empty cache history	`[[], []]`	`[[], []]`	Passed

SHA-256 / f4eeb0d369e92d57698e74e988476fad00d8ac4da1d35426358c2a2479e1ee99

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
from collections import OrderedDict
N = 1
observations = []
def solve(capacity, events):
    cache, reads = OrderedDict(), []
    for event in events:
        kind, key = event[:2]
        if kind == 'get':
            reads.append(cache.get(key))
            if key in cache:
                cache.move_to_end(key)
        elif capacity > 0:
            existed = key in cache
            cache[key] = event[2]
            if not existed:
                cache.move_to_end(key)
            while len(cache) > capacity:
                cache.popitem(last=False)
    return [reads, list(cache)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
keys = ['k'+str(i) for i in range(N+1)]
puts = [['put', key, i+N] for i, key in enumerate(keys)]
new = 'new'
check('hit moves oldest before eviction', solve(N+1, puts+[['get', keys[0]], ['put', new, 99]]), [[N], keys[2:]+[keys[0], new]])
check('overwrite is also recent', solve(N+1, puts+[['put', keys[0], 100], ['put', new, 99]]), [[], keys[2:]+[keys[0], new]])
check('miss leaves recency alone', solve(N+1, puts+[['get', 'absent']]), [[None], keys])
check('zero-capacity cache', solve(0, [['put', 'a', N], ['get', 'a']]), [[None], []])
check('single entry replacement', solve(1, [['put', 'a', N], ['put', 'b', N+1], ['get', 'a'], ['get', 'b']]), [[None, N+1], ['b']])
check('read observes overwrite', solve(1, [['put', 'a', N], ['put', 'a', N+1], ['get', 'a']]), [[N+1], ['a']])
check('empty cache history', solve(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
hit moves oldest before eviction	`[[1], ['k0', 'new']]`	`[[1], ['k0', 'new']]`	Passed
overwrite is also recent	`[[], ['k1', 'new']]`	`[[], ['k0', 'new']]`	Failed
miss leaves recency alone	`[[None], ['k0', 'k1']]`	`[[None], ['k0', 'k1']]`	Passed
zero-capacity cache	`[[None], []]`	`[[None], []]`	Passed
single entry replacement	`[[None, 2], ['b']]`	`[[None, 2], ['b']]`	Passed
read observes overwrite	`[[2], ['a']]`	`[[2], ['a']]`	Passed
empty cache history	`[[], []]`	`[[], []]`	Passed

SHA-256 / c0134099d058f943b4f8bcf809a31005401c4d8217c4b1e9ce999ea3109b4eb3

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json
from collections import OrderedDict
N = 1
observations = []
def solve(capacity, events):
    cache, reads = OrderedDict(), []
    for event in events:
        kind, key = event[:2]
        if kind == 'get':
            reads.append(cache.get(key))
            if key in cache:
                cache.move_to_end(key)
        elif capacity > 0:
            existed = key in cache
            cache[key] = event[2]
            cache.move_to_end(key)
            while len(cache) > capacity:
                cache.popitem(last=False)
    return [reads, list(cache)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
keys = ['k'+str(i) for i in range(N+1)]
puts = [['put', key, i+N] for i, key in enumerate(keys)]
new = 'new'
check('hit moves oldest before eviction', solve(N+1, puts+[['get', keys[0]], ['put', new, 99]]), [[N], keys[2:]+[keys[0], new]])
check('overwrite is also recent', solve(N+1, puts+[['put', keys[0], 100], ['put', new, 99]]), [[], keys[2:]+[keys[0], new]])
check('miss leaves recency alone', solve(N+1, puts+[['get', 'absent']]), [[None], keys])
check('zero-capacity cache', solve(0, [['put', 'a', N], ['get', 'a']]), [[None], []])
check('single entry replacement', solve(1, [['put', 'a', N], ['put', 'b', N+1], ['get', 'a'], ['get', 'b']]), [[None, N+1], ['b']])
check('read observes overwrite', solve(1, [['put', 'a', N], ['put', 'a', N+1], ['get', 'a']]), [[N+1], ['a']])
check('empty cache history', solve(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
hit moves oldest before eviction	`[[1], ['k0', 'new']]`	`[[1], ['k0', 'new']]`	Passed
overwrite is also recent	`[[], ['k0', 'new']]`	`[[], ['k0', 'new']]`	Passed
miss leaves recency alone	`[[None], ['k0', 'k1']]`	`[[None], ['k0', 'k1']]`	Passed
zero-capacity cache	`[[None], []]`	`[[None], []]`	Passed
single entry replacement	`[[None, 2], ['b']]`	`[[None, 2], ['b']]`	Passed
read observes overwrite	`[[2], ['a']]`	`[[2], ['a']]`	Passed
empty cache history	`[[], []]`	`[[], []]`	Passed

SHA-256 / 2790798c838aa91f59617262bf30abdc6a95b1f2dcac1532d20147b44384696d

Verification & scope

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

Case digest / a0fecf930a866e1cd351cfa485d57d70a8b8df8133e16bb2aa8118eae05b6e24