FAILURE MAP
← Case archive

FA-73351 / Rate limiter algorithms / Open access

Token bucket with lazy exact refill: refill anchor rewinds on a late request · case 01

After a late timestamp the next request is credited again for time already refilled.

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

ROOT CAUSE

The refill anchor is set to the request time even when it is older than the anchor.

THE FAILURE

The refill anchor is set to the request time even when it is older than the anchor.

Unsuccessful approach: Tolerating regressions up to one second still rewinds the anchor for small clock steps.

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 = 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 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', 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 / 1ce983976b8538bb3498569917a1a07ddeb2bec9b84a55327cd26d3c498872ed

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 = t if t >= last - 1000 else last
        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 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', 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]], '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 / 7a3e91029848e1c36139fe816a56e6ef7a54a18e56e60ff3527565bb27ed126d

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 / 4413cfa9645c9126238606f14920885553ddb5c17a243d72da6d577390c6e8a4