FA-73396 / Rate limiter algorithms / Open access

Generic cell rate algorithm limiter: oversize check compares units with time · case 01

Requests larger than the burst receive retry hints that can never succeed.

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

ROOT CAUSE

The impossible-quantity check compares the quantity against B*T milliseconds.

VERIFIED REPAIR

Reject quantities greater than B as never satisfiable.

Unsuccessful approach: Rejecting q equal to B refuses a request an idle limiter can admit.

Case contract

Input {period_ms T, burst B, requests [[t, quantity]]}. State TAT starts at 0. A quantity above B is ["never", 0, 0]. Otherwise tat = max(TAT, t) and new_tat = tat + q*T; the request is allowed iff new_tat - t <= B*T, in which case TAT = new_tat and remaining = floor((B*T - (TAT - t))/T). A denied request leaves TAT unchanged and reports retry_after = new_tat - B*T - t and remaining floor((B*T - (tat - t))/T). Return [[decision, retry_after, remaining]].

Why this case matters

GCRA limiters store a single theoretical-arrival timestamp per key; every decision and header value is derived from it, so small formula errors leak bursts or starve clients.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    T = x['period_ms']
    B = x['burst']
    TAT = 0
    out = []
    for t, q in x['requests']:
        if q > B * T:
            out.append(['never', 0, 0])
            continue
        tat = max(TAT, t)
        new_tat = tat + q * T
        if new_tat - t <= B * T:
            TAT = new_tat
            out.append(['allow', 0, (B * T - (TAT - t)) // T])
        else:
            out.append(['deny', new_tat - B * T - t, (B * T - (tat - t)) // T])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst of five',
   {'burst': 5,
    'period_ms': 100,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [101, 1], [250, 1]]},
   [['allow', 0, 4],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['idle credit bounded',
   {'burst': 3,
    'period_ms': 50,
    'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10010, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 50, 0],
    ['deny', 40, 0]]],
  ['denied requests do not push tat',
   {'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [101, 1], [200, 1]]},
   [['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['multi-unit request',
   {'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [41, 2], [5, 5]]},
   [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
  ['exact tolerance edge',
   {'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [201, 1]]},
   [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
  ['random traffic',
   {'burst': 4,
    'period_ms': 100,
    'requests': [[8, 2],
                 [57, 1],
                 [84, 2],
                 [163, 2],
                 [383, 1],
                 [525, 2],
                 [624, 2],
                 [997, 1],
                 [1402, 2],
                 [1869, 2]]},
   [['allow', 0, 2],
    ['allow', 0, 1],
    ['deny', 24, 1],
    ['allow', 0, 0],
    ['allow', 0, 1],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 2]]]],
 [['burst of five',
   {'burst': 5,
    'period_ms': 100,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [102, 1], [250, 1]]},
   [['allow', 0, 4],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['idle credit bounded',
   {'burst': 3,
    'period_ms': 50,
    'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10020, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 50, 0],
    ['deny', 30, 0]]],
  ['denied requests do not push tat',
   {'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [102, 1], [200, 1]]},
   [['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['multi-unit request',
   {'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [42, 2], [10, 5]]},
   [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
  ['exact tolerance edge',
   {'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [202, 1]]},
   [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
  ['random traffic',
   {'burst': 4,
    'period_ms': 100,
    'requests': [[67, 2],
                 [137, 1],
                 [249, 1],
                 [594, 1],
                 [681, 2],
                 [826, 1],
                 [1250, 1],
                 [1428, 1],
                 [1433, 2],
                 [1483, 2]]},
   [['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 1],
    ['allow', 0, 3],
    ['allow', 0, 1],
    ['allow', 0, 2],
    ['allow', 0, 3],
    ['allow', 0, 3],
    ['allow', 0, 1],
    ['deny', 45, 1]]]],
 [['burst of five',
   {'burst': 5,
    'period_ms': 100,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [103, 1], [250, 1]]},
   [['allow', 0, 4],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['idle credit bounded',
   {'burst': 3,
    'period_ms': 50,
    'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10030, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 50, 0],
    ['deny', 20, 0]]],
  ['denied requests do not push tat',
   {'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [103, 1], [200, 1]]},
   [['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['multi-unit request',
   {'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [43, 2], [15, 5]]},
   [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
  ['exact tolerance edge',
   {'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [203, 1]]},
   [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
  ['random traffic',
   {'burst': 4,
    'period_ms': 100,
    'requests': [[56, 1],
                 [339, 2],
                 [932, 1],
                 [1203, 2],
                 [1327, 2],
                 [1505, 1],
                 [1614, 2],
                 [1774, 2],
                 [1930, 1],
                 [1938, 2]]},
   [['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['allow', 0, 1],
    ['deny', 65, 1]]]],
 [['burst of five',
   {'burst': 5,
    'period_ms': 100,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [104, 1], [250, 1]]},
   [['allow', 0, 4],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['idle credit bounded',
   {'burst': 3,
    'period_ms': 50,
    'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10040, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 50, 0],
    ['deny', 10, 0]]],
  ['denied requests do not push tat',
   {'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [104, 1], [200, 1]]},
   [['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['multi-unit request',
   {'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [44, 2], [20, 5]]},
   [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
  ['exact tolerance edge',
   {'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [204, 1]]},
   [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
  ['random traffic',
   {'burst': 4,
    'period_ms': 100,
    'requests': [[415, 1],
                 [479, 1],
                 [592, 1],
                 [602, 2],
                 [683, 2],
                 [973, 2],
                 [1658, 1],
                 [1708, 2],
                 [1784, 1],
                 [1789, 2]]},
   [['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 0],
    ['deny', 32, 1],
    ['allow', 0, 2],
    ['allow', 0, 3],
    ['allow', 0, 1],
    ['allow', 0, 1],
    ['deny', 69, 1]]]],
 [['burst of five',
   {'burst': 5,
    'period_ms': 100,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [105, 1], [250, 1]]},
   [['allow', 0, 4],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['idle credit bounded',
   {'burst': 3,
    'period_ms': 50,
    'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10050, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 50, 0],
    ['allow', 0, 0]]],
  ['denied requests do not push tat',
   {'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [105, 1], [200, 1]]},
   [['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['multi-unit request',
   {'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [45, 2], [25, 5]]},
   [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
  ['exact tolerance edge',
   {'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [205, 1]]},
   [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
  ['random traffic',
   {'burst': 4,
    'period_ms': 100,
    'requests': [[293, 2],
                 [620, 2],
                 [635, 1],
                 [1275, 2],
                 [1525, 2],
                 [1565, 1],
                 [1595, 2],
                 [1614, 1],
                 [1806, 2],
                 [1874, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['deny', 30, 1],
    ['allow', 0, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]]]]
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 of five	`[['allow', 0, 4], ['allow', 0, 3], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]]`	`[['allow', 0, 4], ['allow', 0, 3], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]]`	Passed
idle credit bounded	`[['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 50, 0], ['deny', 40, 0]]`	`[['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 50, 0], ['deny', 40, 0]]`	Passed
denied requests do not push tat	`[['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]]`	`[['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]]`	Passed
multi-unit request	`[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['deny', 115, -1]]`	`[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]`	Failed
exact tolerance edge	`[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]`	`[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]`	Passed
random traffic	`[['allow', 0, 2], ['allow', 0, 1], ['deny', 24, 1], ['allow', 0, 0], ['allow', 0, 1], ['allow', 0, 1], ['allow', 0, 0], ['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 2]]`	`[['allow', 0, 2], ['allow', 0, 1], ['deny', 24, 1], ['allow', 0, 0], ['allow', 0, 1], ['allow', 0, 1], ['allow', 0, 0], ['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 2]]`	Passed

SHA-256 / c7812635dc972855542693d31ffcb85bae9ca33aeae0838295d2ebdfe7f1e585

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    T = x['period_ms']
    B = x['burst']
    TAT = 0
    out = []
    for t, q in x['requests']:
        if q >= B:
            out.append(['never', 0, 0])
            continue
        tat = max(TAT, t)
        new_tat = tat + q * T
        if new_tat - t <= B * T:
            TAT = new_tat
            out.append(['allow', 0, (B * T - (TAT - t)) // T])
        else:
            out.append(['deny', new_tat - B * T - t, (B * T - (tat - t)) // T])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst of five',
   {'burst': 5,
    'period_ms': 100,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [101, 1], [250, 1]]},
   [['allow', 0, 4],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['idle credit bounded',
   {'burst': 3,
    'period_ms': 50,
    'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10010, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 50, 0],
    ['deny', 40, 0]]],
  ['denied requests do not push tat',
   {'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [101, 1], [200, 1]]},
   [['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['multi-unit request',
   {'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [41, 2], [5, 5]]},
   [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
  ['exact tolerance edge',
   {'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [201, 1]]},
   [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
  ['random traffic',
   {'burst': 4,
    'period_ms': 100,
    'requests': [[8, 2],
                 [57, 1],
                 [84, 2],
                 [163, 2],
                 [383, 1],
                 [525, 2],
                 [624, 2],
                 [997, 1],
                 [1402, 2],
                 [1869, 2]]},
   [['allow', 0, 2],
    ['allow', 0, 1],
    ['deny', 24, 1],
    ['allow', 0, 0],
    ['allow', 0, 1],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 2]]]],
 [['burst of five',
   {'burst': 5,
    'period_ms': 100,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [102, 1], [250, 1]]},
   [['allow', 0, 4],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['idle credit bounded',
   {'burst': 3,
    'period_ms': 50,
    'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10020, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 50, 0],
    ['deny', 30, 0]]],
  ['denied requests do not push tat',
   {'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [102, 1], [200, 1]]},
   [['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['multi-unit request',
   {'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [42, 2], [10, 5]]},
   [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
  ['exact tolerance edge',
   {'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [202, 1]]},
   [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
  ['random traffic',
   {'burst': 4,
    'period_ms': 100,
    'requests': [[67, 2],
                 [137, 1],
                 [249, 1],
                 [594, 1],
                 [681, 2],
                 [826, 1],
                 [1250, 1],
                 [1428, 1],
                 [1433, 2],
                 [1483, 2]]},
   [['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 1],
    ['allow', 0, 3],
    ['allow', 0, 1],
    ['allow', 0, 2],
    ['allow', 0, 3],
    ['allow', 0, 3],
    ['allow', 0, 1],
    ['deny', 45, 1]]]],
 [['burst of five',
   {'burst': 5,
    'period_ms': 100,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [103, 1], [250, 1]]},
   [['allow', 0, 4],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['idle credit bounded',
   {'burst': 3,
    'period_ms': 50,
    'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10030, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 50, 0],
    ['deny', 20, 0]]],
  ['denied requests do not push tat',
   {'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [103, 1], [200, 1]]},
   [['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['multi-unit request',
   {'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [43, 2], [15, 5]]},
   [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
  ['exact tolerance edge',
   {'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [203, 1]]},
   [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
  ['random traffic',
   {'burst': 4,
    'period_ms': 100,
    'requests': [[56, 1],
                 [339, 2],
                 [932, 1],
                 [1203, 2],
                 [1327, 2],
                 [1505, 1],
                 [1614, 2],
                 [1774, 2],
                 [1930, 1],
                 [1938, 2]]},
   [['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['allow', 0, 1],
    ['deny', 65, 1]]]],
 [['burst of five',
   {'burst': 5,
    'period_ms': 100,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [104, 1], [250, 1]]},
   [['allow', 0, 4],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['idle credit bounded',
   {'burst': 3,
    'period_ms': 50,
    'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10040, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 50, 0],
    ['deny', 10, 0]]],
  ['denied requests do not push tat',
   {'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [104, 1], [200, 1]]},
   [['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['multi-unit request',
   {'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [44, 2], [20, 5]]},
   [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
  ['exact tolerance edge',
   {'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [204, 1]]},
   [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
  ['random traffic',
   {'burst': 4,
    'period_ms': 100,
    'requests': [[415, 1],
                 [479, 1],
                 [592, 1],
                 [602, 2],
                 [683, 2],
                 [973, 2],
                 [1658, 1],
                 [1708, 2],
                 [1784, 1],
                 [1789, 2]]},
   [['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 0],
    ['deny', 32, 1],
    ['allow', 0, 2],
    ['allow', 0, 3],
    ['allow', 0, 1],
    ['allow', 0, 1],
    ['deny', 69, 1]]]],
 [['burst of five',
   {'burst': 5,
    'period_ms': 100,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [105, 1], [250, 1]]},
   [['allow', 0, 4],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['idle credit bounded',
   {'burst': 3,
    'period_ms': 50,
    'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10050, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 50, 0],
    ['allow', 0, 0]]],
  ['denied requests do not push tat',
   {'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [105, 1], [200, 1]]},
   [['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['multi-unit request',
   {'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [45, 2], [25, 5]]},
   [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
  ['exact tolerance edge',
   {'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [205, 1]]},
   [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
  ['random traffic',
   {'burst': 4,
    'period_ms': 100,
    'requests': [[293, 2],
                 [620, 2],
                 [635, 1],
                 [1275, 2],
                 [1525, 2],
                 [1565, 1],
                 [1595, 2],
                 [1614, 1],
                 [1806, 2],
                 [1874, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['deny', 30, 1],
    ['allow', 0, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]]]]
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 of five	`[['allow', 0, 4], ['allow', 0, 3], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]]`	`[['allow', 0, 4], ['allow', 0, 3], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]]`	Passed
idle credit bounded	`[['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 50, 0], ['deny', 40, 0]]`	`[['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 50, 0], ['deny', 40, 0]]`	Passed
denied requests do not push tat	`[['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]]`	`[['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]]`	Passed
multi-unit request	`[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]`	`[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]`	Passed
exact tolerance edge	`[['never', 0, 0], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 1]]`	`[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]`	Failed
random traffic	`[['allow', 0, 2], ['allow', 0, 1], ['deny', 24, 1], ['allow', 0, 0], ['allow', 0, 1], ['allow', 0, 1], ['allow', 0, 0], ['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 2]]`	`[['allow', 0, 2], ['allow', 0, 1], ['deny', 24, 1], ['allow', 0, 0], ['allow', 0, 1], ['allow', 0, 1], ['allow', 0, 0], ['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 2]]`	Passed

SHA-256 / 81a18af4b7fd2f7aa8d2645a523b491dc92b9aa83d3102f17e5e1ac98c975e2b

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    T = x['period_ms']
    B = x['burst']
    TAT = 0
    out = []
    for t, q in x['requests']:
        if q > B:
            out.append(['never', 0, 0])
            continue
        tat = max(TAT, t)
        new_tat = tat + q * T
        if new_tat - t <= B * T:
            TAT = new_tat
            out.append(['allow', 0, (B * T - (TAT - t)) // T])
        else:
            out.append(['deny', new_tat - B * T - t, (B * T - (tat - t)) // T])
    return out
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['burst of five',
   {'burst': 5,
    'period_ms': 100,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [101, 1], [250, 1]]},
   [['allow', 0, 4],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['idle credit bounded',
   {'burst': 3,
    'period_ms': 50,
    'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10010, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 50, 0],
    ['deny', 40, 0]]],
  ['denied requests do not push tat',
   {'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [101, 1], [200, 1]]},
   [['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['multi-unit request',
   {'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [41, 2], [5, 5]]},
   [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
  ['exact tolerance edge',
   {'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [201, 1]]},
   [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
  ['random traffic',
   {'burst': 4,
    'period_ms': 100,
    'requests': [[8, 2],
                 [57, 1],
                 [84, 2],
                 [163, 2],
                 [383, 1],
                 [525, 2],
                 [624, 2],
                 [997, 1],
                 [1402, 2],
                 [1869, 2]]},
   [['allow', 0, 2],
    ['allow', 0, 1],
    ['deny', 24, 1],
    ['allow', 0, 0],
    ['allow', 0, 1],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 2]]]],
 [['burst of five',
   {'burst': 5,
    'period_ms': 100,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [102, 1], [250, 1]]},
   [['allow', 0, 4],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['idle credit bounded',
   {'burst': 3,
    'period_ms': 50,
    'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10020, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 50, 0],
    ['deny', 30, 0]]],
  ['denied requests do not push tat',
   {'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [102, 1], [200, 1]]},
   [['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['multi-unit request',
   {'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [42, 2], [10, 5]]},
   [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
  ['exact tolerance edge',
   {'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [202, 1]]},
   [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
  ['random traffic',
   {'burst': 4,
    'period_ms': 100,
    'requests': [[67, 2],
                 [137, 1],
                 [249, 1],
                 [594, 1],
                 [681, 2],
                 [826, 1],
                 [1250, 1],
                 [1428, 1],
                 [1433, 2],
                 [1483, 2]]},
   [['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 1],
    ['allow', 0, 3],
    ['allow', 0, 1],
    ['allow', 0, 2],
    ['allow', 0, 3],
    ['allow', 0, 3],
    ['allow', 0, 1],
    ['deny', 45, 1]]]],
 [['burst of five',
   {'burst': 5,
    'period_ms': 100,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [103, 1], [250, 1]]},
   [['allow', 0, 4],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['idle credit bounded',
   {'burst': 3,
    'period_ms': 50,
    'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10030, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 50, 0],
    ['deny', 20, 0]]],
  ['denied requests do not push tat',
   {'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [103, 1], [200, 1]]},
   [['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['multi-unit request',
   {'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [43, 2], [15, 5]]},
   [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
  ['exact tolerance edge',
   {'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [203, 1]]},
   [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
  ['random traffic',
   {'burst': 4,
    'period_ms': 100,
    'requests': [[56, 1],
                 [339, 2],
                 [932, 1],
                 [1203, 2],
                 [1327, 2],
                 [1505, 1],
                 [1614, 2],
                 [1774, 2],
                 [1930, 1],
                 [1938, 2]]},
   [['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['allow', 0, 1],
    ['deny', 65, 1]]]],
 [['burst of five',
   {'burst': 5,
    'period_ms': 100,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [104, 1], [250, 1]]},
   [['allow', 0, 4],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['idle credit bounded',
   {'burst': 3,
    'period_ms': 50,
    'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10040, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 50, 0],
    ['deny', 10, 0]]],
  ['denied requests do not push tat',
   {'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [104, 1], [200, 1]]},
   [['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['multi-unit request',
   {'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [44, 2], [20, 5]]},
   [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
  ['exact tolerance edge',
   {'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [204, 1]]},
   [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
  ['random traffic',
   {'burst': 4,
    'period_ms': 100,
    'requests': [[415, 1],
                 [479, 1],
                 [592, 1],
                 [602, 2],
                 [683, 2],
                 [973, 2],
                 [1658, 1],
                 [1708, 2],
                 [1784, 1],
                 [1789, 2]]},
   [['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 0],
    ['deny', 32, 1],
    ['allow', 0, 2],
    ['allow', 0, 3],
    ['allow', 0, 1],
    ['allow', 0, 1],
    ['deny', 69, 1]]]],
 [['burst of five',
   {'burst': 5,
    'period_ms': 100,
    'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [0, 1], [105, 1], [250, 1]]},
   [['allow', 0, 4],
    ['allow', 0, 3],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['idle credit bounded',
   {'burst': 3,
    'period_ms': 50,
    'requests': [[0, 1], [10000, 1], [10000, 1], [10000, 1], [10000, 1], [10050, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 50, 0],
    ['allow', 0, 0]]],
  ['denied requests do not push tat',
   {'burst': 2, 'period_ms': 100, 'requests': [[0, 1], [0, 1], [0, 1], [0, 1], [105, 1], [200, 1]]},
   [['allow', 0, 1],
    ['allow', 0, 0],
    ['deny', 100, 0],
    ['deny', 100, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]],
  ['multi-unit request',
   {'burst': 4, 'period_ms': 20, 'requests': [[0, 3], [0, 2], [45, 2], [25, 5]]},
   [['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]],
  ['exact tolerance edge',
   {'burst': 3, 'period_ms': 100, 'requests': [[0, 3], [100, 1], [150, 1], [205, 1]]},
   [['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]],
  ['random traffic',
   {'burst': 4,
    'period_ms': 100,
    'requests': [[293, 2],
                 [620, 2],
                 [635, 1],
                 [1275, 2],
                 [1525, 2],
                 [1565, 1],
                 [1595, 2],
                 [1614, 1],
                 [1806, 2],
                 [1874, 1]]},
   [['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['allow', 0, 2],
    ['allow', 0, 2],
    ['allow', 0, 1],
    ['deny', 30, 1],
    ['allow', 0, 0],
    ['allow', 0, 0],
    ['allow', 0, 0]]]]]
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 of five	`[['allow', 0, 4], ['allow', 0, 3], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]]`	`[['allow', 0, 4], ['allow', 0, 3], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]]`	Passed
idle credit bounded	`[['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 50, 0], ['deny', 40, 0]]`	`[['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 1], ['allow', 0, 0], ['deny', 50, 0], ['deny', 40, 0]]`	Passed
denied requests do not push tat	`[['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]]`	`[['allow', 0, 1], ['allow', 0, 0], ['deny', 100, 0], ['deny', 100, 0], ['allow', 0, 0], ['allow', 0, 0]]`	Passed
multi-unit request	`[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]`	`[['allow', 0, 1], ['deny', 20, 1], ['allow', 0, 1], ['never', 0, 0]]`	Passed
exact tolerance edge	`[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]`	`[['allow', 0, 0], ['allow', 0, 0], ['deny', 50, 0], ['allow', 0, 0]]`	Passed
random traffic	`[['allow', 0, 2], ['allow', 0, 1], ['deny', 24, 1], ['allow', 0, 0], ['allow', 0, 1], ['allow', 0, 1], ['allow', 0, 0], ['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 2]]`	`[['allow', 0, 2], ['allow', 0, 1], ['deny', 24, 1], ['allow', 0, 0], ['allow', 0, 1], ['allow', 0, 1], ['allow', 0, 0], ['allow', 0, 2], ['allow', 0, 2], ['allow', 0, 2]]`	Passed

SHA-256 / 4813819e5702a7ff6ba793d3d1f2ce7cee700f3f6586f8372b17a723b314ce6d

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

Case digest / c2597db9200da6762c76745090bf01c404bf8473dc02ad2097da1d93b839eae9