FAILURE MAP
← Case archive

FA-73361 / Rate limiter algorithms / Open access

Token bucket with lazy exact refill: advertised wait rounds down · case 01

Clients that honour the advertised wait arrive a fraction of a millisecond early and are denied again.

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

ROOT CAUSE

The wait in milliseconds is truncated instead of rounded up.

THE FAILURE

The wait in milliseconds is truncated instead of rounded up.

Unsuccessful approach: Rounding up to whole seconds before converting overstates the wait.

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 = 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', int((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 fixtureActualExpectedOutcome
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', 332], ['deny', 133]], '3/5'][[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']Failed
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', 166], ['allow', 0], ['allow', 0]], '703/1000'][[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']Failed
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 / 1ae3adefc3e88f7264a88968262e3b49bca8cbe1896498bc0c832509ac4b7cbf

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 = 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) / rate) * 1000])
    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 fixtureActualExpectedOutcome
burst then refill[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 1000], ['allow', 0], ['deny', 1000]], '401/500'][[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 400], ['allow', 0], ['deny', 99]], '401/500']Failed
idle overflow capped[[['allow', 0], ['allow', 0], ['deny', 1000], ['deny', 1000]], '3/5'][[['allow', 0], ['allow', 0], ['deny', 333], ['deny', 134]], '3/5']Failed
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', 1000], ['allow', 0], ['allow', 0]], '703/1000'][[['allow', 0], ['deny', 167], ['allow', 0], ['allow', 0]], '703/1000']Failed
random stream[[['allow', 0], ['allow', 0], ['deny', 1000], ['deny', 1000], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 1000], ['deny', 1000]], '64/25'][[['allow', 0], ['allow', 0], ['deny', 126], ['deny', 581], ['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 439], ['deny', 220]], '64/25']Failed

SHA-256 / fb1d89876b60b391ec003f7069a6ed5adf97b7303bd44b73800d80f0999002aa

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 8 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

Sign in to the archive ↗

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

Case digest / 81bc1647f5db060e91bd47d7821c1d3127bedc76a9842d3fa97d665c23e0ac9b