FAILURE MAP
← Case archive

FA-73821 / Rate limiter algorithms / Open access

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

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

Verified by executionVariant 1 · 10 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The per-round share divides by all clients instead of the active ones.

THE FAILURE

The per-round share divides by all clients instead of the active ones.

Unsuccessful approach: Dividing the original capacity each round over-allocates once some capacity is spent.

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.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    C = x['capacity']
    need = dict(x['demands'])
    alloc = {c: 0 for c in need}
    active = sorted(c for c, d in need.items() if d > 0)
    left = C
    while active and left > 0:
        share = left // len(need)
        if share == 0:
            for c in active[:left]:
                alloc[c] += 1
            left = 0
            break
        nxt = []
        for c in active:
            give = min(share, need[c] - alloc[c])
            alloc[c] += give
            left -= give
            if alloc[c] < need[c]:
                nxt.append(c)
        active = nxt
    return [sorted([c, a] for c, a in alloc.items()), left]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 12, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 4], ['b', 4], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 6]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 5]]},
   [[['a', 3], ['b', 5]], 12]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 7], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]]},
   [[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 101]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 6]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 4]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 6]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 13, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 4], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 7]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 6]]},
   [[['a', 3], ['b', 6]], 11]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 8], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 2], ['q', 4], ['r', 8], ['s', 8], ['t', 4]]},
   [[['p', 2], ['q', 4], ['r', 6], ['s', 5], ['t', 4]], 0]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 102]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 7]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 5]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 7]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 14, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 5], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 8]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 7]]},
   [[['a', 3], ['b', 7]], 10]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 9], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 7], ['q', 8], ['r', 2], ['s', 9], ['t', 1]]},
   [[['p', 6], ['q', 6], ['r', 2], ['s', 6], ['t', 1]], 0]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 103]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 8]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 6]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 8]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 15, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 5], ['c', 5]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 9]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 8]]},
   [[['a', 3], ['b', 8]], 9]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 10], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]]},
   [[['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]], 3]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 104]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 9]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 7]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 9]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 16, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 6], ['b', 5], ['c', 5]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 10]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 9]]},
   [[['a', 3], ['b', 9]], 8]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 11], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]]},
   [[['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]], 4]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 105]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 10]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 8]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 10]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
small demand satisfied first[[['a', 2], ['b', 4], ['c', 4]], 0][[['a', 2], ['b', 4], ['c', 4]], 0]Passed
remainder to lowest ids[[['a', 4], ['b', 4], ['c', 4]], 0][[['a', 4], ['b', 4], ['c', 4]], 0]Passed
zero demand ignored[[['x', 0], ['y', 4], ['z', 3]], 0][[['x', 0], ['y', 4], ['z', 3]], 0]Passed
surplus left over[[['a', 3], ['b', 5]], 12][[['a', 3], ['b', 5]], 12]Passed
multi-round water filling[[['a', 1], ['b', 3], ['c', 6], ['d', 6]], 0][[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]Failed
random demands[[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7][[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7]Passed
second round respects unmet demand[[['a', 2], ['b', 7], ['c', 8]], 0][[['a', 2], ['b', 7], ['c', 9]], 0]Failed
tiny capacity with idle client[[['a', 0], ['b', 1], ['c', 1]], 0][[['a', 0], ['b', 1], ['c', 1]], 0]Passed
remainder ignores demand size[[['a', 1], ['b', 1], ['c', 0]], 0][[['a', 1], ['b', 1], ['c', 0]], 0]Passed
exact share satisfies[[['a', 3], ['b', 3], ['c', 3]], 0][[['a', 3], ['b', 3], ['c', 3]], 0]Passed

SHA-256 / f582af46bde9447c19bf3f5e63979020ef186953ebbca63421f3f385d36f09da

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    C = x['capacity']
    need = dict(x['demands'])
    alloc = {c: 0 for c in need}
    active = sorted(c for c, d in need.items() if d > 0)
    left = C
    while active and left > 0:
        share = C // len(active)
        if share == 0:
            for c in active[:left]:
                alloc[c] += 1
            left = 0
            break
        nxt = []
        for c in active:
            give = min(share, need[c] - alloc[c])
            alloc[c] += give
            left -= give
            if alloc[c] < need[c]:
                nxt.append(c)
        active = nxt
    return [sorted([c, a] for c, a in alloc.items()), left]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 12, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 4], ['b', 4], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 6]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 5]]},
   [[['a', 3], ['b', 5]], 12]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 7], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]]},
   [[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 101]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 6]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 4]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 6]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 13, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 4], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 7]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 6]]},
   [[['a', 3], ['b', 6]], 11]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 8], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 2], ['q', 4], ['r', 8], ['s', 8], ['t', 4]]},
   [[['p', 2], ['q', 4], ['r', 6], ['s', 5], ['t', 4]], 0]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 102]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 7]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 5]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 7]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 14, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 5], ['c', 4]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 8]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 7]]},
   [[['a', 3], ['b', 7]], 10]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 9], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 7], ['q', 8], ['r', 2], ['s', 9], ['t', 1]]},
   [[['p', 6], ['q', 6], ['r', 2], ['s', 6], ['t', 1]], 0]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 103]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 8]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 6]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 8]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 15, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 5], ['b', 5], ['c', 5]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 9]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 8]]},
   [[['a', 3], ['b', 8]], 9]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 10], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]]},
   [[['p', 2], ['q', 0], ['r', 5], ['s', 3], ['t', 8]], 3]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 104]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 9]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 7]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 9]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]],
 [['small demand satisfied first',
   {'capacity': 10, 'demands': [['a', 2], ['b', 8], ['c', 8]]},
   [[['a', 2], ['b', 4], ['c', 4]], 0]],
  ['remainder to lowest ids',
   {'capacity': 16, 'demands': [['b', 20], ['a', 20], ['c', 20]]},
   [[['a', 6], ['b', 5], ['c', 5]], 0]],
  ['zero demand ignored',
   {'capacity': 7, 'demands': [['x', 0], ['y', 5], ['z', 10]]},
   [[['x', 0], ['y', 4], ['z', 3]], 0]],
  ['surplus left over',
   {'capacity': 20, 'demands': [['a', 3], ['b', 9]]},
   [[['a', 3], ['b', 9]], 8]],
  ['multi-round water filling',
   {'capacity': 17, 'demands': [['a', 1], ['b', 3], ['c', 11], ['d', 20]]},
   [[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]],
  ['random demands',
   {'capacity': 21, 'demands': [['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]]},
   [[['p', 1], ['q', 3], ['r', 0], ['s', 6], ['t', 7]], 4]],
  ['second round respects unmet demand',
   {'capacity': 18, 'demands': [['a', 2], ['b', 7], ['c', 105]]},
   [[['a', 2], ['b', 7], ['c', 9]], 0]],
  ['tiny capacity with idle client',
   {'capacity': 2, 'demands': [['a', 0], ['b', 5], ['c', 10]]},
   [[['a', 0], ['b', 1], ['c', 1]], 0]],
  ['remainder ignores demand size',
   {'capacity': 2, 'demands': [['a', 9], ['b', 3], ['c', 8]]},
   [[['a', 1], ['b', 1], ['c', 0]], 0]],
  ['exact share satisfies',
   {'capacity': 9, 'demands': [['a', 3], ['b', 3], ['c', 10]]},
   [[['a', 3], ['b', 3], ['c', 3]], 0]]]]
for label, args, expected in cases[N - 1]:
    check(label, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
small demand satisfied first[[['a', 2], ['b', 8], ['c', 8]], -8][[['a', 2], ['b', 4], ['c', 4]], 0]Failed
remainder to lowest ids[[['a', 4], ['b', 4], ['c', 4]], 0][[['a', 4], ['b', 4], ['c', 4]], 0]Passed
zero demand ignored[[['x', 0], ['y', 5], ['z', 6]], -4][[['x', 0], ['y', 4], ['z', 3]], 0]Failed
surplus left over[[['a', 3], ['b', 5]], 12][[['a', 3], ['b', 5]], 12]Passed
multi-round water filling[[['a', 1], ['b', 3], ['c', 7], ['d', 12]], -6][[['a', 1], ['b', 3], ['c', 7], ['d', 6]], 0]Failed
random demands[[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7][[['p', 0], ['q', 3], ['r', 5], ['s', 5], ['t', 1]], 7]Passed
second round respects unmet demand[[['a', 2], ['b', 7], ['c', 15]], -6][[['a', 2], ['b', 7], ['c', 9]], 0]Failed
tiny capacity with idle client[[['a', 0], ['b', 1], ['c', 1]], 0][[['a', 0], ['b', 1], ['c', 1]], 0]Passed
remainder ignores demand size[[['a', 1], ['b', 1], ['c', 0]], 0][[['a', 1], ['b', 1], ['c', 0]], 0]Passed
exact share satisfies[[['a', 3], ['b', 3], ['c', 3]], 0][[['a', 3], ['b', 3], ['c', 3]], 0]Passed

SHA-256 / 4a4f0fb429341789d2358ec0a02be6e478f842ab21b62d41b65ae1e1e9e52987

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 10 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

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

Sign in to the archive ↗

Verification & scope

A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:48:51.257879+00:00.

Case digest / 5dbd558fa17c92da3c3cac981dcaac98a110ee26cd6e4c625c95d0c62bf13ef5