FA-73546 / Rate limiter algorithms / Open access
Hierarchical tenant and global token buckets: global bucket capped at tenant capacity · case 01
The shared bucket can never hold more than one tenant's capacity, throttling the fleet.
ROOT CAUSE
Global refill is clamped with the tenant capacity.
VERIFIED REPAIR
Clamp the global bucket with the global capacity.
Unsuccessful approach: Removing the clamp lets the global bucket bank unlimited tokens.
Case contract
Input {tenant_cap, tenant_rate, global_cap, global_rate, requests [[t_s, tenant, cost]]} with nondecreasing whole-second t. Each tenant bucket starts full at its first request and refills from its own last-seen time; the global bucket starts full at t=0. Both refill lazily and are capped by their own capacity. A request needs cost tokens in both; the tenant bucket is checked first ("deny-tenant"), then the global ("deny-global"); both are charged only on admission. Return [decisions, global tokens, sorted [tenant, tokens]].
Why this case matters
Multi-tenant APIs enforce per-tenant and shared limits together; charging or refilling the wrong level leaks capacity between tenants.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
tc, tr = x['tenant_cap'], x['tenant_rate']
gc, gr = x['global_cap'], x['global_rate']
tenants = {}
g = [gc, 0]
out = []
for t, ten, cost in x['requests']:
st = tenants.setdefault(ten, [tc, t])
st[0] = min(tc, st[0] + (t - st[1]) * tr)
st[1] = t
g[0] = min(tc, g[0] + (t - g[1]) * gr)
g[1] = t
if st[0] < cost:
out.append('deny-tenant')
elif g[0] < cost:
out.append('deny-global')
else:
st[0] -= cost
g[0] -= cost
out.append('allow')
return [out, g[0], sorted([k, v[0]] for k, v in tenants.items())]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['global exhaustion',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [2, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 1, [['a', 1], ['b', 1], ['c', 2]]]],
['partial global remains usable',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [1, 'd', 2]],
'tenant_cap': 5,
'tenant_rate': 1},
[['allow', 'deny-global', 'allow', 'deny-global'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 5]]]],
['both short reports tenant',
{'global_cap': 2,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [1, 'b', 2]],
'tenant_cap': 2,
'tenant_rate': 1},
[['allow', 'deny-tenant', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]]],
['tenant clock independent',
{'global_cap': 20,
'global_rate': 5,
'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [6, 'a', 2]],
'tenant_cap': 4,
'tenant_rate': 1},
[['allow', 'allow', 'allow', 'allow'], 18, [['a', 1], ['b', 3]]]],
['new tenant starts full',
{'global_cap': 10,
'global_rate': 2,
'requests': [[5, 'x', 3], [5, 'y', 2], [7, 'z', 3]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'allow'], 6, [['x', 0], ['y', 1], ['z', 0]]]],
['global capacity bound',
{'global_cap': 6,
'global_rate': 3,
'requests': [[0, 'a', 2],
[0, 'b', 2],
[0, 'c', 2],
[10, 'a', 2],
[10, 'b', 2],
[10, 'c', 2],
[11, 'd', 1]],
'tenant_cap': 2,
'tenant_rate': 2},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
2,
[['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
['random tenants',
{'global_cap': 5,
'global_rate': 2,
'requests': [[0, 'a', 2],
[0, 'a', 3],
[1, 'b', 3],
[2, 'a', 1],
[3, 'c', 1],
[4, 'c', 3],
[5, 'a', 2],
[5, 'b', 1],
[6, 'a', 1],
[7, 'b', 2]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow',
'deny-tenant',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow'],
2,
[['a', 1], ['b', 1], ['c', 0]]]]],
[['global exhaustion',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [3, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 2, [['a', 1], ['b', 1], ['c', 2]]]],
['partial global remains usable',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [2, 'd', 2]],
'tenant_cap': 5,
'tenant_rate': 1},
[['allow', 'deny-global', 'allow', 'allow'], 0, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
['both short reports tenant',
{'global_cap': 2,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [2, 'b', 2]],
'tenant_cap': 2,
'tenant_rate': 1},
[['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
['tenant clock independent',
{'global_cap': 20,
'global_rate': 5,
'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [7, 'a', 2]],
'tenant_cap': 4,
'tenant_rate': 1},
[['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
['new tenant starts full',
{'global_cap': 10,
'global_rate': 2,
'requests': [[5, 'x', 3], [5, 'y', 2], [8, 'z', 3]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
['global capacity bound',
{'global_cap': 6,
'global_rate': 3,
'requests': [[0, 'a', 2],
[0, 'b', 2],
[0, 'c', 2],
[10, 'a', 2],
[10, 'b', 2],
[10, 'c', 2],
[12, 'd', 1]],
'tenant_cap': 2,
'tenant_rate': 2},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
5,
[['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
['random tenants',
{'global_cap': 5,
'global_rate': 2,
'requests': [[0, 'a', 2],
[0, 'c', 2],
[0, 'c', 2],
[2, 'b', 3],
[3, 'a', 2],
[3, 'c', 1],
[3, 'c', 1],
[4, 'a', 2],
[8, 'b', 2],
[8, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow',
'allow',
'deny-tenant',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow'],
2,
[['a', 0], ['b', 1], ['c', 2]]]]],
[['global exhaustion',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [4, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],
['partial global remains usable',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [3, 'd', 2]],
'tenant_cap': 5,
'tenant_rate': 1},
[['allow', 'deny-global', 'allow', 'allow'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
['both short reports tenant',
{'global_cap': 2,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [3, 'b', 2]],
'tenant_cap': 2,
'tenant_rate': 1},
[['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
['tenant clock independent',
{'global_cap': 20,
'global_rate': 5,
'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [8, 'a', 2]],
'tenant_cap': 4,
'tenant_rate': 1},
[['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
['new tenant starts full',
{'global_cap': 10,
'global_rate': 2,
'requests': [[5, 'x', 3], [5, 'y', 2], [9, 'z', 3]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
['global capacity bound',
{'global_cap': 6,
'global_rate': 3,
'requests': [[0, 'a', 2],
[0, 'b', 2],
[0, 'c', 2],
[10, 'a', 2],
[10, 'b', 2],
[10, 'c', 2],
[13, 'd', 1]],
'tenant_cap': 2,
'tenant_rate': 2},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
5,
[['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
['random tenants',
{'global_cap': 5,
'global_rate': 2,
'requests': [[0, 'a', 2],
[1, 'c', 2],
[2, 'a', 1],
[2, 'a', 2],
[2, 'b', 1],
[3, 'c', 2],
[3, 'c', 3],
[4, 'a', 3],
[7, 'a', 1],
[8, 'b', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'deny-tenant',
'deny-tenant',
'allow',
'allow'],
4,
[['a', 2], ['b', 2], ['c', 1]]]]],
[['global exhaustion',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [5, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],
['partial global remains usable',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [4, 'd', 2]],
'tenant_cap': 5,
'tenant_rate': 1},
[['allow', 'deny-global', 'allow', 'allow'], 2, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
['both short reports tenant',
{'global_cap': 2,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [4, 'b', 2]],
'tenant_cap': 2,
'tenant_rate': 1},
[['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
['tenant clock independent',
{'global_cap': 20,
'global_rate': 5,
'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [9, 'a', 2]],
'tenant_cap': 4,
'tenant_rate': 1},
[['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
['new tenant starts full',
{'global_cap': 10,
'global_rate': 2,
'requests': [[5, 'x', 3], [5, 'y', 2], [10, 'z', 3]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
['global capacity bound',
{'global_cap': 6,
'global_rate': 3,
'requests': [[0, 'a', 2],
[0, 'b', 2],
[0, 'c', 2],
[10, 'a', 2],
[10, 'b', 2],
[10, 'c', 2],
[14, 'd', 1]],
'tenant_cap': 2,
'tenant_rate': 2},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
5,
[['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
['random tenants',
{'global_cap': 5,
'global_rate': 2,
'requests': [[0, 'a', 3],
[1, 'a', 3],
[1, 'b', 3],
[1, 'c', 2],
[2, 'c', 2],
[3, 'a', 2],
[5, 'b', 2],
[6, 'b', 3],
[7, 'c', 1],
[8, 'a', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow',
'deny-tenant',
'allow',
'deny-global',
'allow',
'allow',
'allow',
'deny-tenant',
'allow',
'allow'],
4,
[['a', 2], ['b', 2], ['c', 2]]]]],
[['global exhaustion',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [6, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],
['partial global remains usable',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [5, 'd', 2]],
'tenant_cap': 5,
'tenant_rate': 1},
[['allow', 'deny-global', 'allow', 'allow'], 2, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
['both short reports tenant',
{'global_cap': 2,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [5, 'b', 2]],
'tenant_cap': 2,
'tenant_rate': 1},
[['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
['tenant clock independent',
{'global_cap': 20,
'global_rate': 5,
'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [10, 'a', 2]],
'tenant_cap': 4,
'tenant_rate': 1},
[['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
['new tenant starts full',
{'global_cap': 10,
'global_rate': 2,
'requests': [[5, 'x', 3], [5, 'y', 2], [11, 'z', 3]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
['global capacity bound',
{'global_cap': 6,
'global_rate': 3,
'requests': [[0, 'a', 2],
[0, 'b', 2],
[0, 'c', 2],
[10, 'a', 2],
[10, 'b', 2],
[10, 'c', 2],
[15, 'd', 1]],
'tenant_cap': 2,
'tenant_rate': 2},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
5,
[['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
['random tenants',
{'global_cap': 5,
'global_rate': 2,
'requests': [[0, 'c', 3],
[3, 'c', 1],
[3, 'c', 2],
[4, 'a', 1],
[7, 'a', 2],
[7, 'b', 1],
[7, 'b', 1],
[7, 'b', 2],
[7, 'c', 1],
[7, 'c', 2]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'deny-tenant',
'allow',
'deny-global'],
0,
[['a', 1], ['b', 1], ['c', 2]]]]]]
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 |
|---|---|---|---|
| global exhaustion | [['allow', 'deny-global', 'deny-global', 'allow', 'allow'], 1, [['a', 0], ['b', 3], ['c', 2]]] | [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 1, [['a', 1], ['b', 1], ['c', 2]]] | Failed |
| partial global remains usable | [['allow', 'deny-global', 'allow', 'deny-global'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 5]]] | [['allow', 'deny-global', 'allow', 'deny-global'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 5]]] | Passed |
| both short reports tenant | [['allow', 'deny-tenant', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]] | [['allow', 'deny-tenant', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]] | Passed |
| tenant clock independent | [['allow', 'allow', 'allow', 'allow'], 2, [['a', 1], ['b', 3]]] | [['allow', 'allow', 'allow', 'allow'], 18, [['a', 1], ['b', 3]]] | Failed |
| new tenant starts full | [['allow', 'deny-global', 'allow'], 0, [['x', 0], ['y', 3], ['z', 0]]] | [['allow', 'allow', 'allow'], 6, [['x', 0], ['y', 1], ['z', 0]]] | Failed |
| global capacity bound | [['allow', 'deny-global', 'deny-global', 'allow', 'deny-global', 'deny-global', 'allow'], 1, [['a', 0], ['b', 2], ['c', 2], ['d', 1]]] | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'], 2, [['a', 0], ['b', 0], ['c', 0], ['d', 1]]] | Failed |
| random tenants | [['allow', 'deny-tenant', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny-global', 'allow', 'allow'], 1, [['a', 1], ['b', 1], ['c', 0]]] | [['allow', 'deny-tenant', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'], 2, [['a', 1], ['b', 1], ['c', 0]]] | Failed |
SHA-256 / 18e3db0d4a2a692e2d2d08b165d7cfbc4faf8338f4d4cf27f0821e6453e30939
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
tc, tr = x['tenant_cap'], x['tenant_rate']
gc, gr = x['global_cap'], x['global_rate']
tenants = {}
g = [gc, 0]
out = []
for t, ten, cost in x['requests']:
st = tenants.setdefault(ten, [tc, t])
st[0] = min(tc, st[0] + (t - st[1]) * tr)
st[1] = t
g[0] = g[0] + (t - g[1]) * gr
g[1] = t
if st[0] < cost:
out.append('deny-tenant')
elif g[0] < cost:
out.append('deny-global')
else:
st[0] -= cost
g[0] -= cost
out.append('allow')
return [out, g[0], sorted([k, v[0]] for k, v in tenants.items())]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['global exhaustion',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [2, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 1, [['a', 1], ['b', 1], ['c', 2]]]],
['partial global remains usable',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [1, 'd', 2]],
'tenant_cap': 5,
'tenant_rate': 1},
[['allow', 'deny-global', 'allow', 'deny-global'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 5]]]],
['both short reports tenant',
{'global_cap': 2,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [1, 'b', 2]],
'tenant_cap': 2,
'tenant_rate': 1},
[['allow', 'deny-tenant', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]]],
['tenant clock independent',
{'global_cap': 20,
'global_rate': 5,
'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [6, 'a', 2]],
'tenant_cap': 4,
'tenant_rate': 1},
[['allow', 'allow', 'allow', 'allow'], 18, [['a', 1], ['b', 3]]]],
['new tenant starts full',
{'global_cap': 10,
'global_rate': 2,
'requests': [[5, 'x', 3], [5, 'y', 2], [7, 'z', 3]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'allow'], 6, [['x', 0], ['y', 1], ['z', 0]]]],
['global capacity bound',
{'global_cap': 6,
'global_rate': 3,
'requests': [[0, 'a', 2],
[0, 'b', 2],
[0, 'c', 2],
[10, 'a', 2],
[10, 'b', 2],
[10, 'c', 2],
[11, 'd', 1]],
'tenant_cap': 2,
'tenant_rate': 2},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
2,
[['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
['random tenants',
{'global_cap': 5,
'global_rate': 2,
'requests': [[0, 'a', 2],
[0, 'a', 3],
[1, 'b', 3],
[2, 'a', 1],
[3, 'c', 1],
[4, 'c', 3],
[5, 'a', 2],
[5, 'b', 1],
[6, 'a', 1],
[7, 'b', 2]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow',
'deny-tenant',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow'],
2,
[['a', 1], ['b', 1], ['c', 0]]]]],
[['global exhaustion',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [3, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 2, [['a', 1], ['b', 1], ['c', 2]]]],
['partial global remains usable',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [2, 'd', 2]],
'tenant_cap': 5,
'tenant_rate': 1},
[['allow', 'deny-global', 'allow', 'allow'], 0, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
['both short reports tenant',
{'global_cap': 2,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [2, 'b', 2]],
'tenant_cap': 2,
'tenant_rate': 1},
[['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
['tenant clock independent',
{'global_cap': 20,
'global_rate': 5,
'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [7, 'a', 2]],
'tenant_cap': 4,
'tenant_rate': 1},
[['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
['new tenant starts full',
{'global_cap': 10,
'global_rate': 2,
'requests': [[5, 'x', 3], [5, 'y', 2], [8, 'z', 3]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
['global capacity bound',
{'global_cap': 6,
'global_rate': 3,
'requests': [[0, 'a', 2],
[0, 'b', 2],
[0, 'c', 2],
[10, 'a', 2],
[10, 'b', 2],
[10, 'c', 2],
[12, 'd', 1]],
'tenant_cap': 2,
'tenant_rate': 2},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
5,
[['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
['random tenants',
{'global_cap': 5,
'global_rate': 2,
'requests': [[0, 'a', 2],
[0, 'c', 2],
[0, 'c', 2],
[2, 'b', 3],
[3, 'a', 2],
[3, 'c', 1],
[3, 'c', 1],
[4, 'a', 2],
[8, 'b', 2],
[8, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow',
'allow',
'deny-tenant',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow'],
2,
[['a', 0], ['b', 1], ['c', 2]]]]],
[['global exhaustion',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [4, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],
['partial global remains usable',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [3, 'd', 2]],
'tenant_cap': 5,
'tenant_rate': 1},
[['allow', 'deny-global', 'allow', 'allow'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
['both short reports tenant',
{'global_cap': 2,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [3, 'b', 2]],
'tenant_cap': 2,
'tenant_rate': 1},
[['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
['tenant clock independent',
{'global_cap': 20,
'global_rate': 5,
'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [8, 'a', 2]],
'tenant_cap': 4,
'tenant_rate': 1},
[['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
['new tenant starts full',
{'global_cap': 10,
'global_rate': 2,
'requests': [[5, 'x', 3], [5, 'y', 2], [9, 'z', 3]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
['global capacity bound',
{'global_cap': 6,
'global_rate': 3,
'requests': [[0, 'a', 2],
[0, 'b', 2],
[0, 'c', 2],
[10, 'a', 2],
[10, 'b', 2],
[10, 'c', 2],
[13, 'd', 1]],
'tenant_cap': 2,
'tenant_rate': 2},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
5,
[['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
['random tenants',
{'global_cap': 5,
'global_rate': 2,
'requests': [[0, 'a', 2],
[1, 'c', 2],
[2, 'a', 1],
[2, 'a', 2],
[2, 'b', 1],
[3, 'c', 2],
[3, 'c', 3],
[4, 'a', 3],
[7, 'a', 1],
[8, 'b', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'deny-tenant',
'deny-tenant',
'allow',
'allow'],
4,
[['a', 2], ['b', 2], ['c', 1]]]]],
[['global exhaustion',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [5, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],
['partial global remains usable',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [4, 'd', 2]],
'tenant_cap': 5,
'tenant_rate': 1},
[['allow', 'deny-global', 'allow', 'allow'], 2, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
['both short reports tenant',
{'global_cap': 2,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [4, 'b', 2]],
'tenant_cap': 2,
'tenant_rate': 1},
[['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
['tenant clock independent',
{'global_cap': 20,
'global_rate': 5,
'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [9, 'a', 2]],
'tenant_cap': 4,
'tenant_rate': 1},
[['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
['new tenant starts full',
{'global_cap': 10,
'global_rate': 2,
'requests': [[5, 'x', 3], [5, 'y', 2], [10, 'z', 3]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
['global capacity bound',
{'global_cap': 6,
'global_rate': 3,
'requests': [[0, 'a', 2],
[0, 'b', 2],
[0, 'c', 2],
[10, 'a', 2],
[10, 'b', 2],
[10, 'c', 2],
[14, 'd', 1]],
'tenant_cap': 2,
'tenant_rate': 2},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
5,
[['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
['random tenants',
{'global_cap': 5,
'global_rate': 2,
'requests': [[0, 'a', 3],
[1, 'a', 3],
[1, 'b', 3],
[1, 'c', 2],
[2, 'c', 2],
[3, 'a', 2],
[5, 'b', 2],
[6, 'b', 3],
[7, 'c', 1],
[8, 'a', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow',
'deny-tenant',
'allow',
'deny-global',
'allow',
'allow',
'allow',
'deny-tenant',
'allow',
'allow'],
4,
[['a', 2], ['b', 2], ['c', 2]]]]],
[['global exhaustion',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [6, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],
['partial global remains usable',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [5, 'd', 2]],
'tenant_cap': 5,
'tenant_rate': 1},
[['allow', 'deny-global', 'allow', 'allow'], 2, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
['both short reports tenant',
{'global_cap': 2,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [5, 'b', 2]],
'tenant_cap': 2,
'tenant_rate': 1},
[['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
['tenant clock independent',
{'global_cap': 20,
'global_rate': 5,
'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [10, 'a', 2]],
'tenant_cap': 4,
'tenant_rate': 1},
[['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
['new tenant starts full',
{'global_cap': 10,
'global_rate': 2,
'requests': [[5, 'x', 3], [5, 'y', 2], [11, 'z', 3]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
['global capacity bound',
{'global_cap': 6,
'global_rate': 3,
'requests': [[0, 'a', 2],
[0, 'b', 2],
[0, 'c', 2],
[10, 'a', 2],
[10, 'b', 2],
[10, 'c', 2],
[15, 'd', 1]],
'tenant_cap': 2,
'tenant_rate': 2},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
5,
[['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
['random tenants',
{'global_cap': 5,
'global_rate': 2,
'requests': [[0, 'c', 3],
[3, 'c', 1],
[3, 'c', 2],
[4, 'a', 1],
[7, 'a', 2],
[7, 'b', 1],
[7, 'b', 1],
[7, 'b', 2],
[7, 'c', 1],
[7, 'c', 2]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'deny-tenant',
'allow',
'deny-global'],
0,
[['a', 1], ['b', 1], ['c', 2]]]]]]
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 |
|---|---|---|---|
| global exhaustion | [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 1, [['a', 1], ['b', 1], ['c', 2]]] | [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 1, [['a', 1], ['b', 1], ['c', 2]]] | Passed |
| partial global remains usable | [['allow', 'deny-global', 'allow', 'deny-global'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 5]]] | [['allow', 'deny-global', 'allow', 'deny-global'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 5]]] | Passed |
| both short reports tenant | [['allow', 'deny-tenant', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]] | [['allow', 'deny-tenant', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]] | Passed |
| tenant clock independent | [['allow', 'allow', 'allow', 'allow'], 40, [['a', 1], ['b', 3]]] | [['allow', 'allow', 'allow', 'allow'], 18, [['a', 1], ['b', 3]]] | Failed |
| new tenant starts full | [['allow', 'allow', 'allow'], 16, [['x', 0], ['y', 1], ['z', 0]]] | [['allow', 'allow', 'allow'], 6, [['x', 0], ['y', 1], ['z', 0]]] | Failed |
| global capacity bound | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'], 26, [['a', 0], ['b', 0], ['c', 0], ['d', 1]]] | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'], 2, [['a', 0], ['b', 0], ['c', 0], ['d', 1]]] | Failed |
| random tenants | [['allow', 'deny-tenant', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'], 3, [['a', 1], ['b', 1], ['c', 0]]] | [['allow', 'deny-tenant', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'], 2, [['a', 1], ['b', 1], ['c', 0]]] | Failed |
SHA-256 / 0cf3f3dd85fd4079f9b7168b45ef0e64579791af1bb2945bb654c04ba1503a00
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
tc, tr = x['tenant_cap'], x['tenant_rate']
gc, gr = x['global_cap'], x['global_rate']
tenants = {}
g = [gc, 0]
out = []
for t, ten, cost in x['requests']:
st = tenants.setdefault(ten, [tc, t])
st[0] = min(tc, st[0] + (t - st[1]) * tr)
st[1] = t
g[0] = min(gc, g[0] + (t - g[1]) * gr)
g[1] = t
if st[0] < cost:
out.append('deny-tenant')
elif g[0] < cost:
out.append('deny-global')
else:
st[0] -= cost
g[0] -= cost
out.append('allow')
return [out, g[0], sorted([k, v[0]] for k, v in tenants.items())]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['global exhaustion',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [2, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 1, [['a', 1], ['b', 1], ['c', 2]]]],
['partial global remains usable',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [1, 'd', 2]],
'tenant_cap': 5,
'tenant_rate': 1},
[['allow', 'deny-global', 'allow', 'deny-global'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 5]]]],
['both short reports tenant',
{'global_cap': 2,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [1, 'b', 2]],
'tenant_cap': 2,
'tenant_rate': 1},
[['allow', 'deny-tenant', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]]],
['tenant clock independent',
{'global_cap': 20,
'global_rate': 5,
'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [6, 'a', 2]],
'tenant_cap': 4,
'tenant_rate': 1},
[['allow', 'allow', 'allow', 'allow'], 18, [['a', 1], ['b', 3]]]],
['new tenant starts full',
{'global_cap': 10,
'global_rate': 2,
'requests': [[5, 'x', 3], [5, 'y', 2], [7, 'z', 3]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'allow'], 6, [['x', 0], ['y', 1], ['z', 0]]]],
['global capacity bound',
{'global_cap': 6,
'global_rate': 3,
'requests': [[0, 'a', 2],
[0, 'b', 2],
[0, 'c', 2],
[10, 'a', 2],
[10, 'b', 2],
[10, 'c', 2],
[11, 'd', 1]],
'tenant_cap': 2,
'tenant_rate': 2},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
2,
[['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
['random tenants',
{'global_cap': 5,
'global_rate': 2,
'requests': [[0, 'a', 2],
[0, 'a', 3],
[1, 'b', 3],
[2, 'a', 1],
[3, 'c', 1],
[4, 'c', 3],
[5, 'a', 2],
[5, 'b', 1],
[6, 'a', 1],
[7, 'b', 2]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow',
'deny-tenant',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow'],
2,
[['a', 1], ['b', 1], ['c', 0]]]]],
[['global exhaustion',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [3, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 2, [['a', 1], ['b', 1], ['c', 2]]]],
['partial global remains usable',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [2, 'd', 2]],
'tenant_cap': 5,
'tenant_rate': 1},
[['allow', 'deny-global', 'allow', 'allow'], 0, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
['both short reports tenant',
{'global_cap': 2,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [2, 'b', 2]],
'tenant_cap': 2,
'tenant_rate': 1},
[['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
['tenant clock independent',
{'global_cap': 20,
'global_rate': 5,
'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [7, 'a', 2]],
'tenant_cap': 4,
'tenant_rate': 1},
[['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
['new tenant starts full',
{'global_cap': 10,
'global_rate': 2,
'requests': [[5, 'x', 3], [5, 'y', 2], [8, 'z', 3]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
['global capacity bound',
{'global_cap': 6,
'global_rate': 3,
'requests': [[0, 'a', 2],
[0, 'b', 2],
[0, 'c', 2],
[10, 'a', 2],
[10, 'b', 2],
[10, 'c', 2],
[12, 'd', 1]],
'tenant_cap': 2,
'tenant_rate': 2},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
5,
[['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
['random tenants',
{'global_cap': 5,
'global_rate': 2,
'requests': [[0, 'a', 2],
[0, 'c', 2],
[0, 'c', 2],
[2, 'b', 3],
[3, 'a', 2],
[3, 'c', 1],
[3, 'c', 1],
[4, 'a', 2],
[8, 'b', 2],
[8, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow',
'allow',
'deny-tenant',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow'],
2,
[['a', 0], ['b', 1], ['c', 2]]]]],
[['global exhaustion',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [4, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],
['partial global remains usable',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [3, 'd', 2]],
'tenant_cap': 5,
'tenant_rate': 1},
[['allow', 'deny-global', 'allow', 'allow'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
['both short reports tenant',
{'global_cap': 2,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [3, 'b', 2]],
'tenant_cap': 2,
'tenant_rate': 1},
[['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
['tenant clock independent',
{'global_cap': 20,
'global_rate': 5,
'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [8, 'a', 2]],
'tenant_cap': 4,
'tenant_rate': 1},
[['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
['new tenant starts full',
{'global_cap': 10,
'global_rate': 2,
'requests': [[5, 'x', 3], [5, 'y', 2], [9, 'z', 3]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
['global capacity bound',
{'global_cap': 6,
'global_rate': 3,
'requests': [[0, 'a', 2],
[0, 'b', 2],
[0, 'c', 2],
[10, 'a', 2],
[10, 'b', 2],
[10, 'c', 2],
[13, 'd', 1]],
'tenant_cap': 2,
'tenant_rate': 2},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
5,
[['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
['random tenants',
{'global_cap': 5,
'global_rate': 2,
'requests': [[0, 'a', 2],
[1, 'c', 2],
[2, 'a', 1],
[2, 'a', 2],
[2, 'b', 1],
[3, 'c', 2],
[3, 'c', 3],
[4, 'a', 3],
[7, 'a', 1],
[8, 'b', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'deny-tenant',
'deny-tenant',
'allow',
'allow'],
4,
[['a', 2], ['b', 2], ['c', 1]]]]],
[['global exhaustion',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [5, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],
['partial global remains usable',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [4, 'd', 2]],
'tenant_cap': 5,
'tenant_rate': 1},
[['allow', 'deny-global', 'allow', 'allow'], 2, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
['both short reports tenant',
{'global_cap': 2,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [4, 'b', 2]],
'tenant_cap': 2,
'tenant_rate': 1},
[['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
['tenant clock independent',
{'global_cap': 20,
'global_rate': 5,
'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [9, 'a', 2]],
'tenant_cap': 4,
'tenant_rate': 1},
[['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
['new tenant starts full',
{'global_cap': 10,
'global_rate': 2,
'requests': [[5, 'x', 3], [5, 'y', 2], [10, 'z', 3]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
['global capacity bound',
{'global_cap': 6,
'global_rate': 3,
'requests': [[0, 'a', 2],
[0, 'b', 2],
[0, 'c', 2],
[10, 'a', 2],
[10, 'b', 2],
[10, 'c', 2],
[14, 'd', 1]],
'tenant_cap': 2,
'tenant_rate': 2},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
5,
[['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
['random tenants',
{'global_cap': 5,
'global_rate': 2,
'requests': [[0, 'a', 3],
[1, 'a', 3],
[1, 'b', 3],
[1, 'c', 2],
[2, 'c', 2],
[3, 'a', 2],
[5, 'b', 2],
[6, 'b', 3],
[7, 'c', 1],
[8, 'a', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow',
'deny-tenant',
'allow',
'deny-global',
'allow',
'allow',
'allow',
'deny-tenant',
'allow',
'allow'],
4,
[['a', 2], ['b', 2], ['c', 2]]]]],
[['global exhaustion',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [6, 'c', 1]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],
['partial global remains usable',
{'global_cap': 4,
'global_rate': 1,
'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [5, 'd', 2]],
'tenant_cap': 5,
'tenant_rate': 1},
[['allow', 'deny-global', 'allow', 'allow'], 2, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],
['both short reports tenant',
{'global_cap': 2,
'global_rate': 1,
'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [5, 'b', 2]],
'tenant_cap': 2,
'tenant_rate': 1},
[['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],
['tenant clock independent',
{'global_cap': 20,
'global_rate': 5,
'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [10, 'a', 2]],
'tenant_cap': 4,
'tenant_rate': 1},
[['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],
['new tenant starts full',
{'global_cap': 10,
'global_rate': 2,
'requests': [[5, 'x', 3], [5, 'y', 2], [11, 'z', 3]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],
['global capacity bound',
{'global_cap': 6,
'global_rate': 3,
'requests': [[0, 'a', 2],
[0, 'b', 2],
[0, 'c', 2],
[10, 'a', 2],
[10, 'b', 2],
[10, 'c', 2],
[15, 'd', 1]],
'tenant_cap': 2,
'tenant_rate': 2},
[['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],
5,
[['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],
['random tenants',
{'global_cap': 5,
'global_rate': 2,
'requests': [[0, 'c', 3],
[3, 'c', 1],
[3, 'c', 2],
[4, 'a', 1],
[7, 'a', 2],
[7, 'b', 1],
[7, 'b', 1],
[7, 'b', 2],
[7, 'c', 1],
[7, 'c', 2]],
'tenant_cap': 3,
'tenant_rate': 1},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'deny-tenant',
'allow',
'deny-global'],
0,
[['a', 1], ['b', 1], ['c', 2]]]]]]
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 |
|---|---|---|---|
| global exhaustion | [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 1, [['a', 1], ['b', 1], ['c', 2]]] | [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 1, [['a', 1], ['b', 1], ['c', 2]]] | Passed |
| partial global remains usable | [['allow', 'deny-global', 'allow', 'deny-global'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 5]]] | [['allow', 'deny-global', 'allow', 'deny-global'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 5]]] | Passed |
| both short reports tenant | [['allow', 'deny-tenant', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]] | [['allow', 'deny-tenant', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]] | Passed |
| tenant clock independent | [['allow', 'allow', 'allow', 'allow'], 18, [['a', 1], ['b', 3]]] | [['allow', 'allow', 'allow', 'allow'], 18, [['a', 1], ['b', 3]]] | Passed |
| new tenant starts full | [['allow', 'allow', 'allow'], 6, [['x', 0], ['y', 1], ['z', 0]]] | [['allow', 'allow', 'allow'], 6, [['x', 0], ['y', 1], ['z', 0]]] | Passed |
| global capacity bound | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'], 2, [['a', 0], ['b', 0], ['c', 0], ['d', 1]]] | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'], 2, [['a', 0], ['b', 0], ['c', 0], ['d', 1]]] | Passed |
| random tenants | [['allow', 'deny-tenant', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'], 2, [['a', 1], ['b', 1], ['c', 0]]] | [['allow', 'deny-tenant', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'], 2, [['a', 1], ['b', 1], ['c', 0]]] | Passed |
SHA-256 / 049e21592079d6f8740cfc43678d3401fcd6b9bd1bb6e386cbf40a786ebc95c9
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:48.583254+00:00.
Case digest / b8d9421c3d5bb012003353d5e221ff2af77f74c26137abd71775013ae2f49041