FA-73576 / Rate limiter algorithms / Open access
AIMD adaptive concurrency limit: reported limit rounded to nearest · case 01
The advertised concurrency exceeds the fractional limit.
ROOT CAUSE
The reported integer limit uses rounding instead of the floor.
VERIFIED REPAIR
Report floor(limit).
Unsuccessful approach: Ceiling over-reports every fractional limit.
Case contract
Input {initial, min, max, cooldown, events}. The limit is kept in fixed-point thousandths (integer). "ok" adds floor(10^6 / limit_thousandths), i.e. 1/limit, capped at max, and counts down an active cooldown. "drop" or "timeout" halves the limit (floor), floored at min, and starts a cooldown of the given number of events when no cooldown is active; during a cooldown a loss only counts it down. After each event report floor(limit). Return [reported whole limits, final limit in thousandths].
Why this case matters
Adaptive concurrency limiters (AIMD, as in TCP congestion control) protect overloaded backends; step sizes, bounds and cooldowns decide whether the limit converges or oscillates.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
lim = x['initial'] * 1000
lo, hi = x['min'] * 1000, x['max'] * 1000
cool = 0
out = []
for ev in x['events']:
if ev == 'ok':
lim = min(hi, lim + 1000000 // lim)
if cool:
cool -= 1
elif cool == 0:
lim = max(lo, lim // 2)
cool = x['cooldown']
else:
cool -= 1
out.append(round(lim / 1000))
return [out, lim]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5], 5861]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2], 2500]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4], 4595]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4], 4250]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'timeout',
'ok',
'timeout',
'ok',
'ok',
'timeout',
'ok',
'ok',
'timeout',
'ok',
'drop',
'ok',
'timeout',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 2500]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6], 6031]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2], 2900]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4], 4812]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4], 4485]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'ok',
'ok',
'ok',
'timeout',
'drop',
'timeout',
'drop',
'ok',
'ok',
'ok',
'timeout',
'ok',
'drop',
'ok',
'ok'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 3], 3244]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4], 4110]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6], 6196]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3], 3244]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5], 5019]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4], 4707]],
['random signals',
{'cooldown': 2,
'events': ['ok',
'drop',
'ok',
'ok',
'ok',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[6, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 3, 4, 4, 4, 2], 2305]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6], 6357]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3, 3], 3552]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5, 5], 5218]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 4], 4919]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'ok',
'drop',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 3, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 2], 2496]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4], 4110]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6], 6514]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3, 3, 3], 3833]],
['ceiling',
{'cooldown': 1,
'events': ['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5, 5, 5], 5409]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 4, 5], 5122]],
['random signals',
{'cooldown': 2,
'events': ['ok',
'timeout',
'timeout',
'ok',
'ok',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop',
'ok',
'timeout',
'ok'],
'initial': 6,
'max': 12,
'min': 2},
[[6, 3, 3, 3, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 2], 2900]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]]]
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 |
|---|---|---|---|
| additive growth | [[4, 4, 5, 5, 5, 5, 6, 6, 6], 5861] | [[4, 4, 4, 4, 5, 5, 5, 5, 5], 5861] | Failed |
| halving to floor | [[2, 2, 2, 2, 2], 2500] | [[2, 2, 2, 2, 2], 2500] | Passed |
| ceiling | [[9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10], 10000] | [[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10], 10000] | Failed |
| cooldown counts successes | [[8, 8, 8, 4, 4, 4, 5], 4595] | [[8, 8, 8, 4, 4, 4, 4], 4595] | Failed |
| cooldown counts losses | [[8, 8, 8, 4, 4, 4], 4250] | [[8, 8, 8, 4, 4, 4], 4250] | Passed |
| random signals | [[3, 3, 3, 2, 2, 3, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2], 2500] | [[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 2500] | Failed |
| odd limit halves | [[7, 4, 4, 4, 2], 2055] | [[7, 3, 3, 4, 2], 2055] | Failed |
SHA-256 / f308aaa07b6132d91319c75296b38c0d430989b11260415eead740b526011565
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
lim = x['initial'] * 1000
lo, hi = x['min'] * 1000, x['max'] * 1000
cool = 0
out = []
for ev in x['events']:
if ev == 'ok':
lim = min(hi, lim + 1000000 // lim)
if cool:
cool -= 1
elif cool == 0:
lim = max(lo, lim // 2)
cool = x['cooldown']
else:
cool -= 1
out.append(-(-lim // 1000))
return [out, lim]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5], 5861]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2], 2500]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4], 4595]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4], 4250]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'timeout',
'ok',
'timeout',
'ok',
'ok',
'timeout',
'ok',
'ok',
'timeout',
'ok',
'drop',
'ok',
'timeout',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 2500]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6], 6031]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2], 2900]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4], 4812]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4], 4485]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'ok',
'ok',
'ok',
'timeout',
'drop',
'timeout',
'drop',
'ok',
'ok',
'ok',
'timeout',
'ok',
'drop',
'ok',
'ok'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 3], 3244]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4], 4110]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6], 6196]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3], 3244]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5], 5019]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4], 4707]],
['random signals',
{'cooldown': 2,
'events': ['ok',
'drop',
'ok',
'ok',
'ok',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[6, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 3, 4, 4, 4, 2], 2305]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6], 6357]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3, 3], 3552]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5, 5], 5218]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 4], 4919]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'ok',
'drop',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 3, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 2], 2496]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4], 4110]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6], 6514]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3, 3, 3], 3833]],
['ceiling',
{'cooldown': 1,
'events': ['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5, 5, 5], 5409]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 4, 5], 5122]],
['random signals',
{'cooldown': 2,
'events': ['ok',
'timeout',
'timeout',
'ok',
'ok',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop',
'ok',
'timeout',
'ok'],
'initial': 6,
'max': 12,
'min': 2},
[[6, 3, 3, 3, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 2], 2900]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]]]
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 |
|---|---|---|---|
| additive growth | [[5, 5, 5, 5, 6, 6, 6, 6, 6], 5861] | [[4, 4, 4, 4, 5, 5, 5, 5, 5], 5861] | Failed |
| halving to floor | [[3, 2, 2, 2, 3], 2500] | [[2, 2, 2, 2, 2], 2500] | Failed |
| ceiling | [[10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10], 10000] | [[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10], 10000] | Failed |
| cooldown counts successes | [[8, 9, 9, 5, 5, 5, 5], 4595] | [[8, 8, 8, 4, 4, 4, 4], 4595] | Failed |
| cooldown counts losses | [[8, 8, 8, 4, 4, 5], 4250] | [[8, 8, 8, 4, 4, 4], 4250] | Failed |
| random signals | [[3, 3, 4, 2, 3, 3, 2, 3, 3, 2, 3, 3, 3, 2, 3, 3], 2500] | [[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 2500] | Failed |
| odd limit halves | [[8, 4, 4, 5, 3], 2055] | [[7, 3, 3, 4, 2], 2055] | Failed |
SHA-256 / a28cfa3e5a9e2bfd1be82cd0274e2971d8d3c1a28fed66671c81084b0e5cf51d
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
lim = x['initial'] * 1000
lo, hi = x['min'] * 1000, x['max'] * 1000
cool = 0
out = []
for ev in x['events']:
if ev == 'ok':
lim = min(hi, lim + 1000000 // lim)
if cool:
cool -= 1
elif cool == 0:
lim = max(lo, lim // 2)
cool = x['cooldown']
else:
cool -= 1
out.append(lim // 1000)
return [out, lim]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5], 5861]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2], 2500]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4], 4595]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4], 4250]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'timeout',
'ok',
'timeout',
'ok',
'ok',
'timeout',
'ok',
'ok',
'timeout',
'ok',
'drop',
'ok',
'timeout',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 2500]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6], 6031]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2], 2900]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4], 4812]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4], 4485]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'ok',
'ok',
'ok',
'timeout',
'drop',
'timeout',
'drop',
'ok',
'ok',
'ok',
'timeout',
'ok',
'drop',
'ok',
'ok'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 3], 3244]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4], 4110]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6], 6196]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3], 3244]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5], 5019]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4], 4707]],
['random signals',
{'cooldown': 2,
'events': ['ok',
'drop',
'ok',
'ok',
'ok',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[6, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 3, 4, 4, 4, 2], 2305]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6], 6357]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3, 3], 3552]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5, 5], 5218]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 4], 4919]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'ok',
'drop',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 3, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 2], 2496]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4], 4110]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6], 6514]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3, 3, 3], 3833]],
['ceiling',
{'cooldown': 1,
'events': ['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5, 5, 5], 5409]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 4, 5], 5122]],
['random signals',
{'cooldown': 2,
'events': ['ok',
'timeout',
'timeout',
'ok',
'ok',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop',
'ok',
'timeout',
'ok'],
'initial': 6,
'max': 12,
'min': 2},
[[6, 3, 3, 3, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 2], 2900]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]]]
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 |
|---|---|---|---|
| additive growth | [[4, 4, 4, 4, 5, 5, 5, 5, 5], 5861] | [[4, 4, 4, 4, 5, 5, 5, 5, 5], 5861] | Passed |
| halving to floor | [[2, 2, 2, 2, 2], 2500] | [[2, 2, 2, 2, 2], 2500] | Passed |
| ceiling | [[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10], 10000] | [[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10], 10000] | Passed |
| cooldown counts successes | [[8, 8, 8, 4, 4, 4, 4], 4595] | [[8, 8, 8, 4, 4, 4, 4], 4595] | Passed |
| cooldown counts losses | [[8, 8, 8, 4, 4, 4], 4250] | [[8, 8, 8, 4, 4, 4], 4250] | Passed |
| random signals | [[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 2500] | [[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 2500] | Passed |
| odd limit halves | [[7, 3, 3, 4, 2], 2055] | [[7, 3, 3, 4, 2], 2055] | Passed |
SHA-256 / d1b5fec9294aa93ab248712334ae5a8b42c18650de1284eea8f8553934e939d5
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:48.797631+00:00.
Case digest / eefd74c57b5733e0889485d97de4900b82af191fba94770c6622897e2f13089c