FA-73760 / Rate limiter algorithms / Member archive

Rate limiter with a bounded per-key state table: any key with tokens counts as idle · case 05

A partially throttled key is evicted and its restrictions are forgotten.

Member previewVariant 5 · 3 implementations · 6 checks per implementation

Case contract

Input {max_keys, capacity, rate, requests [[t_s, key]]} with nondecreasing whole seconds. Each key has a token bucket (starts full, cost 1). The table holds at most max_keys keys; a new key may only evict the least recently used key whose bucket would be full after refill at the current time (so eviction cannot reset anyone's limit); if no key is idle the request is "overflow" and nothing changes. Every admitted or denied request refreshes the key's recency. Return [results, keys in LRU order].

Why this case matters

Edge limiters cap memory with a fixed-size key table; evicting a key that is still being throttled hands an attacker a fresh bucket.

One recorded failure

Sample boundary fixture

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

Boundary fixture	Actual	Expected	Outcome
busy key not evicted	`[["allow", "allow", "allow", "allow", "allow"], ["b", "c"]]`	`[["allow", "allow", "allow", "allow", "allow"], ["a", "c"]]`	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.