FA-73456 / Rate limiter algorithms / Open access
Sliding-window log limiter: newest entry stored at the front · case 01
The retry hint is computed from the newest request instead of the oldest.
ROOT CAUSE
Admitted timestamps are inserted at the front, so log[0] is the newest entry.
VERIFIED REPAIR
Append admitted timestamps so the log stays oldest first.
Unsuccessful approach: Sorting in descending order keeps the newest entry at the front.
Case contract
Input {limit, window_ms, requests [t]}. The limiter clock is now = max of all timestamps seen, so a late request is evaluated at now. Log entries with s <= now - W are pruned. Allow while fewer than limit entries remain and log now; denials are not logged and report retry = oldest + W - now. Return [[decision, retry]], final log].
Why this case matters
Sliding logs give exact rolling-window limits for login attempts and expensive endpoints; pruning and logging rules decide exactly when a client may retry.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
L = x['limit']
W = x['window_ms']
log = []
now = None
out = []
for t in x['requests']:
now = t if now is None else max(now, t)
log = [s for s in log if s > now - W]
if len(log) < L:
log.insert(0, now)
out.append(['allow', 0])
else:
out.append(['deny', log[0] + W - now])
return [out, log]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1011, 1012], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 988]], [1000, 1011]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1051, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1051, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 101, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 701, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 299],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [737, 924, 1194, 1231, 1362, 1408, 1509, 1520, 1559, 1643, 1776, 2570],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 306],
['deny', 175],
['deny', 129],
['deny', 28],
['deny', 17],
['allow', 0],
['deny', 81],
['allow', 0],
['allow', 0]],
[1776, 2570]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 151, 251], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1012, 1013], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 987]], [1000, 1012]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1052, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1052, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 102, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 702, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 298],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [203, 368, 954, 964, 1092, 1537, 1711, 1845, 1983, 2392, 2599, 2816],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 39],
['allow', 0],
['allow', 0],
['deny', 43],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 46],
['allow', 0]],
[2392, 2816]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 152, 252], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 48], ['allow', 0]], [252]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1013, 1014], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 986]], [1000, 1013]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1053, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1053, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 103, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 703, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 297],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [659, 794, 1414, 1446, 1627, 2009, 2196, 2262, 2536, 2557, 2734, 2819],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 13],
['allow', 0],
['allow', 0],
['deny', 18],
['allow', 0],
['allow', 0],
['deny', 252],
['deny', 75],
['allow', 0]],
[2262, 2536, 2819]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 153, 253], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 47], ['allow', 0]], [253]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1014, 1015], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 985]], [1000, 1014]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1054, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1054, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 104, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 704, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 296],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [81, 344, 553, 1450, 1591, 1736, 1934, 2492, 2556, 2664, 2677, 2831],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 316],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 615],
['deny', 461]],
[2492, 2556, 2664]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 154, 254], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 46], ['allow', 0]], [254]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1015, 1016], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 984]], [1000, 1015]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1055, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1055, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 105, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 705, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 295],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [85, 117, 140, 309, 683, 1093, 2036, 2231, 2349, 2416, 2706, 2868],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 576],
['deny', 202],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 420],
['deny', 130],
['allow', 0]],
[2231, 2349, 2868]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 155, 255], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 45], ['allow', 0]], [255]]]]]
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 |
|---|---|---|---|
| exact expiry boundary | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 999]], [1011, 1000]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 988]], [1000, 1011]] | Failed |
| denied requests not logged | [[['allow', 0], ['allow', 0], ['deny', 900], ['deny', 800], ['allow', 0], ['allow', 0]], [1150, 1051]] | [[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]], [1051, 1150]] | Failed |
| late timestamp uses monotonic now | [[['allow', 0], ['allow', 0], ['deny', 500], ['allow', 0], ['deny', 495], ['allow', 0]], [960, 900]] | [[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]], [900, 960]] | Failed |
| retry after oldest expires | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 899], ['deny', 601], ['allow', 0], ['deny', 999]], [1000, 600, 300]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 299], ['deny', 1], ['allow', 0], ['deny', 299]], [300, 600, 1000]] | Failed |
| random traffic | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 763], ['deny', 632], ['deny', 586], ['deny', 485], ['deny', 474], ['allow', 0], ['deny', 716], ['allow', 0], ['allow', 0]], [2570, 1776]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 306], ['deny', 175], ['deny', 129], ['deny', 28], ['deny', 17], ['allow', 0], ['deny', 81], ['allow', 0], ['allow', 0]], [1776, 2570]] | Failed |
| single slot | [[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]] | [[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]] | Passed |
SHA-256 / c9890948871f547f8774cd768ae5b81c761238cc4c38e661ec2f2d55ae6332cc
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
L = x['limit']
W = x['window_ms']
log = []
now = None
out = []
for t in x['requests']:
now = t if now is None else max(now, t)
log = [s for s in log if s > now - W]
if len(log) < L:
log.insert(0, now)
log.sort(reverse=True)
out.append(['allow', 0])
else:
out.append(['deny', log[0] + W - now])
return [out, log]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1011, 1012], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 988]], [1000, 1011]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1051, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1051, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 101, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 701, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 299],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [737, 924, 1194, 1231, 1362, 1408, 1509, 1520, 1559, 1643, 1776, 2570],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 306],
['deny', 175],
['deny', 129],
['deny', 28],
['deny', 17],
['allow', 0],
['deny', 81],
['allow', 0],
['allow', 0]],
[1776, 2570]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 151, 251], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1012, 1013], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 987]], [1000, 1012]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1052, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1052, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 102, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 702, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 298],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [203, 368, 954, 964, 1092, 1537, 1711, 1845, 1983, 2392, 2599, 2816],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 39],
['allow', 0],
['allow', 0],
['deny', 43],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 46],
['allow', 0]],
[2392, 2816]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 152, 252], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 48], ['allow', 0]], [252]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1013, 1014], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 986]], [1000, 1013]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1053, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1053, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 103, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 703, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 297],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [659, 794, 1414, 1446, 1627, 2009, 2196, 2262, 2536, 2557, 2734, 2819],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 13],
['allow', 0],
['allow', 0],
['deny', 18],
['allow', 0],
['allow', 0],
['deny', 252],
['deny', 75],
['allow', 0]],
[2262, 2536, 2819]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 153, 253], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 47], ['allow', 0]], [253]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1014, 1015], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 985]], [1000, 1014]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1054, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1054, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 104, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 704, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 296],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [81, 344, 553, 1450, 1591, 1736, 1934, 2492, 2556, 2664, 2677, 2831],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 316],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 615],
['deny', 461]],
[2492, 2556, 2664]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 154, 254], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 46], ['allow', 0]], [254]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1015, 1016], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 984]], [1000, 1015]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1055, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1055, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 105, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 705, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 295],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [85, 117, 140, 309, 683, 1093, 2036, 2231, 2349, 2416, 2706, 2868],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 576],
['deny', 202],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 420],
['deny', 130],
['allow', 0]],
[2231, 2349, 2868]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 155, 255], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 45], ['allow', 0]], [255]]]]]
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 |
|---|---|---|---|
| exact expiry boundary | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 999]], [1011, 1000]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 988]], [1000, 1011]] | Failed |
| denied requests not logged | [[['allow', 0], ['allow', 0], ['deny', 900], ['deny', 800], ['allow', 0], ['allow', 0]], [1150, 1051]] | [[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]], [1051, 1150]] | Failed |
| late timestamp uses monotonic now | [[['allow', 0], ['allow', 0], ['deny', 500], ['allow', 0], ['deny', 495], ['allow', 0]], [960, 900]] | [[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]], [900, 960]] | Failed |
| retry after oldest expires | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 899], ['deny', 601], ['allow', 0], ['deny', 999]], [1000, 600, 300]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 299], ['deny', 1], ['allow', 0], ['deny', 299]], [300, 600, 1000]] | Failed |
| random traffic | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 763], ['deny', 632], ['deny', 586], ['deny', 485], ['deny', 474], ['allow', 0], ['deny', 716], ['allow', 0], ['allow', 0]], [2570, 1776]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 306], ['deny', 175], ['deny', 129], ['deny', 28], ['deny', 17], ['allow', 0], ['deny', 81], ['allow', 0], ['allow', 0]], [1776, 2570]] | Failed |
| single slot | [[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]] | [[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]] | Passed |
SHA-256 / 0ccf507ec4a220085ee91cbef5d299d6317a5fbb4f4e06b89f2ec0c3a36890c4
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
L = x['limit']
W = x['window_ms']
log = []
now = None
out = []
for t in x['requests']:
now = t if now is None else max(now, t)
log = [s for s in log if s > now - W]
if len(log) < L:
log.append(now)
out.append(['allow', 0])
else:
out.append(['deny', log[0] + W - now])
return [out, log]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1011, 1012], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 988]], [1000, 1011]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1051, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1051, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 101, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 701, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 299],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [737, 924, 1194, 1231, 1362, 1408, 1509, 1520, 1559, 1643, 1776, 2570],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 306],
['deny', 175],
['deny', 129],
['deny', 28],
['deny', 17],
['allow', 0],
['deny', 81],
['allow', 0],
['allow', 0]],
[1776, 2570]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 151, 251], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1012, 1013], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 987]], [1000, 1012]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1052, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1052, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 102, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 702, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 298],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [203, 368, 954, 964, 1092, 1537, 1711, 1845, 1983, 2392, 2599, 2816],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 39],
['allow', 0],
['allow', 0],
['deny', 43],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 46],
['allow', 0]],
[2392, 2816]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 152, 252], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 48], ['allow', 0]], [252]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1013, 1014], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 986]], [1000, 1013]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1053, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1053, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 103, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 703, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 297],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [659, 794, 1414, 1446, 1627, 2009, 2196, 2262, 2536, 2557, 2734, 2819],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 13],
['allow', 0],
['allow', 0],
['deny', 18],
['allow', 0],
['allow', 0],
['deny', 252],
['deny', 75],
['allow', 0]],
[2262, 2536, 2819]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 153, 253], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 47], ['allow', 0]], [253]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1014, 1015], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 985]], [1000, 1014]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1054, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1054, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 104, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 704, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 296],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [81, 344, 553, 1450, 1591, 1736, 1934, 2492, 2556, 2664, 2677, 2831],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 316],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 615],
['deny', 461]],
[2492, 2556, 2664]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 154, 254], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 46], ['allow', 0]], [254]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1015, 1016], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 984]], [1000, 1015]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1055, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1055, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 105, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 705, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 295],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [85, 117, 140, 309, 683, 1093, 2036, 2231, 2349, 2416, 2706, 2868],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 576],
['deny', 202],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 420],
['deny', 130],
['allow', 0]],
[2231, 2349, 2868]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 155, 255], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 45], ['allow', 0]], [255]]]]]
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 |
|---|---|---|---|
| exact expiry boundary | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 988]], [1000, 1011]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 988]], [1000, 1011]] | Passed |
| denied requests not logged | [[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]], [1051, 1150]] | [[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]], [1051, 1150]] | Passed |
| late timestamp uses monotonic now | [[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]], [900, 960]] | [[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]], [900, 960]] | Passed |
| retry after oldest expires | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 299], ['deny', 1], ['allow', 0], ['deny', 299]], [300, 600, 1000]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 299], ['deny', 1], ['allow', 0], ['deny', 299]], [300, 600, 1000]] | Passed |
| random traffic | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 306], ['deny', 175], ['deny', 129], ['deny', 28], ['deny', 17], ['allow', 0], ['deny', 81], ['allow', 0], ['allow', 0]], [1776, 2570]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 306], ['deny', 175], ['deny', 129], ['deny', 28], ['deny', 17], ['allow', 0], ['deny', 81], ['allow', 0], ['allow', 0]], [1776, 2570]] | Passed |
| single slot | [[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]] | [[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]] | Passed |
SHA-256 / ffe51265a277ce4d7596f91f3be68a941ede7195d2ea2fe528e7085fe3934f40
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.721092+00:00.
Case digest / 616613aadf67818e00ca1223b6ba6fbda4404ea03d03c5afcb1c2922455c1694