FA-73787 / Rate limiter algorithms / Member archive

Rolling window over a ring of sub-window counters: reused slot keeps a lapped count · case 02

Traffic from one full window ago is counted again when its slot comes around.

Member previewVariant 2 · 3 implementations · 6 checks per implementation

Case contract

Input {slots N, slot_ms B, limit, requests [t]} with nondecreasing t. Epoch e = t div B maps to slot e mod N; each slot remembers the epoch it counts and is zeroed when reused for a newer epoch. The rolling total sums slots whose epoch lies in (e - N, e]. Admit while total < limit and count the request in the current slot. Return [decisions, slot counts, slot epochs].

Why this case matters

Rolling-window limiters in service meshes keep a ring of small buckets; forgetting to zero reused buckets or summing stale ones replays old traffic into current decisions.

One recorded failure

Sample boundary fixture

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

Boundary fixture	Actual	Expected	Outcome
slot reused after a lap	`[["allow", "allow", "allow", "deny", "deny", "deny", "deny"], [3, 0, 0, 0], [4, -1, -1, -1]]`	`[["allow", "allow", "allow", "allow", "allow", "allow", "deny"], [3, 0, 0, 0], [4, -1, -1, -1]]`	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.