FA-73761 / Rate limiter algorithms / Open access
EWMA arrival-rate throttle: decay constant treated as seconds · case 01
The estimate barely reacts to new arrivals and throttling kicks in minutes late.
ROOT CAUSE
The time constant in milliseconds is scaled by 1000 again.
VERIFIED REPAIR
Use exp(-dt / tau) with both in milliseconds.
Unsuccessful approach: A linear approximation of the decay is inaccurate for intervals comparable to tau.
Case contract
Input {tau_ms, limit_rps, requests [t_ms]}. The rate estimate r starts at 0. For each arrival strictly after the latest seen time, dt = t - last, a = exp(-dt/tau) and r = a*r + (1-a)*(1000/dt) requests per second. Simultaneous or late arrivals leave r unchanged and never move the clock backwards. Every arrival reports deny if r > limit else allow, with r rounded to 3 decimals.
Why this case matters
Irregular-interval EWMA estimators throttle clients by smoothed request rate; time-unit and duplicate-timestamp handling decide whether bursts are detected.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
tau = x['tau_ms']
lim = x['limit_rps']
r = 0.0
last = None
out = []
for t in x['requests']:
if last is not None and t > last:
dt = t - last
a = math.exp(-dt / (tau * 1000))
r = a * r + (1 - a) * (1000.0 / dt)
last = t if last is None else max(last, t)
out.append(['deny' if r > lim else 'allow', round(r, 3)])
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['steady ten per second',
{'limit_rps': 12, 'requests': [1, 101, 201, 301, 401, 501, 601, 701, 801, 901], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 51, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.499],
['allow', 2.319]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 401, 401], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.966],
['allow', 1.966]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 301, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [714, 757, 953, 1023, 1049, 1069, 1190, 1379, 2031, 2512, 2526, 2977],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.386],
['allow', 2.293],
['allow', 3.434],
['allow', 4.712],
['allow', 5.987],
['deny', 6.349],
['deny', 6.098],
['allow', 3.332],
['allow', 2.709],
['allow', 4.07],
['allow', 3.19]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6001, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [2, 102, 202, 302, 402, 502, 602, 702, 802, 902], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 52, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.482],
['allow', 2.32]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 402, 402], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.964],
['allow', 1.964]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 302, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [216, 250, 522, 784, 966, 1254, 1553, 2058, 2080, 2239, 2561, 2685],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.394],
['allow', 2.129],
['allow', 2.656],
['allow', 3.306],
['allow', 3.362],
['allow', 3.356],
['allow', 2.649],
['allow', 3.973],
['allow', 4.444],
['allow', 3.95],
['allow', 4.618]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6002, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [3, 103, 203, 303, 403, 503, 603, 703, 803, 903], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 53, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.465],
['allow', 2.321]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 403, 403], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.962],
['allow', 1.962]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 303, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [86, 138, 254, 788, 1018, 1187, 1336, 1765, 2119, 2249, 2554, 2910],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.377],
['allow', 2.483],
['allow', 2.157],
['allow', 2.771],
['allow', 3.446],
['allow', 4.072],
['allow', 3.274],
['allow', 3.096],
['allow', 3.875],
['allow', 3.664],
['allow', 3.323]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6003, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.69]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [4, 104, 204, 304, 404, 504, 604, 704, 804, 904], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 54, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.448],
['allow', 2.322]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 404, 404], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.96],
['allow', 1.96]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 304, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [385, 507, 716, 724, 1100, 1757, 1778, 1945, 2017, 2160, 2509, 2770],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.311],
['allow', 2.208],
['allow', 3.603],
['allow', 3.211],
['allow', 2.183],
['allow', 3.526],
['allow', 4.048],
['allow', 5.01],
['allow', 5.376],
['allow', 4.391],
['allow', 4.217]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6004, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.316], ['allow', 0.69]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [5, 105, 205, 305, 405, 505, 605, 705, 805, 905], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 55, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.431],
['allow', 2.323]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 405, 405], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.959],
['allow', 1.959]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 305, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [165, 419, 489, 1134, 1196, 1250, 1558, 1747, 2333, 2495, 2720, 2742],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.198],
['allow', 2.444],
['allow', 1.906],
['allow', 3.111],
['allow', 4.255],
['allow', 3.896],
['allow', 4.226],
['allow', 2.797],
['allow', 3.495],
['allow', 3.756],
['allow', 5.046]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6005, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.316], ['allow', 0.69]]]]]
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 |
|---|---|---|---|
| steady ten per second | [['allow', 0.0], ['allow', 0.001], ['allow', 0.002], ['allow', 0.003], ['allow', 0.004], ['allow', 0.005], ['allow', 0.006], ['allow', 0.007], ['allow', 0.008], ['allow', 0.009]] | [['allow', 0.0], ['allow', 0.952], ['allow', 1.813], ['allow', 2.592], ['allow', 3.297], ['allow', 3.935], ['allow', 4.512], ['allow', 5.034], ['allow', 5.507], ['allow', 5.934]] | Failed |
| burst crosses limit | [['allow', 0.0], ['allow', 0.002], ['allow', 0.004], ['allow', 0.006], ['allow', 0.008], ['allow', 0.01], ['allow', 0.012]] | [['allow', 0.0], ['allow', 1.98], ['allow', 3.921], ['allow', 5.824], ['allow', 7.688], ['allow', 9.499], ['allow', 2.319]] | Failed |
| simultaneous arrivals | [['allow', 0.0], ['allow', 0.001], ['allow', 0.001], ['allow', 0.001], ['allow', 0.002], ['allow', 0.002]] | [['allow', 0.0], ['allow', 1.106], ['allow', 1.106], ['allow', 1.106], ['allow', 1.966], ['allow', 1.966]] | Failed |
| late arrival ignored for clock | [['allow', 0.0], ['allow', 0.001], ['allow', 0.001], ['allow', 0.002], ['allow', 0.003]] | [['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]] | Failed |
| random arrivals | [['allow', 0.0], ['allow', 0.001], ['allow', 0.003], ['allow', 0.004], ['allow', 0.006], ['allow', 0.007], ['allow', 0.009], ['allow', 0.01], ['allow', 0.011], ['allow', 0.013], ['allow', 0.014], ['allow', 0.016]] | [['allow', 0.0], ['allow', 1.386], ['allow', 2.293], ['allow', 3.434], ['allow', 4.712], ['allow', 5.987], ['deny', 6.349], ['deny', 6.098], ['allow', 3.332], ['allow', 2.709], ['allow', 4.07], ['allow', 3.19]] | Failed |
| slow client | [['allow', 0.0], ['allow', 0.0], ['allow', 0.001], ['allow', 0.001]] | [['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]] | Failed |
SHA-256 / 90f3880bfbd2d7d7ecf1699405101b6e87d45842c5407a404f2f167fad993228
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
tau = x['tau_ms']
lim = x['limit_rps']
r = 0.0
last = None
out = []
for t in x['requests']:
if last is not None and t > last:
dt = t - last
a = max(0.0, 1 - dt / tau)
r = a * r + (1 - a) * (1000.0 / dt)
last = t if last is None else max(last, t)
out.append(['deny' if r > lim else 'allow', round(r, 3)])
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['steady ten per second',
{'limit_rps': 12, 'requests': [1, 101, 201, 301, 401, 501, 601, 701, 801, 901], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 51, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.499],
['allow', 2.319]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 401, 401], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.966],
['allow', 1.966]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 301, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [714, 757, 953, 1023, 1049, 1069, 1190, 1379, 2031, 2512, 2526, 2977],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.386],
['allow', 2.293],
['allow', 3.434],
['allow', 4.712],
['allow', 5.987],
['deny', 6.349],
['deny', 6.098],
['allow', 3.332],
['allow', 2.709],
['allow', 4.07],
['allow', 3.19]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6001, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [2, 102, 202, 302, 402, 502, 602, 702, 802, 902], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 52, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.482],
['allow', 2.32]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 402, 402], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.964],
['allow', 1.964]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 302, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [216, 250, 522, 784, 966, 1254, 1553, 2058, 2080, 2239, 2561, 2685],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.394],
['allow', 2.129],
['allow', 2.656],
['allow', 3.306],
['allow', 3.362],
['allow', 3.356],
['allow', 2.649],
['allow', 3.973],
['allow', 4.444],
['allow', 3.95],
['allow', 4.618]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6002, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [3, 103, 203, 303, 403, 503, 603, 703, 803, 903], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 53, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.465],
['allow', 2.321]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 403, 403], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.962],
['allow', 1.962]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 303, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [86, 138, 254, 788, 1018, 1187, 1336, 1765, 2119, 2249, 2554, 2910],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.377],
['allow', 2.483],
['allow', 2.157],
['allow', 2.771],
['allow', 3.446],
['allow', 4.072],
['allow', 3.274],
['allow', 3.096],
['allow', 3.875],
['allow', 3.664],
['allow', 3.323]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6003, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.69]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [4, 104, 204, 304, 404, 504, 604, 704, 804, 904], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 54, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.448],
['allow', 2.322]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 404, 404], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.96],
['allow', 1.96]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 304, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [385, 507, 716, 724, 1100, 1757, 1778, 1945, 2017, 2160, 2509, 2770],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.311],
['allow', 2.208],
['allow', 3.603],
['allow', 3.211],
['allow', 2.183],
['allow', 3.526],
['allow', 4.048],
['allow', 5.01],
['allow', 5.376],
['allow', 4.391],
['allow', 4.217]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6004, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.316], ['allow', 0.69]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [5, 105, 205, 305, 405, 505, 605, 705, 805, 905], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 55, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.431],
['allow', 2.323]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 405, 405], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.959],
['allow', 1.959]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 305, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [165, 419, 489, 1134, 1196, 1250, 1558, 1747, 2333, 2495, 2720, 2742],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.198],
['allow', 2.444],
['allow', 1.906],
['allow', 3.111],
['allow', 4.255],
['allow', 3.896],
['allow', 4.226],
['allow', 2.797],
['allow', 3.495],
['allow', 3.756],
['allow', 5.046]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6005, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.316], ['allow', 0.69]]]]]
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 |
|---|---|---|---|
| steady ten per second | [['allow', 0.0], ['allow', 1.0], ['allow', 1.9], ['allow', 2.71], ['allow', 3.439], ['allow', 4.095], ['allow', 4.686], ['allow', 5.217], ['allow', 5.695], ['allow', 6.126]] | [['allow', 0.0], ['allow', 0.952], ['allow', 1.813], ['allow', 2.592], ['allow', 3.297], ['allow', 3.935], ['allow', 4.512], ['allow', 5.034], ['allow', 5.507], ['allow', 5.934]] | Failed |
| burst crosses limit | [['allow', 0.0], ['allow', 2.0], ['allow', 3.96], ['allow', 5.881], ['allow', 7.763], ['allow', 9.592], ['allow', 1.054]] | [['allow', 0.0], ['allow', 1.98], ['allow', 3.921], ['allow', 5.824], ['allow', 7.688], ['allow', 9.499], ['allow', 2.319]] | Failed |
| simultaneous arrivals | [['allow', 0.0], ['allow', 1.25], ['allow', 1.25], ['allow', 1.25], ['allow', 2.186], ['allow', 2.186]] | [['allow', 0.0], ['allow', 1.106], ['allow', 1.106], ['allow', 1.106], ['allow', 1.966], ['allow', 1.966]] | Failed |
| late arrival ignored for clock | [['allow', 0.0], ['allow', 1.0], ['allow', 1.0], ['allow', 1.8], ['allow', 2.44]] | [['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]] | Failed |
| random arrivals | [['allow', 0.0], ['allow', 1.429], ['allow', 2.457], ['allow', 3.64], ['allow', 4.933], ['deny', 6.221], ['deny', 6.574], ['deny', 6.228], ['allow', 1.856], ['allow', 2.009], ['allow', 3.398], ['allow', 2.637]] | [['allow', 0.0], ['allow', 1.386], ['allow', 2.293], ['allow', 3.434], ['allow', 4.712], ['allow', 5.987], ['deny', 6.349], ['deny', 6.098], ['allow', 3.332], ['allow', 2.709], ['allow', 4.07], ['allow', 3.19]] | Failed |
| slow client | [['allow', 0.0], ['allow', 0.333], ['allow', 0.333], ['allow', 0.75]] | [['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]] | Failed |
SHA-256 / 703c6f65bbcec60ba760b444e87c3f10c58cc1a0639c0ade83d3fd89c8b51400
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
tau = x['tau_ms']
lim = x['limit_rps']
r = 0.0
last = None
out = []
for t in x['requests']:
if last is not None and t > last:
dt = t - last
a = math.exp(-dt / tau)
r = a * r + (1 - a) * (1000.0 / dt)
last = t if last is None else max(last, t)
out.append(['deny' if r > lim else 'allow', round(r, 3)])
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['steady ten per second',
{'limit_rps': 12, 'requests': [1, 101, 201, 301, 401, 501, 601, 701, 801, 901], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 51, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.499],
['allow', 2.319]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 401, 401], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.966],
['allow', 1.966]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 301, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [714, 757, 953, 1023, 1049, 1069, 1190, 1379, 2031, 2512, 2526, 2977],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.386],
['allow', 2.293],
['allow', 3.434],
['allow', 4.712],
['allow', 5.987],
['deny', 6.349],
['deny', 6.098],
['allow', 3.332],
['allow', 2.709],
['allow', 4.07],
['allow', 3.19]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6001, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [2, 102, 202, 302, 402, 502, 602, 702, 802, 902], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 52, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.482],
['allow', 2.32]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 402, 402], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.964],
['allow', 1.964]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 302, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [216, 250, 522, 784, 966, 1254, 1553, 2058, 2080, 2239, 2561, 2685],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.394],
['allow', 2.129],
['allow', 2.656],
['allow', 3.306],
['allow', 3.362],
['allow', 3.356],
['allow', 2.649],
['allow', 3.973],
['allow', 4.444],
['allow', 3.95],
['allow', 4.618]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6002, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [3, 103, 203, 303, 403, 503, 603, 703, 803, 903], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 53, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.465],
['allow', 2.321]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 403, 403], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.962],
['allow', 1.962]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 303, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [86, 138, 254, 788, 1018, 1187, 1336, 1765, 2119, 2249, 2554, 2910],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.377],
['allow', 2.483],
['allow', 2.157],
['allow', 2.771],
['allow', 3.446],
['allow', 4.072],
['allow', 3.274],
['allow', 3.096],
['allow', 3.875],
['allow', 3.664],
['allow', 3.323]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6003, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.69]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [4, 104, 204, 304, 404, 504, 604, 704, 804, 904], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 54, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.448],
['allow', 2.322]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 404, 404], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.96],
['allow', 1.96]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 304, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [385, 507, 716, 724, 1100, 1757, 1778, 1945, 2017, 2160, 2509, 2770],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.311],
['allow', 2.208],
['allow', 3.603],
['allow', 3.211],
['allow', 2.183],
['allow', 3.526],
['allow', 4.048],
['allow', 5.01],
['allow', 5.376],
['allow', 4.391],
['allow', 4.217]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6004, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.316], ['allow', 0.69]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [5, 105, 205, 305, 405, 505, 605, 705, 805, 905], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 55, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.431],
['allow', 2.323]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 405, 405], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.959],
['allow', 1.959]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 305, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [165, 419, 489, 1134, 1196, 1250, 1558, 1747, 2333, 2495, 2720, 2742],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.198],
['allow', 2.444],
['allow', 1.906],
['allow', 3.111],
['allow', 4.255],
['allow', 3.896],
['allow', 4.226],
['allow', 2.797],
['allow', 3.495],
['allow', 3.756],
['allow', 5.046]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6005, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.316], ['allow', 0.69]]]]]
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 |
|---|---|---|---|
| steady ten per second | [['allow', 0.0], ['allow', 0.952], ['allow', 1.813], ['allow', 2.592], ['allow', 3.297], ['allow', 3.935], ['allow', 4.512], ['allow', 5.034], ['allow', 5.507], ['allow', 5.934]] | [['allow', 0.0], ['allow', 0.952], ['allow', 1.813], ['allow', 2.592], ['allow', 3.297], ['allow', 3.935], ['allow', 4.512], ['allow', 5.034], ['allow', 5.507], ['allow', 5.934]] | Passed |
| burst crosses limit | [['allow', 0.0], ['allow', 1.98], ['allow', 3.921], ['allow', 5.824], ['allow', 7.688], ['allow', 9.499], ['allow', 2.319]] | [['allow', 0.0], ['allow', 1.98], ['allow', 3.921], ['allow', 5.824], ['allow', 7.688], ['allow', 9.499], ['allow', 2.319]] | Passed |
| simultaneous arrivals | [['allow', 0.0], ['allow', 1.106], ['allow', 1.106], ['allow', 1.106], ['allow', 1.966], ['allow', 1.966]] | [['allow', 0.0], ['allow', 1.106], ['allow', 1.106], ['allow', 1.106], ['allow', 1.966], ['allow', 1.966]] | Passed |
| late arrival ignored for clock | [['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]] | [['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]] | Passed |
| random arrivals | [['allow', 0.0], ['allow', 1.386], ['allow', 2.293], ['allow', 3.434], ['allow', 4.712], ['allow', 5.987], ['deny', 6.349], ['deny', 6.098], ['allow', 3.332], ['allow', 2.709], ['allow', 4.07], ['allow', 3.19]] | [['allow', 0.0], ['allow', 1.386], ['allow', 2.293], ['allow', 3.434], ['allow', 4.712], ['allow', 5.987], ['deny', 6.349], ['deny', 6.098], ['allow', 3.332], ['allow', 2.709], ['allow', 4.07], ['allow', 3.19]] | Passed |
| slow client | [['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]] | [['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]] | Passed |
SHA-256 / ae9e342895343a060b50275053ac8ec827ac062821b494aaada7838947fc65eb
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:50.585355+00:00.
Case digest / 395f2c94e7c0903ef31b696596a27aa4e06dc2b3079012d6c6a3a0d7c5874ad3