FA-73776 / Rate limiter algorithms / Open access
EWMA arrival-rate throttle: blend weights swapped · case 01
Long gaps keep the old rate while short gaps discard it, inverting the smoothing.
ROOT CAUSE
The decay factor weights the new sample instead of the previous estimate.
VERIFIED REPAIR
Weight the previous estimate by a and the new sample by 1 - a.
Unsuccessful approach: Never decaying the previous estimate makes the rate grow without bound.
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)
r = (1 - a) * r + 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', 9.048], ['allow', 9.909], ['allow', 9.991], ['allow', 9.999], ['allow', 10.0], ['allow', 10.0], ['allow', 10.0], ['allow', 10.0], ['allow', 10.0]] | [['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], ['deny', 98.02], ['deny', 99.961], ['deny', 99.999], ['deny', 100.0], ['deny', 91.107], ['deny', 77.611]] | [['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', 3.894], ['allow', 3.894], ['allow', 3.894], ['allow', 4.735], ['allow', 4.735]] | [['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.213], ['allow', 1.213], ['allow', 4.314], ['allow', 4.876]] | [['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]] | Failed |
| random arrivals | [['allow', 0.0], ['deny', 21.87], ['deny', 9.197], ['deny', 13.801], ['deny', 37.562], ['deny', 49.65], ['deny', 14.834], ['deny', 7.549], ['allow', 5.179], ['allow', 3.62], ['deny', 70.086], ['deny', 34.452]] | [['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.074], ['allow', 0.132], ['deny', 1.591]] | [['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]] | Failed |
SHA-256 / 082d3f854f14b654eccd94a421c89f5af12822269e21a9a247076858e315d377
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 = math.exp(-dt / tau)
r = 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.903], ['allow', 2.855], ['allow', 3.807], ['allow', 4.758], ['allow', 5.71], ['allow', 6.661], ['allow', 7.613], ['allow', 8.565]] | [['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', 1.98], ['allow', 3.96], ['allow', 5.94], ['allow', 7.921], ['allow', 9.899], ['allow', 10.795]] | [['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.106], ['allow', 1.106], ['allow', 1.106], ['allow', 2.211], ['allow', 2.211]] | [['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.787], ['allow', 0.787], ['allow', 1.693], ['allow', 2.6]] | [['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]] | Failed |
| random arrivals | [['allow', 0.0], ['allow', 1.386], ['allow', 2.632], ['allow', 3.991], ['allow', 5.393], ['deny', 6.802], ['deny', 8.114], ['deny', 9.366], ['deny', 10.295], ['deny', 11.328], ['deny', 12.743], ['deny', 13.796]] | [['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.259], ['allow', 0.518], ['allow', 0.96]] | [['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]] | Failed |
SHA-256 / eb452aebaabef80ff6ae28255783cd81dd9dadfb6ed1f7e6c05499bf0069f28a
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.708081+00:00.
Case digest / b57a1974a13d405e5ce123030c57be6af07cac8cf97b778d2936d7fa79be7207