FA-73531 / Rate limiter algorithms / Open access
Hierarchical tenant and global token buckets: global reason reported before tenant reason · case 01
Tenants over their own limit are told the shared service is saturated.
ROOT CAUSE
The global check runs before the tenant check.
VERIFIED REPAIR
Check the tenant bucket first.
Unsuccessful approach: A combined reason is not one of the contract outcomes.
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(gc, g[0] + (t - g[1]) * gr)
g[1] = t
if g[0] < cost:
out.append('deny-global')
elif st[0] < cost:
out.append('deny-tenant')
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-global', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]] | [['allow', 'deny-tenant', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]] | Failed |
| 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 / 369cffc70eb68183ee16466bc574703d0205c1f1882bc626e064383e4ea5d1bf
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] = min(gc, g[0] + (t - g[1]) * gr)
g[1] = t
if st[0] < cost and g[0] < cost:
out.append('deny-both')
elif 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-both', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]] | [['allow', 'deny-tenant', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]] | Failed |
| 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 / a336c6240d25124c0e673618e6a99a50024cd77ff5f4e146ef22289ab949a6f5
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.454466+00:00.
Case digest / 9c7601e28ddca26a605095996e0e6942fae13425cc1f6f209caeed58bc60106b