FA-236 / Runtime and resources / Open access
Frequent checks destroy a token bucket's fractional credit · case 01
The limiter admits too few or too many operations when fractional refills occur between requests.
ROOT CAUSE
Rounding each elapsed refill interval loses residual credit or creates tokens before they accrue.
VERIFIED REPAIR
Carry exact fractional tokens between checks, cap the balance, and debit only accepted requests.
Unsuccessful approach: Rounding each refill upward prevents starvation by issuing tokens early, violating the rate contract.
Case contract
Capacity and initial balance are nonnegative integers with initial <= capacity; rate is nonnegative. Requests are [nondecreasing rational timestamp string,nonnegative integer cost]. Refill from time zero, cap at capacity, and accept iff sufficient credit exists. Return [acceptance flags,exact rational balance].
Why this case matters
Models token accounting under frequent polling without binary-float noise; timestamps are injected, so this experiment makes no claim about scheduler accuracy or concurrent atomic updates.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
from fractions import Fraction
from math import ceil
N = 1
observations = []
def solve(capacity, initial, rate, requests):
tokens, last, accepted = Fraction(initial), Fraction(0), []
for timestamp, cost in requests:
now = Fraction(timestamp)
refill = int(Fraction(rate)*(now-last))
tokens = min(Fraction(capacity), tokens + refill)
last = now
allowed = tokens >= cost
if allowed:
tokens -= cost
accepted.append(allowed)
return [accepted, str(tokens)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
rate = 2*N+1
check('fraction survives consumption', solve(rate, 0, rate, [['0.5', N], ['1', N+1]]), [[True, True], '0'])
check('not yet enough for next token', solve(rate, 0, rate, [['0.5', N+1]]), [[False], str(Fraction(rate, 2))])
check('capacity clips idle accrual', solve(N, 0, rate, [['10', 0]]), [[True], str(N)])
check('same instant cannot refill twice', solve(N, N, rate, [['0', N], ['0', 1]]), [[True, False], '0'])
check('oversized cost is rejected', solve(N, N, rate, [['1', N+1]]), [[False], str(N)])
check('zero refill preserves balance', solve(N, N, 0, [['100', N]]), [[True], '0'])
check('no requests preserve initial', solve(N, N, rate, []), [[], str(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 |
|---|---|---|---|
| fraction survives consumption | [[True, False], '1'] | [[True, True], '0'] | Failed |
| not yet enough for next token | [[False], '1'] | [[False], '3/2'] | Failed |
| capacity clips idle accrual | [[True], '1'] | [[True], '1'] | Passed |
| same instant cannot refill twice | [[True, False], '0'] | [[True, False], '0'] | Passed |
| oversized cost is rejected | [[False], '1'] | [[False], '1'] | Passed |
| zero refill preserves balance | [[True], '0'] | [[True], '0'] | Passed |
| no requests preserve initial | [[], '1'] | [[], '1'] | Passed |
SHA-256 / 4b0f5b0499597201ecc849b0820cbae7a313f597fbd7f2299a47682e554a883a
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
from fractions import Fraction
from math import ceil
N = 1
observations = []
def solve(capacity, initial, rate, requests):
tokens, last, accepted = Fraction(initial), Fraction(0), []
for timestamp, cost in requests:
now = Fraction(timestamp)
refill = ceil(Fraction(rate)*(now-last))
tokens = min(Fraction(capacity), tokens + refill)
last = now
allowed = tokens >= cost
if allowed:
tokens -= cost
accepted.append(allowed)
return [accepted, str(tokens)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
rate = 2*N+1
check('fraction survives consumption', solve(rate, 0, rate, [['0.5', N], ['1', N+1]]), [[True, True], '0'])
check('not yet enough for next token', solve(rate, 0, rate, [['0.5', N+1]]), [[False], str(Fraction(rate, 2))])
check('capacity clips idle accrual', solve(N, 0, rate, [['10', 0]]), [[True], str(N)])
check('same instant cannot refill twice', solve(N, N, rate, [['0', N], ['0', 1]]), [[True, False], '0'])
check('oversized cost is rejected', solve(N, N, rate, [['1', N+1]]), [[False], str(N)])
check('zero refill preserves balance', solve(N, N, 0, [['100', N]]), [[True], '0'])
check('no requests preserve initial', solve(N, N, rate, []), [[], str(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 |
|---|---|---|---|
| fraction survives consumption | [[True, True], '1'] | [[True, True], '0'] | Failed |
| not yet enough for next token | [[True], '0'] | [[False], '3/2'] | Failed |
| capacity clips idle accrual | [[True], '1'] | [[True], '1'] | Passed |
| same instant cannot refill twice | [[True, False], '0'] | [[True, False], '0'] | Passed |
| oversized cost is rejected | [[False], '1'] | [[False], '1'] | Passed |
| zero refill preserves balance | [[True], '0'] | [[True], '0'] | Passed |
| no requests preserve initial | [[], '1'] | [[], '1'] | Passed |
SHA-256 / 63ae5cb881652161ccf5284640cb5c9839a4d316e198552eedd361f088564dd0
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
from fractions import Fraction
from math import ceil
N = 1
observations = []
def solve(capacity, initial, rate, requests):
tokens, last, accepted = Fraction(initial), Fraction(0), []
for timestamp, cost in requests:
now = Fraction(timestamp)
refill = Fraction(rate)*(now-last)
tokens = min(Fraction(capacity), tokens + refill)
last = now
allowed = tokens >= cost
if allowed:
tokens -= cost
accepted.append(allowed)
return [accepted, str(tokens)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
rate = 2*N+1
check('fraction survives consumption', solve(rate, 0, rate, [['0.5', N], ['1', N+1]]), [[True, True], '0'])
check('not yet enough for next token', solve(rate, 0, rate, [['0.5', N+1]]), [[False], str(Fraction(rate, 2))])
check('capacity clips idle accrual', solve(N, 0, rate, [['10', 0]]), [[True], str(N)])
check('same instant cannot refill twice', solve(N, N, rate, [['0', N], ['0', 1]]), [[True, False], '0'])
check('oversized cost is rejected', solve(N, N, rate, [['1', N+1]]), [[False], str(N)])
check('zero refill preserves balance', solve(N, N, 0, [['100', N]]), [[True], '0'])
check('no requests preserve initial', solve(N, N, rate, []), [[], str(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 |
|---|---|---|---|
| fraction survives consumption | [[True, True], '0'] | [[True, True], '0'] | Passed |
| not yet enough for next token | [[False], '3/2'] | [[False], '3/2'] | Passed |
| capacity clips idle accrual | [[True], '1'] | [[True], '1'] | Passed |
| same instant cannot refill twice | [[True, False], '0'] | [[True, False], '0'] | Passed |
| oversized cost is rejected | [[False], '1'] | [[False], '1'] | Passed |
| zero refill preserves balance | [[True], '0'] | [[True], '0'] | Passed |
| no requests preserve initial | [[], '1'] | [[], '1'] | Passed |
SHA-256 / a45ea88a91ae13f57c8d351f7a6fcff244d78af54e3339817a04c24b6c97db23
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.531902+00:00.
Case digest / 442347cdbd67478b857422aa2999e365d390022a3f6d675992365f050eb79ca9