FA-73391 / Rate limiter algorithms / Open access
Generic cell rate algorithm limiter: multi-unit request charged as one · case 01
A request for several units consumes only one emission interval, multiplying the admitted rate.
ROOT CAUSE
The TAT increment ignores the requested quantity.
VERIFIED REPAIR
Advance by q*T for a request of quantity q.
Unsuccessful approach: Treating the first unit as free under-charges every request by one interval.
Case contract
Input {period_ms T, burst B, requests [[t, quantity]]}. State TAT starts at 0. A quantity above B is ["never", 0, 0]. Otherwise tat = max(TAT, t) and new_tat = tat + q*T; the request is allowed iff new_tat - t <= B*T, in which case TAT = new_tat and remaining = floor((B*T - (TAT - t))/T). A denied request leaves TAT unchanged and reports retry_after = new_tat - B*T - t and remaining floor((B*T - (tat - t))/T). Return [[decision, retry_after, remaining]].
Why this case matters
GCRA limiters store a single theoretical-arrival timestamp per key; every decision and header value is derived from it, so small formula errors leak bursts or starve clients.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
T = x['period_ms']
B = x['burst']
TAT = 0
out = []
for t, q in x['requests']:
if q > B:
out.append(['never', 0, 0])
continue
tat = max(TAT, t)
new_tat = tat + T
if new_tat - t <= B * T:
TAT = new_tat
out.append(['allow', 0, (B * T - (TAT - t)) // T])
else:
out.append(['deny', new_tat - B * T - t, (B * T - (tat - t)) // T])
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst of five',
{'burst': 5,
'period_ms': 100,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [101, 1], [250, 1]]},
[['allow', 0, 4],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['idle credit bounded',
{'burst': 3,
'period_ms': 50,
'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10010, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 50, 0],
['deny', 40, 0]]],
['denied requests do not push tat',
{'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [101, 1], [200, 1]]},
[['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['multi-unit request',
{'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [41, 2], [5, 5]]},
[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
['exact tolerance edge',
{'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [201, 1]]},
[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
['random traffic',
{'burst': 4,
'period_ms': 100,
'requests': [[8, 2],
[57, 1],
[84, 2],
[163, 2],
[383, 1],
[525, 2],
[624, 2],
[997, 1],
[1402, 2],
[1869, 2]]},
[['allow', 0, 2],
['allow', 0, 1],
['deny', 24, 1],
['allow', 0, 0],
['allow', 0, 1],
['allow', 0, 1],
['allow', 0, 0],
['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 2]]]],
[['burst of five',
{'burst': 5,
'period_ms': 100,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [102, 1], [250, 1]]},
[['allow', 0, 4],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['idle credit bounded',
{'burst': 3,
'period_ms': 50,
'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10020, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 50, 0],
['deny', 30, 0]]],
['denied requests do not push tat',
{'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [102, 1], [200, 1]]},
[['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['multi-unit request',
{'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [42, 2], [10, 5]]},
[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
['exact tolerance edge',
{'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [202, 1]]},
[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
['random traffic',
{'burst': 4,
'period_ms': 100,
'requests': [[67, 2],
[137, 1],
[249, 1],
[594, 1],
[681, 2],
[826, 1],
[1250, 1],
[1428, 1],
[1433, 2],
[1483, 2]]},
[['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 1],
['allow', 0, 3],
['allow', 0, 1],
['allow', 0, 2],
['allow', 0, 3],
['allow', 0, 3],
['allow', 0, 1],
['deny', 45, 1]]]],
[['burst of five',
{'burst': 5,
'period_ms': 100,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [103, 1], [250, 1]]},
[['allow', 0, 4],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['idle credit bounded',
{'burst': 3,
'period_ms': 50,
'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10030, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 50, 0],
['deny', 20, 0]]],
['denied requests do not push tat',
{'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [103, 1], [200, 1]]},
[['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['multi-unit request',
{'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [43, 2], [15, 5]]},
[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
['exact tolerance edge',
{'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [203, 1]]},
[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
['random traffic',
{'burst': 4,
'period_ms': 100,
'requests': [[56, 1],
[339, 2],
[932, 1],
[1203, 2],
[1327, 2],
[1505, 1],
[1614, 2],
[1774, 2],
[1930, 1],
[1938, 2]]},
[['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['allow', 0, 1],
['deny', 65, 1]]]],
[['burst of five',
{'burst': 5,
'period_ms': 100,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [104, 1], [250, 1]]},
[['allow', 0, 4],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['idle credit bounded',
{'burst': 3,
'period_ms': 50,
'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10040, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 50, 0],
['deny', 10, 0]]],
['denied requests do not push tat',
{'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [104, 1], [200, 1]]},
[['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['multi-unit request',
{'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [44, 2], [20, 5]]},
[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
['exact tolerance edge',
{'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [204, 1]]},
[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
['random traffic',
{'burst': 4,
'period_ms': 100,
'requests': [[415, 1],
[479, 1],
[592, 1],
[602, 2],
[683, 2],
[973, 2],
[1658, 1],
[1708, 2],
[1784, 1],
[1789, 2]]},
[['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 0],
['deny', 32, 1],
['allow', 0, 2],
['allow', 0, 3],
['allow', 0, 1],
['allow', 0, 1],
['deny', 69, 1]]]],
[['burst of five',
{'burst': 5,
'period_ms': 100,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [105, 1], [250, 1]]},
[['allow', 0, 4],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['idle credit bounded',
{'burst': 3,
'period_ms': 50,
'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10050, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 50, 0],
['allow', 0, 0]]],
['denied requests do not push tat',
{'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [105, 1], [200, 1]]},
[['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['multi-unit request',
{'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [45, 2], [25, 5]]},
[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
['exact tolerance edge',
{'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [205, 1]]},
[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
['random traffic',
{'burst': 4,
'period_ms': 100,
'requests': [[293, 2],
[620, 2],
[635, 1],
[1275, 2],
[1525, 2],
[1565, 1],
[1595, 2],
[1614, 1],
[1806, 2],
[1874, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['deny', 30, 1],
['allow', 0, 0],
['allow', 0, 0],
['allow', 0, 0]]]]]
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 of five | [['allow', 0, 4], ['allow', 0, 3], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]] | [['allow', 0, 4], ['allow', 0, 3], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]] | Passed |
| idle credit bounded | [['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 50, 0], ['deny', 40, 0]] | [['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 50, 0], ['deny', 40, 0]] | Passed |
| denied requests do not push tat | [['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]] | [['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]] | Passed |
| multi-unit request | [['allow', 0, 3], ['allow', 0, 2], ['allow', 0, 3], ['never', 0, 0]] | [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]] | Failed |
| exact tolerance edge | [['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 1]] | [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]] | Failed |
| random traffic | [['allow', 0, 3], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 1], ['allow', 0, 2], ['allow', 0, 3], ['allow', 0, 2], ['allow', 0, 3], ['allow', 0, 3], ['allow', 0, 3]] | [['allow', 0, 2], ['allow', 0, 1], ['deny', 24, 1], ['allow', 0, 0], ['allow', 0, 1], ['allow', 0, 1], ['allow', 0, 0], ['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 2]] | Failed |
SHA-256 / 78ab9e045a80d62445209b6f4498c6406b640c0481c2b0aa3a86767d8a5a9285
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
T = x['period_ms']
B = x['burst']
TAT = 0
out = []
for t, q in x['requests']:
if q > B:
out.append(['never', 0, 0])
continue
tat = max(TAT, t)
new_tat = tat + (q - 1) * T
if new_tat - t <= B * T:
TAT = new_tat
out.append(['allow', 0, (B * T - (TAT - t)) // T])
else:
out.append(['deny', new_tat - B * T - t, (B * T - (tat - t)) // T])
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst of five',
{'burst': 5,
'period_ms': 100,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [101, 1], [250, 1]]},
[['allow', 0, 4],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['idle credit bounded',
{'burst': 3,
'period_ms': 50,
'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10010, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 50, 0],
['deny', 40, 0]]],
['denied requests do not push tat',
{'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [101, 1], [200, 1]]},
[['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['multi-unit request',
{'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [41, 2], [5, 5]]},
[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
['exact tolerance edge',
{'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [201, 1]]},
[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
['random traffic',
{'burst': 4,
'period_ms': 100,
'requests': [[8, 2],
[57, 1],
[84, 2],
[163, 2],
[383, 1],
[525, 2],
[624, 2],
[997, 1],
[1402, 2],
[1869, 2]]},
[['allow', 0, 2],
['allow', 0, 1],
['deny', 24, 1],
['allow', 0, 0],
['allow', 0, 1],
['allow', 0, 1],
['allow', 0, 0],
['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 2]]]],
[['burst of five',
{'burst': 5,
'period_ms': 100,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [102, 1], [250, 1]]},
[['allow', 0, 4],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['idle credit bounded',
{'burst': 3,
'period_ms': 50,
'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10020, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 50, 0],
['deny', 30, 0]]],
['denied requests do not push tat',
{'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [102, 1], [200, 1]]},
[['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['multi-unit request',
{'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [42, 2], [10, 5]]},
[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
['exact tolerance edge',
{'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [202, 1]]},
[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
['random traffic',
{'burst': 4,
'period_ms': 100,
'requests': [[67, 2],
[137, 1],
[249, 1],
[594, 1],
[681, 2],
[826, 1],
[1250, 1],
[1428, 1],
[1433, 2],
[1483, 2]]},
[['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 1],
['allow', 0, 3],
['allow', 0, 1],
['allow', 0, 2],
['allow', 0, 3],
['allow', 0, 3],
['allow', 0, 1],
['deny', 45, 1]]]],
[['burst of five',
{'burst': 5,
'period_ms': 100,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [103, 1], [250, 1]]},
[['allow', 0, 4],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['idle credit bounded',
{'burst': 3,
'period_ms': 50,
'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10030, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 50, 0],
['deny', 20, 0]]],
['denied requests do not push tat',
{'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [103, 1], [200, 1]]},
[['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['multi-unit request',
{'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [43, 2], [15, 5]]},
[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
['exact tolerance edge',
{'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [203, 1]]},
[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
['random traffic',
{'burst': 4,
'period_ms': 100,
'requests': [[56, 1],
[339, 2],
[932, 1],
[1203, 2],
[1327, 2],
[1505, 1],
[1614, 2],
[1774, 2],
[1930, 1],
[1938, 2]]},
[['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['allow', 0, 1],
['deny', 65, 1]]]],
[['burst of five',
{'burst': 5,
'period_ms': 100,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [104, 1], [250, 1]]},
[['allow', 0, 4],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['idle credit bounded',
{'burst': 3,
'period_ms': 50,
'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10040, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 50, 0],
['deny', 10, 0]]],
['denied requests do not push tat',
{'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [104, 1], [200, 1]]},
[['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['multi-unit request',
{'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [44, 2], [20, 5]]},
[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
['exact tolerance edge',
{'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [204, 1]]},
[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
['random traffic',
{'burst': 4,
'period_ms': 100,
'requests': [[415, 1],
[479, 1],
[592, 1],
[602, 2],
[683, 2],
[973, 2],
[1658, 1],
[1708, 2],
[1784, 1],
[1789, 2]]},
[['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 0],
['deny', 32, 1],
['allow', 0, 2],
['allow', 0, 3],
['allow', 0, 1],
['allow', 0, 1],
['deny', 69, 1]]]],
[['burst of five',
{'burst': 5,
'period_ms': 100,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [105, 1], [250, 1]]},
[['allow', 0, 4],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['idle credit bounded',
{'burst': 3,
'period_ms': 50,
'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10050, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 50, 0],
['allow', 0, 0]]],
['denied requests do not push tat',
{'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [105, 1], [200, 1]]},
[['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['multi-unit request',
{'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [45, 2], [25, 5]]},
[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
['exact tolerance edge',
{'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [205, 1]]},
[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
['random traffic',
{'burst': 4,
'period_ms': 100,
'requests': [[293, 2],
[620, 2],
[635, 1],
[1275, 2],
[1525, 2],
[1565, 1],
[1595, 2],
[1614, 1],
[1806, 2],
[1874, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['deny', 30, 1],
['allow', 0, 0],
['allow', 0, 0],
['allow', 0, 0]]]]]
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 of five | [['allow', 0, 5], ['allow', 0, 5], ['allow', 0, 5], ['allow', 0, 5], ['allow', 0, 5], ['allow', 0, 5], ['allow', 0, 5], ['allow', 0, 5]] | [['allow', 0, 4], ['allow', 0, 3], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]] | Failed |
| idle credit bounded | [['allow', 0, 3], ['allow', 0, 3], ['allow', 0, 3], ['allow', 0, 3], ['allow', 0, 3], ['allow', 0, 3]] | [['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 50, 0], ['deny', 40, 0]] | Failed |
| denied requests do not push tat | [['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 2]] | [['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]] | Failed |
| multi-unit request | [['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 2], ['never', 0, 0]] | [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]] | Failed |
| exact tolerance edge | [['allow', 0, 1], ['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 3]] | [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]] | Failed |
| random traffic | [['allow', 0, 3], ['allow', 0, 3], ['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 4], ['allow', 0, 3], ['allow', 0, 2], ['allow', 0, 4], ['allow', 0, 3], ['allow', 0, 3]] | [['allow', 0, 2], ['allow', 0, 1], ['deny', 24, 1], ['allow', 0, 0], ['allow', 0, 1], ['allow', 0, 1], ['allow', 0, 0], ['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 2]] | Failed |
SHA-256 / 4ad72142dca14051fa4d4411541ffecbb7447921648c9be7090f4baead92a0b5
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
T = x['period_ms']
B = x['burst']
TAT = 0
out = []
for t, q in x['requests']:
if q > B:
out.append(['never', 0, 0])
continue
tat = max(TAT, t)
new_tat = tat + q * T
if new_tat - t <= B * T:
TAT = new_tat
out.append(['allow', 0, (B * T - (TAT - t)) // T])
else:
out.append(['deny', new_tat - B * T - t, (B * T - (tat - t)) // T])
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst of five',
{'burst': 5,
'period_ms': 100,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [101, 1], [250, 1]]},
[['allow', 0, 4],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['idle credit bounded',
{'burst': 3,
'period_ms': 50,
'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10010, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 50, 0],
['deny', 40, 0]]],
['denied requests do not push tat',
{'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [101, 1], [200, 1]]},
[['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['multi-unit request',
{'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [41, 2], [5, 5]]},
[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
['exact tolerance edge',
{'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [201, 1]]},
[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
['random traffic',
{'burst': 4,
'period_ms': 100,
'requests': [[8, 2],
[57, 1],
[84, 2],
[163, 2],
[383, 1],
[525, 2],
[624, 2],
[997, 1],
[1402, 2],
[1869, 2]]},
[['allow', 0, 2],
['allow', 0, 1],
['deny', 24, 1],
['allow', 0, 0],
['allow', 0, 1],
['allow', 0, 1],
['allow', 0, 0],
['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 2]]]],
[['burst of five',
{'burst': 5,
'period_ms': 100,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [102, 1], [250, 1]]},
[['allow', 0, 4],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['idle credit bounded',
{'burst': 3,
'period_ms': 50,
'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10020, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 50, 0],
['deny', 30, 0]]],
['denied requests do not push tat',
{'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [102, 1], [200, 1]]},
[['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['multi-unit request',
{'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [42, 2], [10, 5]]},
[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
['exact tolerance edge',
{'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [202, 1]]},
[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
['random traffic',
{'burst': 4,
'period_ms': 100,
'requests': [[67, 2],
[137, 1],
[249, 1],
[594, 1],
[681, 2],
[826, 1],
[1250, 1],
[1428, 1],
[1433, 2],
[1483, 2]]},
[['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 1],
['allow', 0, 3],
['allow', 0, 1],
['allow', 0, 2],
['allow', 0, 3],
['allow', 0, 3],
['allow', 0, 1],
['deny', 45, 1]]]],
[['burst of five',
{'burst': 5,
'period_ms': 100,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [103, 1], [250, 1]]},
[['allow', 0, 4],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['idle credit bounded',
{'burst': 3,
'period_ms': 50,
'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10030, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 50, 0],
['deny', 20, 0]]],
['denied requests do not push tat',
{'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [103, 1], [200, 1]]},
[['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['multi-unit request',
{'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [43, 2], [15, 5]]},
[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
['exact tolerance edge',
{'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [203, 1]]},
[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
['random traffic',
{'burst': 4,
'period_ms': 100,
'requests': [[56, 1],
[339, 2],
[932, 1],
[1203, 2],
[1327, 2],
[1505, 1],
[1614, 2],
[1774, 2],
[1930, 1],
[1938, 2]]},
[['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['allow', 0, 1],
['deny', 65, 1]]]],
[['burst of five',
{'burst': 5,
'period_ms': 100,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [104, 1], [250, 1]]},
[['allow', 0, 4],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['idle credit bounded',
{'burst': 3,
'period_ms': 50,
'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10040, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 50, 0],
['deny', 10, 0]]],
['denied requests do not push tat',
{'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [104, 1], [200, 1]]},
[['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['multi-unit request',
{'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [44, 2], [20, 5]]},
[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
['exact tolerance edge',
{'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [204, 1]]},
[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
['random traffic',
{'burst': 4,
'period_ms': 100,
'requests': [[415, 1],
[479, 1],
[592, 1],
[602, 2],
[683, 2],
[973, 2],
[1658, 1],
[1708, 2],
[1784, 1],
[1789, 2]]},
[['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 0],
['deny', 32, 1],
['allow', 0, 2],
['allow', 0, 3],
['allow', 0, 1],
['allow', 0, 1],
['deny', 69, 1]]]],
[['burst of five',
{'burst': 5,
'period_ms': 100,
'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [105, 1], [250, 1]]},
[['allow', 0, 4],
['allow', 0, 3],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['idle credit bounded',
{'burst': 3,
'period_ms': 50,
'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10050, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 0],
['deny', 50, 0],
['allow', 0, 0]]],
['denied requests do not push tat',
{'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [105, 1], [200, 1]]},
[['allow', 0, 1],
['allow', 0, 0],
['deny', 100, 0],
['deny', 100, 0],
['allow', 0, 0],
['allow', 0, 0]]],
['multi-unit request',
{'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [45, 2], [25, 5]]},
[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
['exact tolerance edge',
{'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [205, 1]]},
[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
['random traffic',
{'burst': 4,
'period_ms': 100,
'requests': [[293, 2],
[620, 2],
[635, 1],
[1275, 2],
[1525, 2],
[1565, 1],
[1595, 2],
[1614, 1],
[1806, 2],
[1874, 1]]},
[['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['allow', 0, 2],
['allow', 0, 2],
['allow', 0, 1],
['deny', 30, 1],
['allow', 0, 0],
['allow', 0, 0],
['allow', 0, 0]]]]]
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 of five | [['allow', 0, 4], ['allow', 0, 3], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]] | [['allow', 0, 4], ['allow', 0, 3], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]] | Passed |
| idle credit bounded | [['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 50, 0], ['deny', 40, 0]] | [['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 50, 0], ['deny', 40, 0]] | Passed |
| denied requests do not push tat | [['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]] | [['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]] | Passed |
| multi-unit request | [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]] | [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]] | Passed |
| exact tolerance edge | [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]] | [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]] | Passed |
| random traffic | [['allow', 0, 2], ['allow', 0, 1], ['deny', 24, 1], ['allow', 0, 0], ['allow', 0, 1], ['allow', 0, 1], ['allow', 0, 0], ['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 2]] | [['allow', 0, 2], ['allow', 0, 1], ['deny', 24, 1], ['allow', 0, 0], ['allow', 0, 1], ['allow', 0, 1], ['allow', 0, 0], ['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 2]] | Passed |
SHA-256 / 4813819e5702a7ff6ba793d3d1f2ce7cee700f3f6586f8372b17a723b314ce6d
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:47.174721+00:00.
Case digest / f8f71b81bb5699a0bf60a60abbc381e5acd4f7ac821cf7e9a511ffbb079af957