FA-73366 / Rate limiter algorithms / Open access
Token bucket with lazy exact refill: exact balance is denied · case 01
A request whose cost exactly equals the refilled balance is denied.
ROOT CAUSE
Admission requires strictly more tokens than the cost.
VERIFIED REPAIR
Admit when tokens >= cost.
Unsuccessful approach: Rounding the fractional balance admits requests that are still short of tokens.
Case contract
Input {capacity, rate (tokens per second), requests [[t_ms, cost]]}. The bucket starts full at t=0. At each request, elapsed = max(0, t - last); tokens = min(capacity, tokens + elapsed*rate/1000) in exact rational arithmetic; last = max(last, t) so a regressing clock neither drains nor re-credits. A cost above capacity can never succeed ("never"). Otherwise allow when tokens >= cost and deduct; else deny with wait = ceil((cost - tokens) * 1000 / rate) ms. Return [[decision, wait]], final tokens].
Why this case matters
API gateways and client SDKs meter requests with lazily refilled token buckets; the refill, clock and boundary rules decide who is throttled and what wait is advertised.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
C = x['capacity']
rate = x['rate']
tokens = Fraction(C)
last = 0
out = []
for t, cost in x['requests']:
elapsed = max(0, t - last)
tokens = min(Fraction(C), tokens + Fraction(elapsed * rate, 1000))
last = max(last, t)
if cost > C:
out.append(['never', 0])
elif tokens > cost:
tokens -= cost
out.append(['allow', 0])
else:
out.append(['deny', math.ceil((cost - tokens) * 1000 / rate)])
return [out, str(tokens)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst then refill',
{'capacity': 5,
'rate': 2,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [100, 1], [1000, 2], [1401, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 400],
['allow', 0],
['deny', 99]],
'401/500']],
['idle overflow capped',
{'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10001, 1], [10200, 1]]},
[[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']],
['clock regression',
{'capacity': 6,
'rate': 1,
'requests': [[0, 6], [5000, 1], [3100, 1], [5500, 1], [6000, 1], [6400, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
['small clock step back',
{'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3710, 1], [4000, 1], [4300, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
['oversize cost',
{'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3001, 3], [3001, 5]]},
[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
['exact boundary after refill',
{'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2334, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']],
['fractional shortfall',
{'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [901, 1]]},
[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']],
['random stream',
{'capacity': 4,
'rate': 2,
'requests': [[1025, 1],
[1038, 3],
[1399, 1],
[1944, 3],
[2745, 1],
[2753, 1],
[3169, 1],
[4025, 1],
[4086, 3],
[4305, 3]]},
[[['allow', 0],
['allow', 0],
['deny', 126],
['deny', 581],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 439],
['deny', 220]],
'64/25']]],
[['burst then refill',
{'capacity': 5,
'rate': 2,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [200, 1], [1000, 2], [1402, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 300],
['allow', 0],
['deny', 98]],
'201/250']],
['idle overflow capped',
{'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10002, 1], [10200, 1]]},
[[['allow', 0], ['allow', 0], ['deny', 332], ['deny', 134]], '3/5']],
['clock regression',
{'capacity': 6,
'rate': 1,
'requests': [[0, 6], [5000, 1], [3200, 1], [5500, 1], [6000, 1], [6400, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
['small clock step back',
{'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3720, 1], [4000, 1], [4300, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
['oversize cost',
{'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3002, 3], [3002, 6]]},
[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
['exact boundary after refill',
{'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2668, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '251/250']],
['fractional shortfall',
{'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [902, 1]]},
[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '353/500']],
['random stream',
{'capacity': 4,
'rate': 2,
'requests': [[679, 3],
[889, 1],
[1479, 1],
[1523, 1],
[1681, 1],
[2074, 3],
[2401, 2],
[2669, 3],
[4187, 3],
[4538, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 156],
['allow', 0],
['deny', 1105],
['deny', 278],
['deny', 510],
['allow', 0],
['allow', 0]],
'351/500']]],
[['burst then refill',
{'capacity': 5,
'rate': 2,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [300, 1], [1000, 2], [1403, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 200],
['allow', 0],
['deny', 97]],
'403/500']],
['idle overflow capped',
{'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10003, 1], [10200, 1]]},
[[['allow', 0], ['allow', 0], ['deny', 331], ['deny', 134]], '3/5']],
['clock regression',
{'capacity': 6,
'rate': 1,
'requests': [[0, 6], [5000, 1], [3300, 1], [5500, 1], [6000, 1], [6400, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
['small clock step back',
{'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3730, 1], [4000, 1], [4300, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
['oversize cost',
{'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3003, 3], [3003, 7]]},
[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
['exact boundary after refill',
{'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3002, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1003/500']],
['fractional shortfall',
{'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [903, 1]]},
[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '709/1000']],
['random stream',
{'capacity': 4,
'rate': 2,
'requests': [[476, 2],
[1005, 3],
[1092, 1],
[1140, 2],
[2416, 2],
[2727, 2],
[3540, 3],
[3809, 1],
[3822, 1],
[4130, 1]]},
[[['allow', 0],
['allow', 0],
['deny', 384],
['deny', 836],
['allow', 0],
['deny', 249],
['allow', 0],
['deny', 167],
['deny', 154],
['allow', 0]],
'77/250']]],
[['burst then refill',
{'capacity': 5,
'rate': 2,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [400, 1], [1000, 2], [1404, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 100],
['allow', 0],
['deny', 96]],
'101/125']],
['idle overflow capped',
{'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10004, 1], [10200, 1]]},
[[['allow', 0], ['allow', 0], ['deny', 330], ['deny', 134]], '3/5']],
['clock regression',
{'capacity': 6,
'rate': 1,
'requests': [[0, 6], [5000, 1], [3400, 1], [5500, 1], [6000, 1], [6400, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
['small clock step back',
{'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3740, 1], [4000, 1], [4300, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
['oversize cost',
{'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3004, 3], [3004, 8]]},
[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
['exact boundary after refill',
{'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3336, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '376/125']],
['fractional shortfall',
{'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [904, 1]]},
[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '89/125']],
['random stream',
{'capacity': 4,
'rate': 2,
'requests': [[295, 3],
[481, 2],
[603, 2],
[1079, 3],
[1690, 3],
[1700, 3],
[2433, 3],
[3280, 3],
[4573, 3],
[4680, 3]]},
[[['allow', 0],
['deny', 314],
['deny', 192],
['deny', 216],
['allow', 0],
['deny', 1095],
['deny', 362],
['allow', 0],
['allow', 0],
['deny', 1115]],
'77/100']]],
[['burst then refill',
{'capacity': 5,
'rate': 2,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [500, 1], [1000, 2], [1405, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 500],
['allow', 0]],
'81/100']],
['idle overflow capped',
{'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10005, 1], [10200, 1]]},
[[['allow', 0], ['allow', 0], ['deny', 329], ['deny', 134]], '3/5']],
['clock regression',
{'capacity': 6,
'rate': 1,
'requests': [[0, 6], [5000, 1], [3500, 1], [5500, 1], [6000, 1], [6400, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
['small clock step back',
{'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3750, 1], [4000, 1], [4300, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
['oversize cost',
{'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3005, 3], [3005, 9]]},
[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
['exact boundary after refill',
{'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3670, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '401/100']],
['fractional shortfall',
{'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [905, 1]]},
[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '143/200']],
['random stream',
{'capacity': 4,
'rate': 2,
'requests': [[1144, 3],
[1657, 3],
[1896, 3],
[2302, 2],
[2570, 2],
[3012, 1],
[3025, 1],
[3251, 1],
[4294, 1],
[4860, 2]]},
[[['allow', 0],
['deny', 487],
['deny', 248],
['allow', 0],
['deny', 74],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0]],
'54/125']]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
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 |
|---|---|---|---|
| burst then refill | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 0], ['allow', 0], ['deny', 0], ['allow', 0]], '901/500'] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 400], ['allow', 0], ['deny', 99]], '401/500'] | Failed |
| idle overflow capped | [[['deny', 0], ['deny', 0], ['allow', 0], ['allow', 0]], '2597/1000'] | [[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5'] | Failed |
| clock regression | [[['deny', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '12/5'] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5'] | Failed |
| small clock step back | [[['deny', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '23/10'] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10'] | Failed |
| oversize cost | [[['never', 0], ['deny', 0], ['deny', 0], ['never', 0]], '3'] | [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0'] | Failed |
| exact boundary after refill | [[['deny', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3501/500'] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500'] | Failed |
| fractional shortfall | [[['deny', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '2203/1000'] | [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000'] | Failed |
| random stream | [[['allow', 0], ['allow', 0], ['deny', 126], ['deny', 581], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 439], ['deny', 220]], '64/25'] | [[['allow', 0], ['allow', 0], ['deny', 126], ['deny', 581], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 439], ['deny', 220]], '64/25'] | Passed |
SHA-256 / a29f922b4e8d1520ca75af6f040ea89cf752c5b7a90e6528cf011aa4671425f8
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
C = x['capacity']
rate = x['rate']
tokens = Fraction(C)
last = 0
out = []
for t, cost in x['requests']:
elapsed = max(0, t - last)
tokens = min(Fraction(C), tokens + Fraction(elapsed * rate, 1000))
last = max(last, t)
if cost > C:
out.append(['never', 0])
elif round(tokens) >= cost:
tokens -= cost
out.append(['allow', 0])
else:
out.append(['deny', math.ceil((cost - tokens) * 1000 / rate)])
return [out, str(tokens)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst then refill',
{'capacity': 5,
'rate': 2,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [100, 1], [1000, 2], [1401, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 400],
['allow', 0],
['deny', 99]],
'401/500']],
['idle overflow capped',
{'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10001, 1], [10200, 1]]},
[[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']],
['clock regression',
{'capacity': 6,
'rate': 1,
'requests': [[0, 6], [5000, 1], [3100, 1], [5500, 1], [6000, 1], [6400, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
['small clock step back',
{'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3710, 1], [4000, 1], [4300, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
['oversize cost',
{'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3001, 3], [3001, 5]]},
[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
['exact boundary after refill',
{'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2334, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']],
['fractional shortfall',
{'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [901, 1]]},
[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']],
['random stream',
{'capacity': 4,
'rate': 2,
'requests': [[1025, 1],
[1038, 3],
[1399, 1],
[1944, 3],
[2745, 1],
[2753, 1],
[3169, 1],
[4025, 1],
[4086, 3],
[4305, 3]]},
[[['allow', 0],
['allow', 0],
['deny', 126],
['deny', 581],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 439],
['deny', 220]],
'64/25']]],
[['burst then refill',
{'capacity': 5,
'rate': 2,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [200, 1], [1000, 2], [1402, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 300],
['allow', 0],
['deny', 98]],
'201/250']],
['idle overflow capped',
{'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10002, 1], [10200, 1]]},
[[['allow', 0], ['allow', 0], ['deny', 332], ['deny', 134]], '3/5']],
['clock regression',
{'capacity': 6,
'rate': 1,
'requests': [[0, 6], [5000, 1], [3200, 1], [5500, 1], [6000, 1], [6400, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
['small clock step back',
{'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3720, 1], [4000, 1], [4300, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
['oversize cost',
{'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3002, 3], [3002, 6]]},
[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
['exact boundary after refill',
{'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2668, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '251/250']],
['fractional shortfall',
{'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [902, 1]]},
[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '353/500']],
['random stream',
{'capacity': 4,
'rate': 2,
'requests': [[679, 3],
[889, 1],
[1479, 1],
[1523, 1],
[1681, 1],
[2074, 3],
[2401, 2],
[2669, 3],
[4187, 3],
[4538, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 156],
['allow', 0],
['deny', 1105],
['deny', 278],
['deny', 510],
['allow', 0],
['allow', 0]],
'351/500']]],
[['burst then refill',
{'capacity': 5,
'rate': 2,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [300, 1], [1000, 2], [1403, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 200],
['allow', 0],
['deny', 97]],
'403/500']],
['idle overflow capped',
{'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10003, 1], [10200, 1]]},
[[['allow', 0], ['allow', 0], ['deny', 331], ['deny', 134]], '3/5']],
['clock regression',
{'capacity': 6,
'rate': 1,
'requests': [[0, 6], [5000, 1], [3300, 1], [5500, 1], [6000, 1], [6400, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
['small clock step back',
{'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3730, 1], [4000, 1], [4300, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
['oversize cost',
{'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3003, 3], [3003, 7]]},
[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
['exact boundary after refill',
{'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3002, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1003/500']],
['fractional shortfall',
{'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [903, 1]]},
[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '709/1000']],
['random stream',
{'capacity': 4,
'rate': 2,
'requests': [[476, 2],
[1005, 3],
[1092, 1],
[1140, 2],
[2416, 2],
[2727, 2],
[3540, 3],
[3809, 1],
[3822, 1],
[4130, 1]]},
[[['allow', 0],
['allow', 0],
['deny', 384],
['deny', 836],
['allow', 0],
['deny', 249],
['allow', 0],
['deny', 167],
['deny', 154],
['allow', 0]],
'77/250']]],
[['burst then refill',
{'capacity': 5,
'rate': 2,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [400, 1], [1000, 2], [1404, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 100],
['allow', 0],
['deny', 96]],
'101/125']],
['idle overflow capped',
{'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10004, 1], [10200, 1]]},
[[['allow', 0], ['allow', 0], ['deny', 330], ['deny', 134]], '3/5']],
['clock regression',
{'capacity': 6,
'rate': 1,
'requests': [[0, 6], [5000, 1], [3400, 1], [5500, 1], [6000, 1], [6400, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
['small clock step back',
{'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3740, 1], [4000, 1], [4300, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
['oversize cost',
{'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3004, 3], [3004, 8]]},
[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
['exact boundary after refill',
{'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3336, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '376/125']],
['fractional shortfall',
{'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [904, 1]]},
[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '89/125']],
['random stream',
{'capacity': 4,
'rate': 2,
'requests': [[295, 3],
[481, 2],
[603, 2],
[1079, 3],
[1690, 3],
[1700, 3],
[2433, 3],
[3280, 3],
[4573, 3],
[4680, 3]]},
[[['allow', 0],
['deny', 314],
['deny', 192],
['deny', 216],
['allow', 0],
['deny', 1095],
['deny', 362],
['allow', 0],
['allow', 0],
['deny', 1115]],
'77/100']]],
[['burst then refill',
{'capacity': 5,
'rate': 2,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [500, 1], [1000, 2], [1405, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 500],
['allow', 0]],
'81/100']],
['idle overflow capped',
{'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10005, 1], [10200, 1]]},
[[['allow', 0], ['allow', 0], ['deny', 329], ['deny', 134]], '3/5']],
['clock regression',
{'capacity': 6,
'rate': 1,
'requests': [[0, 6], [5000, 1], [3500, 1], [5500, 1], [6000, 1], [6400, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
['small clock step back',
{'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3750, 1], [4000, 1], [4300, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
['oversize cost',
{'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3005, 3], [3005, 9]]},
[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
['exact boundary after refill',
{'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3670, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '401/100']],
['fractional shortfall',
{'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [905, 1]]},
[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '143/200']],
['random stream',
{'capacity': 4,
'rate': 2,
'requests': [[1144, 3],
[1657, 3],
[1896, 3],
[2302, 2],
[2570, 2],
[3012, 1],
[3025, 1],
[3251, 1],
[4294, 1],
[4860, 2]]},
[[['allow', 0],
['deny', 487],
['deny', 248],
['allow', 0],
['deny', 74],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0]],
'54/125']]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
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 |
|---|---|---|---|
| burst then refill | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 400], ['allow', 0], ['allow', 0]], '-99/500'] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 400], ['allow', 0], ['deny', 99]], '401/500'] | Failed |
| idle overflow capped | [[['allow', 0], ['allow', 0], ['deny', 333], ['allow', 0]], '-2/5'] | [[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5'] | Failed |
| clock regression | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5'] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5'] | Passed |
| small clock step back | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10'] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10'] | Passed |
| oversize cost | [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0'] | [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0'] | Passed |
| exact boundary after refill | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500'] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500'] | Passed |
| fractional shortfall | [[['allow', 0], ['allow', 0], ['deny', 300], ['allow', 0]], '-297/1000'] | [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000'] | Failed |
| random stream | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 1081], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 939], ['deny', 720]], '39/25'] | [[['allow', 0], ['allow', 0], ['deny', 126], ['deny', 581], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 439], ['deny', 220]], '64/25'] | Failed |
SHA-256 / 72d2132bb554e3d0c48657e5057fd063370031520762ff7614b4087b726f2af3
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
C = x['capacity']
rate = x['rate']
tokens = Fraction(C)
last = 0
out = []
for t, cost in x['requests']:
elapsed = max(0, t - last)
tokens = min(Fraction(C), tokens + Fraction(elapsed * rate, 1000))
last = max(last, t)
if cost > C:
out.append(['never', 0])
elif tokens >= cost:
tokens -= cost
out.append(['allow', 0])
else:
out.append(['deny', math.ceil((cost - tokens) * 1000 / rate)])
return [out, str(tokens)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst then refill',
{'capacity': 5,
'rate': 2,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [100, 1], [1000, 2], [1401, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 400],
['allow', 0],
['deny', 99]],
'401/500']],
['idle overflow capped',
{'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10001, 1], [10200, 1]]},
[[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']],
['clock regression',
{'capacity': 6,
'rate': 1,
'requests': [[0, 6], [5000, 1], [3100, 1], [5500, 1], [6000, 1], [6400, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
['small clock step back',
{'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3710, 1], [4000, 1], [4300, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
['oversize cost',
{'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3001, 3], [3001, 5]]},
[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
['exact boundary after refill',
{'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2334, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']],
['fractional shortfall',
{'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [901, 1]]},
[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']],
['random stream',
{'capacity': 4,
'rate': 2,
'requests': [[1025, 1],
[1038, 3],
[1399, 1],
[1944, 3],
[2745, 1],
[2753, 1],
[3169, 1],
[4025, 1],
[4086, 3],
[4305, 3]]},
[[['allow', 0],
['allow', 0],
['deny', 126],
['deny', 581],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 439],
['deny', 220]],
'64/25']]],
[['burst then refill',
{'capacity': 5,
'rate': 2,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [200, 1], [1000, 2], [1402, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 300],
['allow', 0],
['deny', 98]],
'201/250']],
['idle overflow capped',
{'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10002, 1], [10200, 1]]},
[[['allow', 0], ['allow', 0], ['deny', 332], ['deny', 134]], '3/5']],
['clock regression',
{'capacity': 6,
'rate': 1,
'requests': [[0, 6], [5000, 1], [3200, 1], [5500, 1], [6000, 1], [6400, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
['small clock step back',
{'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3720, 1], [4000, 1], [4300, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
['oversize cost',
{'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3002, 3], [3002, 6]]},
[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
['exact boundary after refill',
{'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2668, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '251/250']],
['fractional shortfall',
{'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [902, 1]]},
[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '353/500']],
['random stream',
{'capacity': 4,
'rate': 2,
'requests': [[679, 3],
[889, 1],
[1479, 1],
[1523, 1],
[1681, 1],
[2074, 3],
[2401, 2],
[2669, 3],
[4187, 3],
[4538, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 156],
['allow', 0],
['deny', 1105],
['deny', 278],
['deny', 510],
['allow', 0],
['allow', 0]],
'351/500']]],
[['burst then refill',
{'capacity': 5,
'rate': 2,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [300, 1], [1000, 2], [1403, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 200],
['allow', 0],
['deny', 97]],
'403/500']],
['idle overflow capped',
{'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10003, 1], [10200, 1]]},
[[['allow', 0], ['allow', 0], ['deny', 331], ['deny', 134]], '3/5']],
['clock regression',
{'capacity': 6,
'rate': 1,
'requests': [[0, 6], [5000, 1], [3300, 1], [5500, 1], [6000, 1], [6400, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
['small clock step back',
{'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3730, 1], [4000, 1], [4300, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
['oversize cost',
{'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3003, 3], [3003, 7]]},
[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
['exact boundary after refill',
{'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3002, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1003/500']],
['fractional shortfall',
{'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [903, 1]]},
[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '709/1000']],
['random stream',
{'capacity': 4,
'rate': 2,
'requests': [[476, 2],
[1005, 3],
[1092, 1],
[1140, 2],
[2416, 2],
[2727, 2],
[3540, 3],
[3809, 1],
[3822, 1],
[4130, 1]]},
[[['allow', 0],
['allow', 0],
['deny', 384],
['deny', 836],
['allow', 0],
['deny', 249],
['allow', 0],
['deny', 167],
['deny', 154],
['allow', 0]],
'77/250']]],
[['burst then refill',
{'capacity': 5,
'rate': 2,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [400, 1], [1000, 2], [1404, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 100],
['allow', 0],
['deny', 96]],
'101/125']],
['idle overflow capped',
{'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10004, 1], [10200, 1]]},
[[['allow', 0], ['allow', 0], ['deny', 330], ['deny', 134]], '3/5']],
['clock regression',
{'capacity': 6,
'rate': 1,
'requests': [[0, 6], [5000, 1], [3400, 1], [5500, 1], [6000, 1], [6400, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
['small clock step back',
{'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3740, 1], [4000, 1], [4300, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
['oversize cost',
{'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3004, 3], [3004, 8]]},
[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
['exact boundary after refill',
{'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3336, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '376/125']],
['fractional shortfall',
{'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [904, 1]]},
[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '89/125']],
['random stream',
{'capacity': 4,
'rate': 2,
'requests': [[295, 3],
[481, 2],
[603, 2],
[1079, 3],
[1690, 3],
[1700, 3],
[2433, 3],
[3280, 3],
[4573, 3],
[4680, 3]]},
[[['allow', 0],
['deny', 314],
['deny', 192],
['deny', 216],
['allow', 0],
['deny', 1095],
['deny', 362],
['allow', 0],
['allow', 0],
['deny', 1115]],
'77/100']]],
[['burst then refill',
{'capacity': 5,
'rate': 2,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [500, 1], [1000, 2], [1405, 1]]},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 500],
['allow', 0]],
'81/100']],
['idle overflow capped',
{'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10005, 1], [10200, 1]]},
[[['allow', 0], ['allow', 0], ['deny', 329], ['deny', 134]], '3/5']],
['clock regression',
{'capacity': 6,
'rate': 1,
'requests': [[0, 6], [5000, 1], [3500, 1], [5500, 1], [6000, 1], [6400, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
['small clock step back',
{'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3750, 1], [4000, 1], [4300, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
['oversize cost',
{'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3005, 3], [3005, 9]]},
[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
['exact boundary after refill',
{'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3670, 1]]},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '401/100']],
['fractional shortfall',
{'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [905, 1]]},
[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '143/200']],
['random stream',
{'capacity': 4,
'rate': 2,
'requests': [[1144, 3],
[1657, 3],
[1896, 3],
[2302, 2],
[2570, 2],
[3012, 1],
[3025, 1],
[3251, 1],
[4294, 1],
[4860, 2]]},
[[['allow', 0],
['deny', 487],
['deny', 248],
['allow', 0],
['deny', 74],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0]],
'54/125']]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
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 |
|---|---|---|---|
| burst then refill | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 400], ['allow', 0], ['deny', 99]], '401/500'] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 400], ['allow', 0], ['deny', 99]], '401/500'] | Passed |
| idle overflow capped | [[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5'] | [[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5'] | Passed |
| clock regression | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5'] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5'] | Passed |
| small clock step back | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10'] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10'] | Passed |
| oversize cost | [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0'] | [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0'] | Passed |
| exact boundary after refill | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500'] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500'] | Passed |
| fractional shortfall | [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000'] | [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000'] | Passed |
| random stream | [[['allow', 0], ['allow', 0], ['deny', 126], ['deny', 581], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 439], ['deny', 220]], '64/25'] | [[['allow', 0], ['allow', 0], ['deny', 126], ['deny', 581], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 439], ['deny', 220]], '64/25'] | Passed |
SHA-256 / 2612351e5227e74d969039fe7a26772663589e8216880ec6294649255dde1d2c
Verification & scope
A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. 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:48:46.850069+00:00.
Case digest / 43c109021afb9507e93dfb945f4fc294ecc4a17bcf6f093f8a3e497d8a932a6f