FA-73740 / Rate limiter algorithms / Member archive

Token bucket with bounded overdraft: refill clock advances only on admission · case 05

After a denial the same interval is refilled again at the next request.

Member previewVariant 5 · 3 implementations · 6 checks per implementation

Case contract

Input {capacity, rate (tokens per second), max_debt, requests [[t_s, cost]]} with nondecreasing whole seconds. The bucket starts full; refill is min(capacity, tokens + elapsed*rate) and also repays debt. A request is admitted when the balance is positive and the post-charge balance stays >= -max_debt, so one expensive request may overdraw. Denials change nothing. Return [[decision, balance]].

Why this case matters

Cost-weighted APIs (query units, LLM tokens) let an expensive call overdraw the bucket and repay it from future refill; the overdraft rules decide fairness between cheap and expensive callers.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
overdraft then repay	`[["allow", 2], ["allow", -2], ["deny", -1], ["allow", 1], ["allow", 3]]`	`[["allow", 2], ["allow", -2], ["deny", -1], ["allow", 0], ["allow", 3]]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

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