FA-73711 / Rate limiter algorithms / Open access
Distributed limiter with leased quota chunks: exhausted lease never refetched · case 01
A node that used up its first chunk denies everything for the rest of the window although quota remains.
ROOT CAUSE
A lease is fetched only for nodes with no lease entry, not for nodes whose lease is exhausted.
VERIFIED REPAIR
Fetch a new chunk whenever the node's lease is empty.
Unsuccessful approach: Refetching at one remaining unit overwrites and loses that unit.
Case contract
Input {quota, window_s, chunk, events [[t, node, "req"|"return"]]} with nondecreasing t. Each epoch window starts with the full global quota and voids all node leases. A node with an empty lease fetches min(chunk, remaining) from the coordinator; each request spends one leased unit or is denied when none is available. "return" credits the node's unused lease back and reports the new remaining. Return [results, remaining, sorted [node, lease]].
Why this case matters
Large-scale limiters hand out quota in chunks to avoid a coordinator round trip per request; lease accounting errors oversubscribe the global limit or strand quota.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
Q = x['quota']
W = x['window_s']
L = x['chunk']
win = None
remaining = 0
local = {}
out = []
for t, node, op in x['events']:
w = t // W
if w != win:
win, remaining, local = w, Q, {}
if op == 'return':
remaining += local.pop(node, 0)
out.append(remaining)
continue
if node not in local:
grant = min(L, remaining)
remaining -= grant
local[node] = grant
if local[node] > 0:
local[node] -= 1
out.append('allow')
else:
out.append('deny')
return [out, remaining, sorted([k, v] for k, v in local.items())]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['partial last chunk',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[3, 'c', 'req']],
'quota': 7,
'window_s': 60},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
0,
[['a', 2], ['b', 0], ['c', 0]]]],
['return credits leftover',
{'chunk': 4,
'events': [[0, 'a', 'req'],
[1, 'a', 'return'],
[2, 'b', 'req'],
[3, 'b', 'req'],
[5, 'c', 'req']],
'quota': 6,
'window_s': 60},
[['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
['window rollover voids leases',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[3, 'b', 'req'],
[11, 'a', 'req'],
[12, 'a', 'req'],
[14, 'a', 'req']],
'quota': 4,
'window_s': 10},
[['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
['exhausted lease refetches',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[2, 'a', 'return']],
'quota': 10,
'window_s': 100},
[['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
['global exhaustion',
{'chunk': 2,
'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [4, 'a', 'req']],
'quota': 3,
'window_s': 100},
[['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
['random nodes',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[5, 'a', 'req'],
[6, 'b', 'req'],
[10, 'a', 'return'],
[14, 'a', 'return'],
[20, 'b', 'req'],
[23, 'b', 'req'],
[24, 'b', 'req'],
[24, 'b', 'return'],
[25, 'a', 'req'],
[25, 'b', 'req'],
[31, 'b', 'return'],
[38, 'a', 'req'],
[38, 'b', 'req']],
'quota': 8,
'window_s': 30},
[['allow',
'allow',
'allow',
3,
3,
'allow',
'allow',
'allow',
2,
'allow',
'deny',
8,
'allow',
'allow'],
2,
[['a', 2], ['b', 2]]]]],
[['partial last chunk',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[4, 'c', 'req']],
'quota': 7,
'window_s': 60},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
0,
[['a', 2], ['b', 0], ['c', 0]]]],
['return credits leftover',
{'chunk': 4,
'events': [[0, 'a', 'req'],
[1, 'a', 'return'],
[2, 'b', 'req'],
[3, 'b', 'req'],
[6, 'c', 'req']],
'quota': 6,
'window_s': 60},
[['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
['window rollover voids leases',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[3, 'b', 'req'],
[11, 'a', 'req'],
[12, 'a', 'req'],
[15, 'a', 'req']],
'quota': 4,
'window_s': 10},
[['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
['exhausted lease refetches',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[3, 'a', 'return']],
'quota': 10,
'window_s': 100},
[['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
['global exhaustion',
{'chunk': 2,
'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [5, 'a', 'req']],
'quota': 3,
'window_s': 100},
[['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
['random nodes',
{'chunk': 3,
'events': [[1, 'a', 'req'],
[13, 'a', 'req'],
[15, 'b', 'req'],
[22, 'a', 'req'],
[25, 'a', 'req'],
[25, 'a', 'return'],
[26, 'b', 'req'],
[26, 'b', 'return'],
[29, 'b', 'req'],
[39, 'b', 'req'],
[44, 'a', 'req'],
[48, 'a', 'req'],
[48, 'a', 'return'],
[49, 'b', 'req']],
'quota': 8,
'window_s': 30},
[['allow',
'allow',
'allow',
'allow',
'allow',
1,
'allow',
2,
'allow',
'allow',
'allow',
'allow',
3,
'allow'],
3,
[['b', 1]]]]],
[['partial last chunk',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[5, 'c', 'req']],
'quota': 7,
'window_s': 60},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
0,
[['a', 2], ['b', 0], ['c', 0]]]],
['return credits leftover',
{'chunk': 4,
'events': [[0, 'a', 'req'],
[1, 'a', 'return'],
[2, 'b', 'req'],
[3, 'b', 'req'],
[7, 'c', 'req']],
'quota': 6,
'window_s': 60},
[['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
['window rollover voids leases',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[3, 'b', 'req'],
[11, 'a', 'req'],
[12, 'a', 'req'],
[16, 'a', 'req']],
'quota': 4,
'window_s': 10},
[['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
['exhausted lease refetches',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[4, 'a', 'return']],
'quota': 10,
'window_s': 100},
[['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
['global exhaustion',
{'chunk': 2,
'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [6, 'a', 'req']],
'quota': 3,
'window_s': 100},
[['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
['random nodes',
{'chunk': 3,
'events': [[0, 'a', 'return'],
[9, 'a', 'req'],
[9, 'a', 'return'],
[16, 'a', 'req'],
[22, 'a', 'req'],
[24, 'a', 'req'],
[32, 'b', 'req'],
[34, 'a', 'req'],
[35, 'b', 'return'],
[36, 'b', 'req'],
[40, 'a', 'req'],
[44, 'a', 'return'],
[45, 'b', 'req'],
[48, 'a', 'req']],
'quota': 8,
'window_s': 30},
[[8,
'allow',
7,
'allow',
'allow',
'allow',
'allow',
'allow',
4,
'allow',
'allow',
2,
'allow',
'allow'],
0,
[['a', 1], ['b', 1]]]]],
[['partial last chunk',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[6, 'c', 'req']],
'quota': 7,
'window_s': 60},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
0,
[['a', 2], ['b', 0], ['c', 0]]]],
['return credits leftover',
{'chunk': 4,
'events': [[0, 'a', 'req'],
[1, 'a', 'return'],
[2, 'b', 'req'],
[3, 'b', 'req'],
[8, 'c', 'req']],
'quota': 6,
'window_s': 60},
[['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
['window rollover voids leases',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[3, 'b', 'req'],
[11, 'a', 'req'],
[12, 'a', 'req'],
[17, 'a', 'req']],
'quota': 4,
'window_s': 10},
[['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
['exhausted lease refetches',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[5, 'a', 'return']],
'quota': 10,
'window_s': 100},
[['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
['global exhaustion',
{'chunk': 2,
'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [7, 'a', 'req']],
'quota': 3,
'window_s': 100},
[['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
['random nodes',
{'chunk': 3,
'events': [[4, 'b', 'req'],
[8, 'a', 'req'],
[17, 'b', 'req'],
[20, 'b', 'req'],
[26, 'a', 'return'],
[28, 'b', 'req'],
[32, 'b', 'req'],
[36, 'a', 'req'],
[38, 'b', 'req'],
[40, 'a', 'req'],
[41, 'a', 'req'],
[42, 'a', 'req'],
[42, 'a', 'return'],
[43, 'a', 'req']],
'quota': 8,
'window_s': 30},
[['allow',
'allow',
'allow',
'allow',
4,
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
1,
'allow'],
0,
[['a', 0], ['b', 1]]]]],
[['partial last chunk',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[7, 'c', 'req']],
'quota': 7,
'window_s': 60},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
0,
[['a', 2], ['b', 0], ['c', 0]]]],
['return credits leftover',
{'chunk': 4,
'events': [[0, 'a', 'req'],
[1, 'a', 'return'],
[2, 'b', 'req'],
[3, 'b', 'req'],
[9, 'c', 'req']],
'quota': 6,
'window_s': 60},
[['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
['window rollover voids leases',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[3, 'b', 'req'],
[11, 'a', 'req'],
[12, 'a', 'req'],
[18, 'a', 'req']],
'quota': 4,
'window_s': 10},
[['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
['exhausted lease refetches',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[6, 'a', 'return']],
'quota': 10,
'window_s': 100},
[['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
['global exhaustion',
{'chunk': 2,
'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [8, 'a', 'req']],
'quota': 3,
'window_s': 100},
[['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
['random nodes',
{'chunk': 3,
'events': [[8, 'b', 'return'],
[10, 'b', 'req'],
[11, 'a', 'req'],
[11, 'a', 'return'],
[14, 'b', 'req'],
[25, 'a', 'req'],
[26, 'b', 'req'],
[35, 'a', 'req'],
[35, 'a', 'return'],
[39, 'a', 'req'],
[40, 'a', 'req'],
[43, 'b', 'req'],
[44, 'b', 'return'],
[47, 'a', 'return']],
'quota': 8,
'window_s': 30},
[[8,
'allow',
'allow',
4,
'allow',
'allow',
'allow',
'allow',
7,
'allow',
'allow',
'allow',
3,
4],
4,
[]]]]]
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| partial last chunk | [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'allow', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]] | [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'], 0, [['a', 2], ['b', 0], ['c', 0]]] | Failed |
| return credits leftover | [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]] | [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]] | Passed |
| window rollover voids leases | [['allow', 'allow', 'allow', 'allow', 'deny'], 2, [['a', 0]]] | [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]] | Failed |
| exhausted lease refetches | [['allow', 'allow', 'deny', 'deny', 'deny', 8], 8, []] | [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []] | Failed |
| global exhaustion | [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]] | [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]] | Passed |
| random nodes | [['allow', 'allow', 'allow', 3, 3, 'allow', 'allow', 'deny', 3, 'allow', 'deny', 8, 'allow', 'allow'], 2, [['a', 2], ['b', 2]]] | [['allow', 'allow', 'allow', 3, 3, 'allow', 'allow', 'allow', 2, 'allow', 'deny', 8, 'allow', 'allow'], 2, [['a', 2], ['b', 2]]] | Failed |
SHA-256 / cdcfa2b23d871394fbbfe3eab422956d1a74e5152af9f42c5cad20f881119a58
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
Q = x['quota']
W = x['window_s']
L = x['chunk']
win = None
remaining = 0
local = {}
out = []
for t, node, op in x['events']:
w = t // W
if w != win:
win, remaining, local = w, Q, {}
if op == 'return':
remaining += local.pop(node, 0)
out.append(remaining)
continue
if local.get(node, 0) <= 1:
grant = min(L, remaining)
remaining -= grant
local[node] = grant
if local[node] > 0:
local[node] -= 1
out.append('allow')
else:
out.append('deny')
return [out, remaining, sorted([k, v] for k, v in local.items())]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['partial last chunk',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[3, 'c', 'req']],
'quota': 7,
'window_s': 60},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
0,
[['a', 2], ['b', 0], ['c', 0]]]],
['return credits leftover',
{'chunk': 4,
'events': [[0, 'a', 'req'],
[1, 'a', 'return'],
[2, 'b', 'req'],
[3, 'b', 'req'],
[5, 'c', 'req']],
'quota': 6,
'window_s': 60},
[['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
['window rollover voids leases',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[3, 'b', 'req'],
[11, 'a', 'req'],
[12, 'a', 'req'],
[14, 'a', 'req']],
'quota': 4,
'window_s': 10},
[['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
['exhausted lease refetches',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[2, 'a', 'return']],
'quota': 10,
'window_s': 100},
[['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
['global exhaustion',
{'chunk': 2,
'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [4, 'a', 'req']],
'quota': 3,
'window_s': 100},
[['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
['random nodes',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[5, 'a', 'req'],
[6, 'b', 'req'],
[10, 'a', 'return'],
[14, 'a', 'return'],
[20, 'b', 'req'],
[23, 'b', 'req'],
[24, 'b', 'req'],
[24, 'b', 'return'],
[25, 'a', 'req'],
[25, 'b', 'req'],
[31, 'b', 'return'],
[38, 'a', 'req'],
[38, 'b', 'req']],
'quota': 8,
'window_s': 30},
[['allow',
'allow',
'allow',
3,
3,
'allow',
'allow',
'allow',
2,
'allow',
'deny',
8,
'allow',
'allow'],
2,
[['a', 2], ['b', 2]]]]],
[['partial last chunk',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[4, 'c', 'req']],
'quota': 7,
'window_s': 60},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
0,
[['a', 2], ['b', 0], ['c', 0]]]],
['return credits leftover',
{'chunk': 4,
'events': [[0, 'a', 'req'],
[1, 'a', 'return'],
[2, 'b', 'req'],
[3, 'b', 'req'],
[6, 'c', 'req']],
'quota': 6,
'window_s': 60},
[['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
['window rollover voids leases',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[3, 'b', 'req'],
[11, 'a', 'req'],
[12, 'a', 'req'],
[15, 'a', 'req']],
'quota': 4,
'window_s': 10},
[['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
['exhausted lease refetches',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[3, 'a', 'return']],
'quota': 10,
'window_s': 100},
[['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
['global exhaustion',
{'chunk': 2,
'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [5, 'a', 'req']],
'quota': 3,
'window_s': 100},
[['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
['random nodes',
{'chunk': 3,
'events': [[1, 'a', 'req'],
[13, 'a', 'req'],
[15, 'b', 'req'],
[22, 'a', 'req'],
[25, 'a', 'req'],
[25, 'a', 'return'],
[26, 'b', 'req'],
[26, 'b', 'return'],
[29, 'b', 'req'],
[39, 'b', 'req'],
[44, 'a', 'req'],
[48, 'a', 'req'],
[48, 'a', 'return'],
[49, 'b', 'req']],
'quota': 8,
'window_s': 30},
[['allow',
'allow',
'allow',
'allow',
'allow',
1,
'allow',
2,
'allow',
'allow',
'allow',
'allow',
3,
'allow'],
3,
[['b', 1]]]]],
[['partial last chunk',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[5, 'c', 'req']],
'quota': 7,
'window_s': 60},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
0,
[['a', 2], ['b', 0], ['c', 0]]]],
['return credits leftover',
{'chunk': 4,
'events': [[0, 'a', 'req'],
[1, 'a', 'return'],
[2, 'b', 'req'],
[3, 'b', 'req'],
[7, 'c', 'req']],
'quota': 6,
'window_s': 60},
[['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
['window rollover voids leases',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[3, 'b', 'req'],
[11, 'a', 'req'],
[12, 'a', 'req'],
[16, 'a', 'req']],
'quota': 4,
'window_s': 10},
[['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
['exhausted lease refetches',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[4, 'a', 'return']],
'quota': 10,
'window_s': 100},
[['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
['global exhaustion',
{'chunk': 2,
'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [6, 'a', 'req']],
'quota': 3,
'window_s': 100},
[['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
['random nodes',
{'chunk': 3,
'events': [[0, 'a', 'return'],
[9, 'a', 'req'],
[9, 'a', 'return'],
[16, 'a', 'req'],
[22, 'a', 'req'],
[24, 'a', 'req'],
[32, 'b', 'req'],
[34, 'a', 'req'],
[35, 'b', 'return'],
[36, 'b', 'req'],
[40, 'a', 'req'],
[44, 'a', 'return'],
[45, 'b', 'req'],
[48, 'a', 'req']],
'quota': 8,
'window_s': 30},
[[8,
'allow',
7,
'allow',
'allow',
'allow',
'allow',
'allow',
4,
'allow',
'allow',
2,
'allow',
'allow'],
0,
[['a', 1], ['b', 1]]]]],
[['partial last chunk',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[6, 'c', 'req']],
'quota': 7,
'window_s': 60},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
0,
[['a', 2], ['b', 0], ['c', 0]]]],
['return credits leftover',
{'chunk': 4,
'events': [[0, 'a', 'req'],
[1, 'a', 'return'],
[2, 'b', 'req'],
[3, 'b', 'req'],
[8, 'c', 'req']],
'quota': 6,
'window_s': 60},
[['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
['window rollover voids leases',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[3, 'b', 'req'],
[11, 'a', 'req'],
[12, 'a', 'req'],
[17, 'a', 'req']],
'quota': 4,
'window_s': 10},
[['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
['exhausted lease refetches',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[5, 'a', 'return']],
'quota': 10,
'window_s': 100},
[['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
['global exhaustion',
{'chunk': 2,
'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [7, 'a', 'req']],
'quota': 3,
'window_s': 100},
[['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
['random nodes',
{'chunk': 3,
'events': [[4, 'b', 'req'],
[8, 'a', 'req'],
[17, 'b', 'req'],
[20, 'b', 'req'],
[26, 'a', 'return'],
[28, 'b', 'req'],
[32, 'b', 'req'],
[36, 'a', 'req'],
[38, 'b', 'req'],
[40, 'a', 'req'],
[41, 'a', 'req'],
[42, 'a', 'req'],
[42, 'a', 'return'],
[43, 'a', 'req']],
'quota': 8,
'window_s': 30},
[['allow',
'allow',
'allow',
'allow',
4,
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
1,
'allow'],
0,
[['a', 0], ['b', 1]]]]],
[['partial last chunk',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[7, 'c', 'req']],
'quota': 7,
'window_s': 60},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
0,
[['a', 2], ['b', 0], ['c', 0]]]],
['return credits leftover',
{'chunk': 4,
'events': [[0, 'a', 'req'],
[1, 'a', 'return'],
[2, 'b', 'req'],
[3, 'b', 'req'],
[9, 'c', 'req']],
'quota': 6,
'window_s': 60},
[['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
['window rollover voids leases',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[3, 'b', 'req'],
[11, 'a', 'req'],
[12, 'a', 'req'],
[18, 'a', 'req']],
'quota': 4,
'window_s': 10},
[['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
['exhausted lease refetches',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[6, 'a', 'return']],
'quota': 10,
'window_s': 100},
[['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
['global exhaustion',
{'chunk': 2,
'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [8, 'a', 'req']],
'quota': 3,
'window_s': 100},
[['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
['random nodes',
{'chunk': 3,
'events': [[8, 'b', 'return'],
[10, 'b', 'req'],
[11, 'a', 'req'],
[11, 'a', 'return'],
[14, 'b', 'req'],
[25, 'a', 'req'],
[26, 'b', 'req'],
[35, 'a', 'req'],
[35, 'a', 'return'],
[39, 'a', 'req'],
[40, 'a', 'req'],
[43, 'b', 'req'],
[44, 'b', 'return'],
[47, 'a', 'return']],
'quota': 8,
'window_s': 30},
[[8,
'allow',
'allow',
4,
'allow',
'allow',
'allow',
'allow',
7,
'allow',
'allow',
'allow',
3,
4],
4,
[]]]]]
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| partial last chunk | [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'], 0, [['a', 1], ['b', 0], ['c', 0]]] | [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'], 0, [['a', 2], ['b', 0], ['c', 0]]] | Failed |
| return credits leftover | [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]] | [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]] | Passed |
| window rollover voids leases | [['allow', 'allow', 'allow', 'allow', 'deny'], 0, [['a', 0]]] | [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]] | Failed |
| exhausted lease refetches | [['allow', 'allow', 'allow', 'allow', 'allow', 1], 1, []] | [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []] | Failed |
| global exhaustion | [['allow', 'allow', 'deny', 'deny', 'deny'], 0, [['a', 0], ['b', 0], ['c', 0]]] | [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]] | Failed |
| random nodes | [['allow', 'allow', 'allow', 3, 3, 'allow', 'allow', 'allow', 1, 'allow', 'deny', 8, 'allow', 'allow'], 2, [['a', 2], ['b', 2]]] | [['allow', 'allow', 'allow', 3, 3, 'allow', 'allow', 'allow', 2, 'allow', 'deny', 8, 'allow', 'allow'], 2, [['a', 2], ['b', 2]]] | Failed |
SHA-256 / 4b37e2be3d1beb8eb503369b07409e2793c8f3aa9a66e3280ce29e3cea993143
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
Q = x['quota']
W = x['window_s']
L = x['chunk']
win = None
remaining = 0
local = {}
out = []
for t, node, op in x['events']:
w = t // W
if w != win:
win, remaining, local = w, Q, {}
if op == 'return':
remaining += local.pop(node, 0)
out.append(remaining)
continue
if local.get(node, 0) == 0:
grant = min(L, remaining)
remaining -= grant
local[node] = grant
if local[node] > 0:
local[node] -= 1
out.append('allow')
else:
out.append('deny')
return [out, remaining, sorted([k, v] for k, v in local.items())]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['partial last chunk',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[3, 'c', 'req']],
'quota': 7,
'window_s': 60},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
0,
[['a', 2], ['b', 0], ['c', 0]]]],
['return credits leftover',
{'chunk': 4,
'events': [[0, 'a', 'req'],
[1, 'a', 'return'],
[2, 'b', 'req'],
[3, 'b', 'req'],
[5, 'c', 'req']],
'quota': 6,
'window_s': 60},
[['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
['window rollover voids leases',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[3, 'b', 'req'],
[11, 'a', 'req'],
[12, 'a', 'req'],
[14, 'a', 'req']],
'quota': 4,
'window_s': 10},
[['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
['exhausted lease refetches',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[2, 'a', 'return']],
'quota': 10,
'window_s': 100},
[['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
['global exhaustion',
{'chunk': 2,
'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [4, 'a', 'req']],
'quota': 3,
'window_s': 100},
[['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
['random nodes',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[5, 'a', 'req'],
[6, 'b', 'req'],
[10, 'a', 'return'],
[14, 'a', 'return'],
[20, 'b', 'req'],
[23, 'b', 'req'],
[24, 'b', 'req'],
[24, 'b', 'return'],
[25, 'a', 'req'],
[25, 'b', 'req'],
[31, 'b', 'return'],
[38, 'a', 'req'],
[38, 'b', 'req']],
'quota': 8,
'window_s': 30},
[['allow',
'allow',
'allow',
3,
3,
'allow',
'allow',
'allow',
2,
'allow',
'deny',
8,
'allow',
'allow'],
2,
[['a', 2], ['b', 2]]]]],
[['partial last chunk',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[4, 'c', 'req']],
'quota': 7,
'window_s': 60},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
0,
[['a', 2], ['b', 0], ['c', 0]]]],
['return credits leftover',
{'chunk': 4,
'events': [[0, 'a', 'req'],
[1, 'a', 'return'],
[2, 'b', 'req'],
[3, 'b', 'req'],
[6, 'c', 'req']],
'quota': 6,
'window_s': 60},
[['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
['window rollover voids leases',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[3, 'b', 'req'],
[11, 'a', 'req'],
[12, 'a', 'req'],
[15, 'a', 'req']],
'quota': 4,
'window_s': 10},
[['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
['exhausted lease refetches',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[3, 'a', 'return']],
'quota': 10,
'window_s': 100},
[['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
['global exhaustion',
{'chunk': 2,
'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [5, 'a', 'req']],
'quota': 3,
'window_s': 100},
[['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
['random nodes',
{'chunk': 3,
'events': [[1, 'a', 'req'],
[13, 'a', 'req'],
[15, 'b', 'req'],
[22, 'a', 'req'],
[25, 'a', 'req'],
[25, 'a', 'return'],
[26, 'b', 'req'],
[26, 'b', 'return'],
[29, 'b', 'req'],
[39, 'b', 'req'],
[44, 'a', 'req'],
[48, 'a', 'req'],
[48, 'a', 'return'],
[49, 'b', 'req']],
'quota': 8,
'window_s': 30},
[['allow',
'allow',
'allow',
'allow',
'allow',
1,
'allow',
2,
'allow',
'allow',
'allow',
'allow',
3,
'allow'],
3,
[['b', 1]]]]],
[['partial last chunk',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[5, 'c', 'req']],
'quota': 7,
'window_s': 60},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
0,
[['a', 2], ['b', 0], ['c', 0]]]],
['return credits leftover',
{'chunk': 4,
'events': [[0, 'a', 'req'],
[1, 'a', 'return'],
[2, 'b', 'req'],
[3, 'b', 'req'],
[7, 'c', 'req']],
'quota': 6,
'window_s': 60},
[['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
['window rollover voids leases',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[3, 'b', 'req'],
[11, 'a', 'req'],
[12, 'a', 'req'],
[16, 'a', 'req']],
'quota': 4,
'window_s': 10},
[['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
['exhausted lease refetches',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[4, 'a', 'return']],
'quota': 10,
'window_s': 100},
[['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
['global exhaustion',
{'chunk': 2,
'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [6, 'a', 'req']],
'quota': 3,
'window_s': 100},
[['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
['random nodes',
{'chunk': 3,
'events': [[0, 'a', 'return'],
[9, 'a', 'req'],
[9, 'a', 'return'],
[16, 'a', 'req'],
[22, 'a', 'req'],
[24, 'a', 'req'],
[32, 'b', 'req'],
[34, 'a', 'req'],
[35, 'b', 'return'],
[36, 'b', 'req'],
[40, 'a', 'req'],
[44, 'a', 'return'],
[45, 'b', 'req'],
[48, 'a', 'req']],
'quota': 8,
'window_s': 30},
[[8,
'allow',
7,
'allow',
'allow',
'allow',
'allow',
'allow',
4,
'allow',
'allow',
2,
'allow',
'allow'],
0,
[['a', 1], ['b', 1]]]]],
[['partial last chunk',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[6, 'c', 'req']],
'quota': 7,
'window_s': 60},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
0,
[['a', 2], ['b', 0], ['c', 0]]]],
['return credits leftover',
{'chunk': 4,
'events': [[0, 'a', 'req'],
[1, 'a', 'return'],
[2, 'b', 'req'],
[3, 'b', 'req'],
[8, 'c', 'req']],
'quota': 6,
'window_s': 60},
[['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
['window rollover voids leases',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[3, 'b', 'req'],
[11, 'a', 'req'],
[12, 'a', 'req'],
[17, 'a', 'req']],
'quota': 4,
'window_s': 10},
[['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
['exhausted lease refetches',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[5, 'a', 'return']],
'quota': 10,
'window_s': 100},
[['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
['global exhaustion',
{'chunk': 2,
'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [7, 'a', 'req']],
'quota': 3,
'window_s': 100},
[['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
['random nodes',
{'chunk': 3,
'events': [[4, 'b', 'req'],
[8, 'a', 'req'],
[17, 'b', 'req'],
[20, 'b', 'req'],
[26, 'a', 'return'],
[28, 'b', 'req'],
[32, 'b', 'req'],
[36, 'a', 'req'],
[38, 'b', 'req'],
[40, 'a', 'req'],
[41, 'a', 'req'],
[42, 'a', 'req'],
[42, 'a', 'return'],
[43, 'a', 'req']],
'quota': 8,
'window_s': 30},
[['allow',
'allow',
'allow',
'allow',
4,
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
1,
'allow'],
0,
[['a', 0], ['b', 1]]]]],
[['partial last chunk',
{'chunk': 3,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[1, 'b', 'req'],
[7, 'c', 'req']],
'quota': 7,
'window_s': 60},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],
0,
[['a', 2], ['b', 0], ['c', 0]]]],
['return credits leftover',
{'chunk': 4,
'events': [[0, 'a', 'req'],
[1, 'a', 'return'],
[2, 'b', 'req'],
[3, 'b', 'req'],
[9, 'c', 'req']],
'quota': 6,
'window_s': 60},
[['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],
['window rollover voids leases',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[3, 'b', 'req'],
[11, 'a', 'req'],
[12, 'a', 'req'],
[18, 'a', 'req']],
'quota': 4,
'window_s': 10},
[['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],
['exhausted lease refetches',
{'chunk': 2,
'events': [[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[0, 'a', 'req'],
[6, 'a', 'return']],
'quota': 10,
'window_s': 100},
[['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],
['global exhaustion',
{'chunk': 2,
'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [8, 'a', 'req']],
'quota': 3,
'window_s': 100},
[['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],
['random nodes',
{'chunk': 3,
'events': [[8, 'b', 'return'],
[10, 'b', 'req'],
[11, 'a', 'req'],
[11, 'a', 'return'],
[14, 'b', 'req'],
[25, 'a', 'req'],
[26, 'b', 'req'],
[35, 'a', 'req'],
[35, 'a', 'return'],
[39, 'a', 'req'],
[40, 'a', 'req'],
[43, 'b', 'req'],
[44, 'b', 'return'],
[47, 'a', 'return']],
'quota': 8,
'window_s': 30},
[[8,
'allow',
'allow',
4,
'allow',
'allow',
'allow',
'allow',
7,
'allow',
'allow',
'allow',
3,
4],
4,
[]]]]]
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 fixture | Actual | Expected | Outcome |
|---|---|---|---|
| partial last chunk | [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'], 0, [['a', 2], ['b', 0], ['c', 0]]] | [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'], 0, [['a', 2], ['b', 0], ['c', 0]]] | Passed |
| return credits leftover | [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]] | [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]] | Passed |
| window rollover voids leases | [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]] | [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]] | Passed |
| exhausted lease refetches | [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []] | [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []] | Passed |
| global exhaustion | [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]] | [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]] | Passed |
| random nodes | [['allow', 'allow', 'allow', 3, 3, 'allow', 'allow', 'allow', 2, 'allow', 'deny', 8, 'allow', 'allow'], 2, [['a', 2], ['b', 2]]] | [['allow', 'allow', 'allow', 3, 3, 'allow', 'allow', 'allow', 2, 'allow', 'deny', 8, 'allow', 'allow'], 2, [['a', 2], ['b', 2]]] | Passed |
SHA-256 / 7a242cde12e85329d71b51a99c4258b4a9d9e81ab4d883a0cec47012b8ba9ecd
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:50.080661+00:00.
Case digest / eda7f670b9e361d9e1a51de1ea8631df70970d8ccb87c710ca99301a01319abd