FA-73536 / Rate limiter algorithms / Open access
Hierarchical tenant and global token buckets: tenant refills from the global clock · case 01
A tenant idle while others were active never refills, because the elapsed time is measured from anyone's last request.
ROOT CAUSE
Tenant refill uses the global last-seen time.
VERIFIED REPAIR
Refill each tenant from its own last-seen time.
Unsuccessful approach: Refilling only when short still advances the tenant clock and discards accrued 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 - g[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', 'deny-tenant', 'allow'], 18, [['a', 1], ['b', 3]]] | [['allow', 'allow', 'allow', 'allow'], 18, [['a', 1], ['b', 3]]] | Failed |
| 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', 'deny-tenant', 'deny-tenant', 'allow'], 5, [['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', 'deny-tenant', 'allow', 'deny-tenant'], 5, [['a', 0], ['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 / df4b9f4f518fc6a7611f2b441e6e89360b4e7aa20d763166c7e3e4b0b3926526
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) if st[0] < cost else st[0]
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', 0], ['b', 0], ['c', 0]]] | [['allow', 'deny-tenant', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'], 2, [['a', 1], ['b', 1], ['c', 0]]] | Failed |
SHA-256 / 83e24c963bde07b9c2a111cb5cedb958df35e09dd8575a3aa89ac8d56002da1e
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.543023+00:00.
Case digest / cc24381d271037c100096aa20cfe0a605279e110148b28c89b4227b19f51e7fa