FA-73359 / Rate limiter algorithms / Member archive

Token bucket with lazy exact refill: impossible cost reported with a finite wait · case 04

A request larger than the bucket is told to retry after a wait that can never be satisfied.

Member previewVariant 4 · 3 implementations · 8 checks per implementation

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.

One recorded failure

Sample boundary fixture

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

Boundary fixture	Actual	Expected	Outcome
oversize cost	`[[["deny", 1000], ["allow", 0], ["allow", 0], ["deny", 8000]], "0"]`	`[[["never", 0], ["allow", 0], ["allow", 0], ["never", 0]], "0"]`	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.