FAILURE MAP
← Case archive

FA-73496 / Rate limiter algorithms / Open access

Leaky bucket meter: admission ignores the request cost · case 01

A large request is admitted into an almost full bucket and overflows it.

Verified by executionVariant 1 · 6 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

Admission only checks that the bucket is not already full.

VERIFIED REPAIR

Admit only when level + cost fits within capacity.

Unsuccessful approach: A strict comparison rejects requests that exactly fill the bucket.

Case contract

Input {capacity, leak_per_s, requests [[t_ms, cost]]} with nondecreasing t. The water level drains continuously at leak_per_s units per second (exact rationals) but never below zero; the drain clock advances at every request. A request is admitted iff level + cost <= capacity, raising the level by cost; a denied request leaves the level unchanged. Return [decisions, final level as a fraction string].

Why this case matters

Leaky-bucket meters police sustained rates for network and API traffic; drain and admission rules decide how much burst is tolerated after idleness.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    cap = x['capacity']
    leak = x['leak_per_s']
    level = Fraction(0)
    last = 0
    out = []
    for t, cost in x['requests']:
        level = max(Fraction(0), level - Fraction((t - last) * leak, 1000))
        last = t
        if level < cap:
            level += cost
            out.append('allow')
        else:
            out.append('deny')
    return [out, str(level)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1501, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '1999/500']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20501, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '3499/1000']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [401, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1001, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [601, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[781, 3],
                 [1209, 2],
                 [1536, 1],
                 [2095, 2],
                 [2724, 2],
                 [3100, 1],
                 [3484, 2],
                 [3740, 2],
                 [4367, 3],
                 [4423, 2]]},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny', 'allow', 'deny'],
    '1179/250']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1502, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '999/250']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20502, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '1749/500']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [402, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1002, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [602, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[589, 3],
                 [638, 1],
                 [745, 3],
                 [2131, 2],
                 [2216, 1],
                 [2400, 1],
                 [3010, 3],
                 [3050, 3],
                 [4494, 3],
                 [4689, 1]]},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'allow', 'deny', 'deny', 'allow', 'allow'],
    '19/5']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1503, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '1997/500']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20503, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '3497/1000']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [403, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1003, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [603, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[952, 1],
                 [1197, 1],
                 [1505, 1],
                 [2785, 2],
                 [2886, 3],
                 [3133, 3],
                 [3501, 1],
                 [3696, 3],
                 [4546, 2],
                 [4936, 3]]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow', 'deny', 'allow', 'deny'],
    '1849/500']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1504, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '499/125']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20504, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '437/125']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [404, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1004, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [604, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[81, 3],
                 [993, 2],
                 [1192, 3],
                 [2031, 1],
                 [2228, 3],
                 [2879, 2],
                 [2930, 2],
                 [3521, 3],
                 [4067, 2],
                 [4522, 3]]},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny', 'deny', 'allow', 'deny'],
    '1059/500']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1505, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '399/100']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20505, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '699/200']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [405, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1005, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [605, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[294, 3],
                 [1702, 1],
                 [1855, 3],
                 [1921, 3],
                 [2460, 1],
                 [2482, 3],
                 [3497, 3],
                 [4189, 1],
                 [4252, 3],
                 [4982, 2]]},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'deny', 'allow', 'allow', 'deny', 'allow'],
    '578/125']]]]
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 fixtureActualExpectedOutcome
fill and drain[['allow', 'allow', 'allow', 'deny', 'allow'], '2499/500'][['allow', 'allow', 'deny', 'allow', 'allow'], '1999/500']Failed
idle does not bank credit[['allow', 'allow', 'deny', 'allow'], '4499/1000'][['allow', 'allow', 'deny', 'deny'], '3499/1000']Failed
sub-second leak[['allow', 'allow', 'allow', 'allow', 'allow'], '22/5'][['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']Failed
exact fit[['allow', 'allow', 'allow', 'allow'], '7'][['allow', 'allow', 'deny', 'allow'], '6']Failed
denials do not fill[['allow', 'allow', 'deny', 'deny', 'deny'], '23/5'][['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']Failed
random stream[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow', 'deny', 'allow', 'deny'], '1929/250'][['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny', 'allow', 'deny'], '1179/250']Failed

SHA-256 / 724c0adc50b24a85d142c668ee6abfcad2ca91074251d5832d977aba01ba641f

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    cap = x['capacity']
    leak = x['leak_per_s']
    level = Fraction(0)
    last = 0
    out = []
    for t, cost in x['requests']:
        level = max(Fraction(0), level - Fraction((t - last) * leak, 1000))
        last = t
        if level + cost < cap:
            level += cost
            out.append('allow')
        else:
            out.append('deny')
    return [out, str(level)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1501, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '1999/500']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20501, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '3499/1000']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [401, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1001, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [601, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[781, 3],
                 [1209, 2],
                 [1536, 1],
                 [2095, 2],
                 [2724, 2],
                 [3100, 1],
                 [3484, 2],
                 [3740, 2],
                 [4367, 3],
                 [4423, 2]]},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny', 'allow', 'deny'],
    '1179/250']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1502, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '999/250']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20502, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '1749/500']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [402, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1002, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [602, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[589, 3],
                 [638, 1],
                 [745, 3],
                 [2131, 2],
                 [2216, 1],
                 [2400, 1],
                 [3010, 3],
                 [3050, 3],
                 [4494, 3],
                 [4689, 1]]},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'allow', 'deny', 'deny', 'allow', 'allow'],
    '19/5']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1503, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '1997/500']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20503, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '3497/1000']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [403, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1003, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [603, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[952, 1],
                 [1197, 1],
                 [1505, 1],
                 [2785, 2],
                 [2886, 3],
                 [3133, 3],
                 [3501, 1],
                 [3696, 3],
                 [4546, 2],
                 [4936, 3]]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow', 'deny', 'allow', 'deny'],
    '1849/500']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1504, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '499/125']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20504, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '437/125']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [404, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1004, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [604, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[81, 3],
                 [993, 2],
                 [1192, 3],
                 [2031, 1],
                 [2228, 3],
                 [2879, 2],
                 [2930, 2],
                 [3521, 3],
                 [4067, 2],
                 [4522, 3]]},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny', 'deny', 'allow', 'deny'],
    '1059/500']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1505, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '399/100']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20505, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '699/200']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [405, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1005, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [605, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[294, 3],
                 [1702, 1],
                 [1855, 3],
                 [1921, 3],
                 [2460, 1],
                 [2482, 3],
                 [3497, 3],
                 [4189, 1],
                 [4252, 3],
                 [4982, 2]]},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'deny', 'allow', 'allow', 'deny', 'allow'],
    '578/125']]]]
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 fixtureActualExpectedOutcome
fill and drain[['allow', 'allow', 'deny', 'allow', 'allow'], '1999/500'][['allow', 'allow', 'deny', 'allow', 'allow'], '1999/500']Passed
idle does not bank credit[['allow', 'deny', 'allow', 'allow'], '1499/1000'][['allow', 'allow', 'deny', 'deny'], '3499/1000']Failed
sub-second leak[['deny', 'allow', 'allow', 'allow', 'allow'], '12/5'][['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']Failed
exact fit[['deny', 'allow', 'allow', 'allow'], '4'][['allow', 'allow', 'deny', 'allow'], '6']Failed
denials do not fill[['allow', 'deny', 'deny', 'allow', 'deny'], '18/5'][['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']Passed
random stream[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny', 'allow', 'deny'], '1179/250'][['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny', 'allow', 'deny'], '1179/250']Passed

SHA-256 / 38796907755c2b30b2fbce7139759acd33eaccc70ba3d9f3710cab2243364961

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    cap = x['capacity']
    leak = x['leak_per_s']
    level = Fraction(0)
    last = 0
    out = []
    for t, cost in x['requests']:
        level = max(Fraction(0), level - Fraction((t - last) * leak, 1000))
        last = t
        if level + cost <= cap:
            level += cost
            out.append('allow')
        else:
            out.append('deny')
    return [out, str(level)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1501, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '1999/500']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20501, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '3499/1000']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [401, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1001, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [601, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[781, 3],
                 [1209, 2],
                 [1536, 1],
                 [2095, 2],
                 [2724, 2],
                 [3100, 1],
                 [3484, 2],
                 [3740, 2],
                 [4367, 3],
                 [4423, 2]]},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny', 'allow', 'deny'],
    '1179/250']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1502, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '999/250']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20502, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '1749/500']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [402, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1002, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [602, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[589, 3],
                 [638, 1],
                 [745, 3],
                 [2131, 2],
                 [2216, 1],
                 [2400, 1],
                 [3010, 3],
                 [3050, 3],
                 [4494, 3],
                 [4689, 1]]},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'allow', 'deny', 'deny', 'allow', 'allow'],
    '19/5']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1503, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '1997/500']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20503, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '3497/1000']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [403, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1003, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [603, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[952, 1],
                 [1197, 1],
                 [1505, 1],
                 [2785, 2],
                 [2886, 3],
                 [3133, 3],
                 [3501, 1],
                 [3696, 3],
                 [4546, 2],
                 [4936, 3]]},
   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow', 'deny', 'allow', 'deny'],
    '1849/500']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1504, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '499/125']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20504, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '437/125']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [404, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1004, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [604, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[81, 3],
                 [993, 2],
                 [1192, 3],
                 [2031, 1],
                 [2228, 3],
                 [2879, 2],
                 [2930, 2],
                 [3521, 3],
                 [4067, 2],
                 [4522, 3]]},
   [['allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny', 'deny', 'allow', 'deny'],
    '1059/500']]],
 [['fill and drain',
   {'capacity': 5, 'leak_per_s': 2, 'requests': [[0, 2], [0, 2], [0, 2], [500, 1], [1505, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'allow'], '399/100']],
  ['idle does not bank credit',
   {'capacity': 4, 'leak_per_s': 1, 'requests': [[0, 1], [20000, 4], [20000, 1], [20505, 1]]},
   [['allow', 'allow', 'deny', 'deny'], '699/200']],
  ['sub-second leak',
   {'capacity': 3, 'leak_per_s': 4, 'requests': [[0, 3], [250, 1], [405, 1], [600, 1], [900, 2]]},
   [['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']],
  ['exact fit',
   {'capacity': 6, 'leak_per_s': 3, 'requests': [[0, 6], [1000, 3], [1005, 1], [2000, 3]]},
   [['allow', 'allow', 'deny', 'allow'], '6']],
  ['denials do not fill',
   {'capacity': 4, 'leak_per_s': 2, 'requests': [[0, 3], [100, 3], [200, 3], [605, 2], [700, 1]]},
   [['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']],
  ['random stream',
   {'capacity': 5,
    'leak_per_s': 2,
    'requests': [[294, 3],
                 [1702, 1],
                 [1855, 3],
                 [1921, 3],
                 [2460, 1],
                 [2482, 3],
                 [3497, 3],
                 [4189, 1],
                 [4252, 3],
                 [4982, 2]]},
   [['allow', 'allow', 'allow', 'deny', 'allow', 'deny', 'allow', 'allow', 'deny', 'allow'],
    '578/125']]]]
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 fixtureActualExpectedOutcome
fill and drain[['allow', 'allow', 'deny', 'allow', 'allow'], '1999/500'][['allow', 'allow', 'deny', 'allow', 'allow'], '1999/500']Passed
idle does not bank credit[['allow', 'allow', 'deny', 'deny'], '3499/1000'][['allow', 'allow', 'deny', 'deny'], '3499/1000']Passed
sub-second leak[['allow', 'allow', 'deny', 'allow', 'deny'], '7/5'][['allow', 'allow', 'deny', 'allow', 'deny'], '7/5']Passed
exact fit[['allow', 'allow', 'deny', 'allow'], '6'][['allow', 'allow', 'deny', 'allow'], '6']Passed
denials do not fill[['allow', 'deny', 'deny', 'allow', 'deny'], '18/5'][['allow', 'deny', 'deny', 'allow', 'deny'], '18/5']Passed
random stream[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny', 'allow', 'deny'], '1179/250'][['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny', 'allow', 'deny'], '1179/250']Passed

SHA-256 / 87019a2a4d4cad60d1df32476ac7faf5eeaea95a71bd745285150e5ea159c338

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.139065+00:00.

Case digest / 72a4fa98291edf7a09624b72ad72afed811bfd37d8a324e14c3f8790fa745719