FA-73701 / Rate limiter algorithms / Open access
Distributed limiter with leased quota chunks: returned lease not credited · case 01
Quota returned by draining nodes is lost for the rest of the window.
ROOT CAUSE
The returned lease is discarded without crediting the coordinator.
VERIFIED REPAIR
Add the node's unused lease back to remaining.
Unsuccessful approach: Crediting a full chunk regardless of what was left mints quota.
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':
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', 2, 'allow', 'allow', 'deny'], 0, [['b', 0], ['c', 0]]] | [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]] | Failed |
| 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', 4], 4, []] | [['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', 2, 2, 'allow', 'allow', 'allow', 0, 'deny', '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 / ac93afa07850119d2cd8e80075c4421c13462865c68797e9d9135f368abd5ef0
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 += L
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', 6, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 1]]] | [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]] | Failed |
| 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', 6], 6, []] | [['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', 5, 8, 'allow', 'allow', 'allow', 8, 'allow', 'allow', 11, 'allow', 'allow'], 5, [['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 / 70ceeee67a0f74f6d28fa04a6f167f87c25f50e365e684bdd916e3e861d5e90e
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.039310+00:00.
Case digest / 40c174b48671ff6275caf62a10d486d9bcd9fa532b9fef4b62f820277ed730fe