FA-73346 / Rate limiter algorithms / Open access

Token bucket with lazy exact refill: backwards clock step drains tokens · case 01

A request stamped slightly earlier than the previous one removes tokens it never spent.

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

ROOT CAUSE

Negative elapsed time is not clamped to zero.

VERIFIED REPAIR

Treat negative elapsed time as zero.

Unsuccessful approach: Using the absolute value credits tokens for time that never passed.

Case contract

Input {capacity, rate (tokens per second), requests [[t_ms, cost]]}. The bucket starts full at t=0. At each request, elapsed = max(0, t - last); tokens = min(capacity, tokens + elapsed*rate/1000) in exact rational arithmetic; last = max(last, t) so a regressing clock neither drains nor re-credits. A cost above capacity can never succeed ("never"). Otherwise allow when tokens >= cost and deduct; else deny with wait = ceil((cost - tokens) * 1000 / rate) ms. Return [[decision, wait]], final tokens].

Why this case matters

API gateways and client SDKs meter requests with lazily refilled token buckets; the refill, clock and boundary rules decide who is throttled and what wait is advertised.

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):
    C = x['capacity']
    rate = x['rate']
    tokens = Fraction(C)
    last = 0
    out = []
    for t, cost in x['requests']:
        elapsed = t - last
        tokens = min(Fraction(C), tokens + Fraction(elapsed * rate, 1000))
        last = max(last, t)
        if cost > C:
            out.append(['never', 0])
        elif tokens >= cost:
            tokens -= cost
            out.append(['allow', 0])
        else:
            out.append(['deny', math.ceil((cost - tokens) * 1000 / rate)])
    return [out, str(tokens)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [100, 1], [1000, 2], [1401, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 400],
     ['allow', 0],
     ['deny', 99]],
    '401/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10001, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3100, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3710, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3001, 3], [3001, 5]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2334, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [901, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1025, 1],
                 [1038, 3],
                 [1399, 1],
                 [1944, 3],
                 [2745, 1],
                 [2753, 1],
                 [3169, 1],
                 [4025, 1],
                 [4086, 3],
                 [4305, 3]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 126],
     ['deny', 581],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 439],
     ['deny', 220]],
    '64/25']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [200, 1], [1000, 2], [1402, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 300],
     ['allow', 0],
     ['deny', 98]],
    '201/250']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10002, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 332], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3200, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3720, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3002, 3], [3002, 6]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2668, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '251/250']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [902, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '353/500']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[679, 3],
                 [889, 1],
                 [1479, 1],
                 [1523, 1],
                 [1681, 1],
                 [2074, 3],
                 [2401, 2],
                 [2669, 3],
                 [4187, 3],
                 [4538, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 156],
     ['allow', 0],
     ['deny', 1105],
     ['deny', 278],
     ['deny', 510],
     ['allow', 0],
     ['allow', 0]],
    '351/500']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [300, 1], [1000, 2], [1403, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 200],
     ['allow', 0],
     ['deny', 97]],
    '403/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10003, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 331], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3300, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3730, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3003, 3], [3003, 7]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3002, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1003/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [903, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '709/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[476, 2],
                 [1005, 3],
                 [1092, 1],
                 [1140, 2],
                 [2416, 2],
                 [2727, 2],
                 [3540, 3],
                 [3809, 1],
                 [3822, 1],
                 [4130, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 384],
     ['deny', 836],
     ['allow', 0],
     ['deny', 249],
     ['allow', 0],
     ['deny', 167],
     ['deny', 154],
     ['allow', 0]],
    '77/250']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [400, 1], [1000, 2], [1404, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 100],
     ['allow', 0],
     ['deny', 96]],
    '101/125']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10004, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 330], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3400, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3740, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3004, 3], [3004, 8]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3336, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '376/125']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [904, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '89/125']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[295, 3],
                 [481, 2],
                 [603, 2],
                 [1079, 3],
                 [1690, 3],
                 [1700, 3],
                 [2433, 3],
                 [3280, 3],
                 [4573, 3],
                 [4680, 3]]},
   [[['allow', 0],
     ['deny', 314],
     ['deny', 192],
     ['deny', 216],
     ['allow', 0],
     ['deny', 1095],
     ['deny', 362],
     ['allow', 0],
     ['allow', 0],
     ['deny', 1115]],
    '77/100']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [500, 1], [1000, 2], [1405, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 500],
     ['allow', 0]],
    '81/100']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10005, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 329], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3500, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3750, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3005, 3], [3005, 9]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3670, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '401/100']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [905, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '143/200']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1144, 3],
                 [1657, 3],
                 [1896, 3],
                 [2302, 2],
                 [2570, 2],
                 [3012, 1],
                 [3025, 1],
                 [3251, 1],
                 [4294, 1],
                 [4860, 2]]},
   [[['allow', 0],
     ['deny', 487],
     ['deny', 248],
     ['allow', 0],
     ['deny', 74],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0]],
    '54/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 fixture	Actual	Expected	Outcome
burst then refill	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 400], ['allow', 0], ['deny', 99]], '401/500']`	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 400], ['allow', 0], ['deny', 99]], '401/500']`	Passed
idle overflow capped	`[[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']`	`[[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']`	Passed
clock regression	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 500]], '1/2']`	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']`	Failed
small clock step back	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/100']`	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']`	Failed
oversize cost	`[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']`	`[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']`	Passed
exact boundary after refill	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']`	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']`	Passed
fractional shortfall	`[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']`	`[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']`	Passed
random stream	`[[['allow', 0], ['allow', 0], ['deny', 126], ['deny', 581], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 439], ['deny', 220]], '64/25']`	`[[['allow', 0], ['allow', 0], ['deny', 126], ['deny', 581], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 439], ['deny', 220]], '64/25']`	Passed

SHA-256 / bce8e35f5b9bf6c69e90dc0d44b038e95b6022ff2fab4aa90bf99a2a26836480

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):
    C = x['capacity']
    rate = x['rate']
    tokens = Fraction(C)
    last = 0
    out = []
    for t, cost in x['requests']:
        elapsed = abs(t - last)
        tokens = min(Fraction(C), tokens + Fraction(elapsed * rate, 1000))
        last = max(last, t)
        if cost > C:
            out.append(['never', 0])
        elif tokens >= cost:
            tokens -= cost
            out.append(['allow', 0])
        else:
            out.append(['deny', math.ceil((cost - tokens) * 1000 / rate)])
    return [out, str(tokens)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [100, 1], [1000, 2], [1401, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 400],
     ['allow', 0],
     ['deny', 99]],
    '401/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10001, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3100, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3710, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3001, 3], [3001, 5]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2334, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [901, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1025, 1],
                 [1038, 3],
                 [1399, 1],
                 [1944, 3],
                 [2745, 1],
                 [2753, 1],
                 [3169, 1],
                 [4025, 1],
                 [4086, 3],
                 [4305, 3]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 126],
     ['deny', 581],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 439],
     ['deny', 220]],
    '64/25']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [200, 1], [1000, 2], [1402, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 300],
     ['allow', 0],
     ['deny', 98]],
    '201/250']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10002, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 332], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3200, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3720, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3002, 3], [3002, 6]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2668, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '251/250']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [902, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '353/500']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[679, 3],
                 [889, 1],
                 [1479, 1],
                 [1523, 1],
                 [1681, 1],
                 [2074, 3],
                 [2401, 2],
                 [2669, 3],
                 [4187, 3],
                 [4538, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 156],
     ['allow', 0],
     ['deny', 1105],
     ['deny', 278],
     ['deny', 510],
     ['allow', 0],
     ['allow', 0]],
    '351/500']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [300, 1], [1000, 2], [1403, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 200],
     ['allow', 0],
     ['deny', 97]],
    '403/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10003, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 331], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3300, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3730, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3003, 3], [3003, 7]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3002, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1003/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [903, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '709/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[476, 2],
                 [1005, 3],
                 [1092, 1],
                 [1140, 2],
                 [2416, 2],
                 [2727, 2],
                 [3540, 3],
                 [3809, 1],
                 [3822, 1],
                 [4130, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 384],
     ['deny', 836],
     ['allow', 0],
     ['deny', 249],
     ['allow', 0],
     ['deny', 167],
     ['deny', 154],
     ['allow', 0]],
    '77/250']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [400, 1], [1000, 2], [1404, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 100],
     ['allow', 0],
     ['deny', 96]],
    '101/125']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10004, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 330], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3400, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3740, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3004, 3], [3004, 8]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3336, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '376/125']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [904, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '89/125']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[295, 3],
                 [481, 2],
                 [603, 2],
                 [1079, 3],
                 [1690, 3],
                 [1700, 3],
                 [2433, 3],
                 [3280, 3],
                 [4573, 3],
                 [4680, 3]]},
   [[['allow', 0],
     ['deny', 314],
     ['deny', 192],
     ['deny', 216],
     ['allow', 0],
     ['deny', 1095],
     ['deny', 362],
     ['allow', 0],
     ['allow', 0],
     ['deny', 1115]],
    '77/100']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [500, 1], [1000, 2], [1405, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 500],
     ['allow', 0]],
    '81/100']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10005, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 329], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3500, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3750, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3005, 3], [3005, 9]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3670, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '401/100']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [905, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '143/200']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1144, 3],
                 [1657, 3],
                 [1896, 3],
                 [2302, 2],
                 [2570, 2],
                 [3012, 1],
                 [3025, 1],
                 [3251, 1],
                 [4294, 1],
                 [4860, 2]]},
   [[['allow', 0],
     ['deny', 487],
     ['deny', 248],
     ['allow', 0],
     ['deny', 74],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0]],
    '54/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 fixture	Actual	Expected	Outcome
burst then refill	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 400], ['allow', 0], ['deny', 99]], '401/500']`	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 400], ['allow', 0], ['deny', 99]], '401/500']`	Passed
idle overflow capped	`[[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']`	`[[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']`	Passed
clock regression	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '33/10']`	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']`	Failed
small clock step back	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '59/100']`	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']`	Failed
oversize cost	`[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']`	`[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']`	Passed
exact boundary after refill	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']`	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']`	Passed
fractional shortfall	`[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']`	`[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']`	Passed
random stream	`[[['allow', 0], ['allow', 0], ['deny', 126], ['deny', 581], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 439], ['deny', 220]], '64/25']`	`[[['allow', 0], ['allow', 0], ['deny', 126], ['deny', 581], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 439], ['deny', 220]], '64/25']`	Passed

SHA-256 / 1c8796496d2ad39fdbec5e80c25f605b1db195900d0d23cdb74353abac278776

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):
    C = x['capacity']
    rate = x['rate']
    tokens = Fraction(C)
    last = 0
    out = []
    for t, cost in x['requests']:
        elapsed = max(0, t - last)
        tokens = min(Fraction(C), tokens + Fraction(elapsed * rate, 1000))
        last = max(last, t)
        if cost > C:
            out.append(['never', 0])
        elif tokens >= cost:
            tokens -= cost
            out.append(['allow', 0])
        else:
            out.append(['deny', math.ceil((cost - tokens) * 1000 / rate)])
    return [out, str(tokens)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [100, 1], [1000, 2], [1401, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 400],
     ['allow', 0],
     ['deny', 99]],
    '401/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10001, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3100, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3710, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3001, 3], [3001, 5]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2334, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [901, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1025, 1],
                 [1038, 3],
                 [1399, 1],
                 [1944, 3],
                 [2745, 1],
                 [2753, 1],
                 [3169, 1],
                 [4025, 1],
                 [4086, 3],
                 [4305, 3]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 126],
     ['deny', 581],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 439],
     ['deny', 220]],
    '64/25']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [200, 1], [1000, 2], [1402, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 300],
     ['allow', 0],
     ['deny', 98]],
    '201/250']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10002, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 332], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3200, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3720, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3002, 3], [3002, 6]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [2668, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '251/250']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [902, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '353/500']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[679, 3],
                 [889, 1],
                 [1479, 1],
                 [1523, 1],
                 [1681, 1],
                 [2074, 3],
                 [2401, 2],
                 [2669, 3],
                 [4187, 3],
                 [4538, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 156],
     ['allow', 0],
     ['deny', 1105],
     ['deny', 278],
     ['deny', 510],
     ['allow', 0],
     ['allow', 0]],
    '351/500']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [300, 1], [1000, 2], [1403, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 200],
     ['allow', 0],
     ['deny', 97]],
    '403/500']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10003, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 331], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3300, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3730, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3003, 3], [3003, 7]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3002, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1003/500']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [903, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '709/1000']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[476, 2],
                 [1005, 3],
                 [1092, 1],
                 [1140, 2],
                 [2416, 2],
                 [2727, 2],
                 [3540, 3],
                 [3809, 1],
                 [3822, 1],
                 [4130, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['deny', 384],
     ['deny', 836],
     ['allow', 0],
     ['deny', 249],
     ['allow', 0],
     ['deny', 167],
     ['deny', 154],
     ['allow', 0]],
    '77/250']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [400, 1], [1000, 2], [1404, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 100],
     ['allow', 0],
     ['deny', 96]],
    '101/125']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10004, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 330], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3400, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3740, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3004, 3], [3004, 8]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3336, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '376/125']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [904, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '89/125']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[295, 3],
                 [481, 2],
                 [603, 2],
                 [1079, 3],
                 [1690, 3],
                 [1700, 3],
                 [2433, 3],
                 [3280, 3],
                 [4573, 3],
                 [4680, 3]]},
   [[['allow', 0],
     ['deny', 314],
     ['deny', 192],
     ['deny', 216],
     ['allow', 0],
     ['deny', 1095],
     ['deny', 362],
     ['allow', 0],
     ['allow', 0],
     ['deny', 1115]],
    '77/100']]],
 [['burst then refill',
   {'capacity': 5,
    'rate': 2,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [500, 1], [1000, 2], [1405, 1]]},
   [[['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['deny', 500],
     ['allow', 0]],
    '81/100']],
  ['idle overflow capped',
   {'capacity': 4, 'rate': 3, 'requests': [[0, 4], [10000, 4], [10005, 1], [10200, 1]]},
   [[['allow', 0], ['allow', 0], ['deny', 329], ['deny', 134]], '3/5']],
  ['clock regression',
   {'capacity': 6,
    'rate': 1,
    'requests': [[0, 6], [5000, 1], [3500, 1], [5500, 1], [6000, 1], [6400, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']],
  ['small clock step back',
   {'capacity': 6, 'rate': 1, 'requests': [[0, 6], [4000, 1], [3750, 1], [4000, 1], [4300, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']],
  ['oversize cost',
   {'capacity': 3, 'rate': 1, 'requests': [[0, 4], [0, 3], [3005, 3], [3005, 9]]},
   [[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']],
  ['exact boundary after refill',
   {'capacity': 10, 'rate': 3, 'requests': [[0, 10], [1000, 3], [2000, 3], [3670, 1]]},
   [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '401/100']],
  ['fractional shortfall',
   {'capacity': 5, 'rate': 3, 'requests': [[0, 5], [500, 2], [700, 1], [905, 1]]},
   [[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '143/200']],
  ['random stream',
   {'capacity': 4,
    'rate': 2,
    'requests': [[1144, 3],
                 [1657, 3],
                 [1896, 3],
                 [2302, 2],
                 [2570, 2],
                 [3012, 1],
                 [3025, 1],
                 [3251, 1],
                 [4294, 1],
                 [4860, 2]]},
   [[['allow', 0],
     ['deny', 487],
     ['deny', 248],
     ['allow', 0],
     ['deny', 74],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0],
     ['allow', 0]],
    '54/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 fixture	Actual	Expected	Outcome
burst then refill	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 400], ['allow', 0], ['deny', 99]], '401/500']`	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 400], ['allow', 0], ['deny', 99]], '401/500']`	Passed
idle overflow capped	`[[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']`	`[[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']`	Passed
clock regression	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']`	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '7/5']`	Passed
small clock step back	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']`	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '3/10']`	Passed
oversize cost	`[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']`	`[[['never', 0], ['allow', 0], ['allow', 0], ['never', 0]], '0']`	Passed
exact boundary after refill	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']`	`[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0]], '1/500']`	Passed
fractional shortfall	`[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']`	`[[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']`	Passed
random stream	`[[['allow', 0], ['allow', 0], ['deny', 126], ['deny', 581], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 439], ['deny', 220]], '64/25']`	`[[['allow', 0], ['allow', 0], ['deny', 126], ['deny', 581], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 439], ['deny', 220]], '64/25']`	Passed

SHA-256 / 2612351e5227e74d969039fe7a26772663589e8216880ec6294649255dde1d2c

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

Case digest / d30745b96b9e0c6f30f4f33d3706a61260f3e5b59baba6927850243eb95ea2ed