FA-73825 / Rate limiter algorithms / Member archive

Max-min fair split of a global rate limit: share divided among satisfied clients too · case 05

Capacity is split among clients that no longer need it, needing extra rounds and misallocating the remainder.

Member previewVariant 5 · 3 implementations · 10 checks per implementation

Case contract

Input {capacity, demands [[client, demand]]} in integer requests per second. Clients with positive demand are active. Repeatedly give each active client min(floor(left / active count), unmet demand) and drop satisfied clients; when the per-client share rounds to zero, hand single units to active clients in ascending id order until capacity is exhausted. Return [sorted [client, allocation]], unallocated capacity].

Why this case matters

Distributed limiters split a global rate among clients or nodes by max-min fairness so light users are fully served and heavy users share the rest.

One recorded failure

Sample boundary fixture

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

Boundary fixture	Actual	Expected	Outcome
multi-round water filling	`[[["a", 1], ["b", 3], ["c", 6], ["d", 6]], 0]`	`[[["a", 1], ["b", 3], ["c", 7], ["d", 6]], 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.