FA-10426 / Caching / Open access
LFU eviction breaks equal-frequency ties by key name · case 01
LFU eviction breaks equal-frequency ties by key name.
ROOT CAUSE
Lexical identity replaces the least-recent access timestamp for frequency ties.
VERIFIED REPAIR
Preserve the cache-state invariant: Entries are [key,frequency,last-access sequence]. Return the minimum (frequency,last access,key) victim, or None for an empty cache.
Unsuccessful approach: Pure LRU discards the frequency ordering instead of fixing its tie-break.
Case contract
Entries are [key,frequency,last-access sequence]. Return the minimum (frequency,last access,key) victim, or None for an empty cache.
Why this case matters
A deterministic cache state transformation. Inputs are copied or treated as immutable; no remote storage, real clock, or concurrent interleaving is simulated.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(entries):
return min(entries,key=lambda x:(x[1],x[0]))[0] if entries else None
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('fixture 1', solve(*([['z', 1, 2], ['a', 1, 9]],)), 'z')
check('fixture 2', solve(*([['a', 3, 1], ['b', 1, 8]],)), 'b')
check('fixture 3', solve(*([['a', 1, 4]],)), 'a')
check('fixture 4', solve(*([],)), None)
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 |
|---|---|---|---|
| fixture 1 | a | z | Failed |
| fixture 2 | b | b | Passed |
| fixture 3 | a | a | Passed |
| fixture 4 | None | None | Passed |
SHA-256 / 3bb7c31adc34694122637e0fb1d50de266a0439e4ab034624a6846d7ac11d2bb
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(entries):
return min(entries,key=lambda x:x[2])[0] if entries else None
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('fixture 1', solve(*([['z', 1, 2], ['a', 1, 9]],)), 'z')
check('fixture 2', solve(*([['a', 3, 1], ['b', 1, 8]],)), 'b')
check('fixture 3', solve(*([['a', 1, 4]],)), 'a')
check('fixture 4', solve(*([],)), None)
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 |
|---|---|---|---|
| fixture 1 | z | z | Passed |
| fixture 2 | a | b | Failed |
| fixture 3 | a | a | Passed |
| fixture 4 | None | None | Passed |
SHA-256 / c9be40ced3987f86945c0e2b98710d615f2ddcfba063b54cc42f24c1eabbe0d2
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(entries):
return min(entries,key=lambda x:(x[1],x[2],x[0]))[0] if entries else None
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('fixture 1', solve(*([['z', 1, 2], ['a', 1, 9]],)), 'z')
check('fixture 2', solve(*([['a', 3, 1], ['b', 1, 8]],)), 'b')
check('fixture 3', solve(*([['a', 1, 4]],)), 'a')
check('fixture 4', solve(*([],)), None)
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 |
|---|---|---|---|
| fixture 1 | z | z | Passed |
| fixture 2 | b | b | Passed |
| fixture 3 | a | a | Passed |
| fixture 4 | None | None | Passed |
SHA-256 / 005aa1584f0810d0c1e1e5bf46ebb77b0e8fb3b1469588653cdf2997aa20c678
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:38:38.881054+00:00.
Case digest / 3bb0a2e653ad98fbd0a269763bd8f10ac60f62b5cc89f21429c45769a8351835