{"abstract":"The shared bucket can never hold more than one tenant's capacity, throttling the fleet.","category":"Rate limiter algorithms","checks":7,"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]].","evaluation_group":"w2-rate_limiter_algorithms-hierarchical-buckets","failed_approach":"Removing the clamp lets the global bucket bank unlimited tokens.","family":"w2-rate_limiter_algorithms-hierarchical-buckets-global-cap","id":"FA-73546","implementations":{"attempt":{"sha256":"0cf3f3dd85fd4079f9b7168b45ef0e64579791af1bb2945bb654c04ba1503a00","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    tc, tr = x['tenant_cap'], x['tenant_rate']\n    gc, gr = x['global_cap'], x['global_rate']\n    tenants = {}\n    g = [gc, 0]\n    out = []\n    for t, ten, cost in x['requests']:\n        st = tenants.setdefault(ten, [tc, t])\n        st[0] = min(tc, st[0] + (t - st[1]) * tr)\n        st[1] = t\n        g[0] = g[0] + (t - g[1]) * gr\n        g[1] = t\n        if st[0] < cost:\n            out.append('deny-tenant')\n        elif g[0] < cost:\n            out.append('deny-global')\n        else:\n            st[0] -= cost\n            g[0] -= cost\n            out.append('allow')\n    return [out, g[0], sorted([k, v[0]] for k, v in tenants.items())]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['global exhaustion',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [2, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 1, [['a', 1], ['b', 1], ['c', 2]]]],\n  ['partial global remains usable',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [1, 'd', 2]],\n    'tenant_cap': 5,\n    'tenant_rate': 1},\n   [['allow', 'deny-global', 'allow', 'deny-global'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 5]]]],\n  ['both short reports tenant',\n   {'global_cap': 2,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [1, 'b', 2]],\n    'tenant_cap': 2,\n    'tenant_rate': 1},\n   [['allow', 'deny-tenant', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]]],\n  ['tenant clock independent',\n   {'global_cap': 20,\n    'global_rate': 5,\n    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [6, 'a', 2]],\n    'tenant_cap': 4,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 1], ['b', 3]]]],\n  ['new tenant starts full',\n   {'global_cap': 10,\n    'global_rate': 2,\n    'requests': [[5, 'x', 3], [5, 'y', 2], [7, 'z', 3]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow'], 6, [['x', 0], ['y', 1], ['z', 0]]]],\n  ['global capacity bound',\n   {'global_cap': 6,\n    'global_rate': 3,\n    'requests': [[0, 'a', 2],\n                 [0, 'b', 2],\n                 [0, 'c', 2],\n                 [10, 'a', 2],\n                 [10, 'b', 2],\n                 [10, 'c', 2],\n                 [11, 'd', 1]],\n    'tenant_cap': 2,\n    'tenant_rate': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],\n    2,\n    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],\n  ['random tenants',\n   {'global_cap': 5,\n    'global_rate': 2,\n    'requests': [[0, 'a', 2],\n                 [0, 'a', 3],\n                 [1, 'b', 3],\n                 [2, 'a', 1],\n                 [3, 'c', 1],\n                 [4, 'c', 3],\n                 [5, 'a', 2],\n                 [5, 'b', 1],\n                 [6, 'a', 1],\n                 [7, 'b', 2]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow',\n     'deny-tenant',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    2,\n    [['a', 1], ['b', 1], ['c', 0]]]]],\n [['global exhaustion',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [3, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 2, [['a', 1], ['b', 1], ['c', 2]]]],\n  ['partial global remains usable',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [2, 'd', 2]],\n    'tenant_cap': 5,\n    'tenant_rate': 1},\n   [['allow', 'deny-global', 'allow', 'allow'], 0, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],\n  ['both short reports tenant',\n   {'global_cap': 2,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [2, 'b', 2]],\n    'tenant_cap': 2,\n    'tenant_rate': 1},\n   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],\n  ['tenant clock independent',\n   {'global_cap': 20,\n    'global_rate': 5,\n    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [7, 'a', 2]],\n    'tenant_cap': 4,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],\n  ['new tenant starts full',\n   {'global_cap': 10,\n    'global_rate': 2,\n    'requests': [[5, 'x', 3], [5, 'y', 2], [8, 'z', 3]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],\n  ['global capacity bound',\n   {'global_cap': 6,\n    'global_rate': 3,\n    'requests': [[0, 'a', 2],\n                 [0, 'b', 2],\n                 [0, 'c', 2],\n                 [10, 'a', 2],\n                 [10, 'b', 2],\n                 [10, 'c', 2],\n                 [12, 'd', 1]],\n    'tenant_cap': 2,\n    'tenant_rate': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],\n    5,\n    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],\n  ['random tenants',\n   {'global_cap': 5,\n    'global_rate': 2,\n    'requests': [[0, 'a', 2],\n                 [0, 'c', 2],\n                 [0, 'c', 2],\n                 [2, 'b', 3],\n                 [3, 'a', 2],\n                 [3, 'c', 1],\n                 [3, 'c', 1],\n                 [4, 'a', 2],\n                 [8, 'b', 2],\n                 [8, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow',\n     'allow',\n     'deny-tenant',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    2,\n    [['a', 0], ['b', 1], ['c', 2]]]]],\n [['global exhaustion',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [4, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],\n  ['partial global remains usable',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [3, 'd', 2]],\n    'tenant_cap': 5,\n    'tenant_rate': 1},\n   [['allow', 'deny-global', 'allow', 'allow'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],\n  ['both short reports tenant',\n   {'global_cap': 2,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [3, 'b', 2]],\n    'tenant_cap': 2,\n    'tenant_rate': 1},\n   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],\n  ['tenant clock independent',\n   {'global_cap': 20,\n    'global_rate': 5,\n    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [8, 'a', 2]],\n    'tenant_cap': 4,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],\n  ['new tenant starts full',\n   {'global_cap': 10,\n    'global_rate': 2,\n    'requests': [[5, 'x', 3], [5, 'y', 2], [9, 'z', 3]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],\n  ['global capacity bound',\n   {'global_cap': 6,\n    'global_rate': 3,\n    'requests': [[0, 'a', 2],\n                 [0, 'b', 2],\n                 [0, 'c', 2],\n                 [10, 'a', 2],\n                 [10, 'b', 2],\n                 [10, 'c', 2],\n                 [13, 'd', 1]],\n    'tenant_cap': 2,\n    'tenant_rate': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],\n    5,\n    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],\n  ['random tenants',\n   {'global_cap': 5,\n    'global_rate': 2,\n    'requests': [[0, 'a', 2],\n                 [1, 'c', 2],\n                 [2, 'a', 1],\n                 [2, 'a', 2],\n                 [2, 'b', 1],\n                 [3, 'c', 2],\n                 [3, 'c', 3],\n                 [4, 'a', 3],\n                 [7, 'a', 1],\n                 [8, 'b', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny-tenant',\n     'deny-tenant',\n     'allow',\n     'allow'],\n    4,\n    [['a', 2], ['b', 2], ['c', 1]]]]],\n [['global exhaustion',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [5, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],\n  ['partial global remains usable',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [4, 'd', 2]],\n    'tenant_cap': 5,\n    'tenant_rate': 1},\n   [['allow', 'deny-global', 'allow', 'allow'], 2, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],\n  ['both short reports tenant',\n   {'global_cap': 2,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [4, 'b', 2]],\n    'tenant_cap': 2,\n    'tenant_rate': 1},\n   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],\n  ['tenant clock independent',\n   {'global_cap': 20,\n    'global_rate': 5,\n    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [9, 'a', 2]],\n    'tenant_cap': 4,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],\n  ['new tenant starts full',\n   {'global_cap': 10,\n    'global_rate': 2,\n    'requests': [[5, 'x', 3], [5, 'y', 2], [10, 'z', 3]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],\n  ['global capacity bound',\n   {'global_cap': 6,\n    'global_rate': 3,\n    'requests': [[0, 'a', 2],\n                 [0, 'b', 2],\n                 [0, 'c', 2],\n                 [10, 'a', 2],\n                 [10, 'b', 2],\n                 [10, 'c', 2],\n                 [14, 'd', 1]],\n    'tenant_cap': 2,\n    'tenant_rate': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],\n    5,\n    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],\n  ['random tenants',\n   {'global_cap': 5,\n    'global_rate': 2,\n    'requests': [[0, 'a', 3],\n                 [1, 'a', 3],\n                 [1, 'b', 3],\n                 [1, 'c', 2],\n                 [2, 'c', 2],\n                 [3, 'a', 2],\n                 [5, 'b', 2],\n                 [6, 'b', 3],\n                 [7, 'c', 1],\n                 [8, 'a', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow',\n     'deny-tenant',\n     'allow',\n     'deny-global',\n     'allow',\n     'allow',\n     'allow',\n     'deny-tenant',\n     'allow',\n     'allow'],\n    4,\n    [['a', 2], ['b', 2], ['c', 2]]]]],\n [['global exhaustion',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [6, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],\n  ['partial global remains usable',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [5, 'd', 2]],\n    'tenant_cap': 5,\n    'tenant_rate': 1},\n   [['allow', 'deny-global', 'allow', 'allow'], 2, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],\n  ['both short reports tenant',\n   {'global_cap': 2,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [5, 'b', 2]],\n    'tenant_cap': 2,\n    'tenant_rate': 1},\n   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],\n  ['tenant clock independent',\n   {'global_cap': 20,\n    'global_rate': 5,\n    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [10, 'a', 2]],\n    'tenant_cap': 4,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],\n  ['new tenant starts full',\n   {'global_cap': 10,\n    'global_rate': 2,\n    'requests': [[5, 'x', 3], [5, 'y', 2], [11, 'z', 3]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],\n  ['global capacity bound',\n   {'global_cap': 6,\n    'global_rate': 3,\n    'requests': [[0, 'a', 2],\n                 [0, 'b', 2],\n                 [0, 'c', 2],\n                 [10, 'a', 2],\n                 [10, 'b', 2],\n                 [10, 'c', 2],\n                 [15, 'd', 1]],\n    'tenant_cap': 2,\n    'tenant_rate': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],\n    5,\n    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],\n  ['random tenants',\n   {'global_cap': 5,\n    'global_rate': 2,\n    'requests': [[0, 'c', 3],\n                 [3, 'c', 1],\n                 [3, 'c', 2],\n                 [4, 'a', 1],\n                 [7, 'a', 2],\n                 [7, 'b', 1],\n                 [7, 'b', 1],\n                 [7, 'b', 2],\n                 [7, 'c', 1],\n                 [7, 'c', 2]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny-tenant',\n     'allow',\n     'deny-global'],\n    0,\n    [['a', 1], ['b', 1], ['c', 2]]]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"18e3db0d4a2a692e2d2d08b165d7cfbc4faf8338f4d4cf27f0821e6453e30939","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    tc, tr = x['tenant_cap'], x['tenant_rate']\n    gc, gr = x['global_cap'], x['global_rate']\n    tenants = {}\n    g = [gc, 0]\n    out = []\n    for t, ten, cost in x['requests']:\n        st = tenants.setdefault(ten, [tc, t])\n        st[0] = min(tc, st[0] + (t - st[1]) * tr)\n        st[1] = t\n        g[0] = min(tc, g[0] + (t - g[1]) * gr)\n        g[1] = t\n        if st[0] < cost:\n            out.append('deny-tenant')\n        elif g[0] < cost:\n            out.append('deny-global')\n        else:\n            st[0] -= cost\n            g[0] -= cost\n            out.append('allow')\n    return [out, g[0], sorted([k, v[0]] for k, v in tenants.items())]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['global exhaustion',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [2, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 1, [['a', 1], ['b', 1], ['c', 2]]]],\n  ['partial global remains usable',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [1, 'd', 2]],\n    'tenant_cap': 5,\n    'tenant_rate': 1},\n   [['allow', 'deny-global', 'allow', 'deny-global'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 5]]]],\n  ['both short reports tenant',\n   {'global_cap': 2,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [1, 'b', 2]],\n    'tenant_cap': 2,\n    'tenant_rate': 1},\n   [['allow', 'deny-tenant', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]]],\n  ['tenant clock independent',\n   {'global_cap': 20,\n    'global_rate': 5,\n    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [6, 'a', 2]],\n    'tenant_cap': 4,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 1], ['b', 3]]]],\n  ['new tenant starts full',\n   {'global_cap': 10,\n    'global_rate': 2,\n    'requests': [[5, 'x', 3], [5, 'y', 2], [7, 'z', 3]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow'], 6, [['x', 0], ['y', 1], ['z', 0]]]],\n  ['global capacity bound',\n   {'global_cap': 6,\n    'global_rate': 3,\n    'requests': [[0, 'a', 2],\n                 [0, 'b', 2],\n                 [0, 'c', 2],\n                 [10, 'a', 2],\n                 [10, 'b', 2],\n                 [10, 'c', 2],\n                 [11, 'd', 1]],\n    'tenant_cap': 2,\n    'tenant_rate': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],\n    2,\n    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],\n  ['random tenants',\n   {'global_cap': 5,\n    'global_rate': 2,\n    'requests': [[0, 'a', 2],\n                 [0, 'a', 3],\n                 [1, 'b', 3],\n                 [2, 'a', 1],\n                 [3, 'c', 1],\n                 [4, 'c', 3],\n                 [5, 'a', 2],\n                 [5, 'b', 1],\n                 [6, 'a', 1],\n                 [7, 'b', 2]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow',\n     'deny-tenant',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    2,\n    [['a', 1], ['b', 1], ['c', 0]]]]],\n [['global exhaustion',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [3, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 2, [['a', 1], ['b', 1], ['c', 2]]]],\n  ['partial global remains usable',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [2, 'd', 2]],\n    'tenant_cap': 5,\n    'tenant_rate': 1},\n   [['allow', 'deny-global', 'allow', 'allow'], 0, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],\n  ['both short reports tenant',\n   {'global_cap': 2,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [2, 'b', 2]],\n    'tenant_cap': 2,\n    'tenant_rate': 1},\n   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],\n  ['tenant clock independent',\n   {'global_cap': 20,\n    'global_rate': 5,\n    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [7, 'a', 2]],\n    'tenant_cap': 4,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],\n  ['new tenant starts full',\n   {'global_cap': 10,\n    'global_rate': 2,\n    'requests': [[5, 'x', 3], [5, 'y', 2], [8, 'z', 3]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],\n  ['global capacity bound',\n   {'global_cap': 6,\n    'global_rate': 3,\n    'requests': [[0, 'a', 2],\n                 [0, 'b', 2],\n                 [0, 'c', 2],\n                 [10, 'a', 2],\n                 [10, 'b', 2],\n                 [10, 'c', 2],\n                 [12, 'd', 1]],\n    'tenant_cap': 2,\n    'tenant_rate': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],\n    5,\n    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],\n  ['random tenants',\n   {'global_cap': 5,\n    'global_rate': 2,\n    'requests': [[0, 'a', 2],\n                 [0, 'c', 2],\n                 [0, 'c', 2],\n                 [2, 'b', 3],\n                 [3, 'a', 2],\n                 [3, 'c', 1],\n                 [3, 'c', 1],\n                 [4, 'a', 2],\n                 [8, 'b', 2],\n                 [8, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow',\n     'allow',\n     'deny-tenant',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    2,\n    [['a', 0], ['b', 1], ['c', 2]]]]],\n [['global exhaustion',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [4, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],\n  ['partial global remains usable',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [3, 'd', 2]],\n    'tenant_cap': 5,\n    'tenant_rate': 1},\n   [['allow', 'deny-global', 'allow', 'allow'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],\n  ['both short reports tenant',\n   {'global_cap': 2,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [3, 'b', 2]],\n    'tenant_cap': 2,\n    'tenant_rate': 1},\n   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],\n  ['tenant clock independent',\n   {'global_cap': 20,\n    'global_rate': 5,\n    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [8, 'a', 2]],\n    'tenant_cap': 4,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],\n  ['new tenant starts full',\n   {'global_cap': 10,\n    'global_rate': 2,\n    'requests': [[5, 'x', 3], [5, 'y', 2], [9, 'z', 3]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],\n  ['global capacity bound',\n   {'global_cap': 6,\n    'global_rate': 3,\n    'requests': [[0, 'a', 2],\n                 [0, 'b', 2],\n                 [0, 'c', 2],\n                 [10, 'a', 2],\n                 [10, 'b', 2],\n                 [10, 'c', 2],\n                 [13, 'd', 1]],\n    'tenant_cap': 2,\n    'tenant_rate': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],\n    5,\n    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],\n  ['random tenants',\n   {'global_cap': 5,\n    'global_rate': 2,\n    'requests': [[0, 'a', 2],\n                 [1, 'c', 2],\n                 [2, 'a', 1],\n                 [2, 'a', 2],\n                 [2, 'b', 1],\n                 [3, 'c', 2],\n                 [3, 'c', 3],\n                 [4, 'a', 3],\n                 [7, 'a', 1],\n                 [8, 'b', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny-tenant',\n     'deny-tenant',\n     'allow',\n     'allow'],\n    4,\n    [['a', 2], ['b', 2], ['c', 1]]]]],\n [['global exhaustion',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [5, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],\n  ['partial global remains usable',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [4, 'd', 2]],\n    'tenant_cap': 5,\n    'tenant_rate': 1},\n   [['allow', 'deny-global', 'allow', 'allow'], 2, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],\n  ['both short reports tenant',\n   {'global_cap': 2,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [4, 'b', 2]],\n    'tenant_cap': 2,\n    'tenant_rate': 1},\n   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],\n  ['tenant clock independent',\n   {'global_cap': 20,\n    'global_rate': 5,\n    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [9, 'a', 2]],\n    'tenant_cap': 4,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],\n  ['new tenant starts full',\n   {'global_cap': 10,\n    'global_rate': 2,\n    'requests': [[5, 'x', 3], [5, 'y', 2], [10, 'z', 3]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],\n  ['global capacity bound',\n   {'global_cap': 6,\n    'global_rate': 3,\n    'requests': [[0, 'a', 2],\n                 [0, 'b', 2],\n                 [0, 'c', 2],\n                 [10, 'a', 2],\n                 [10, 'b', 2],\n                 [10, 'c', 2],\n                 [14, 'd', 1]],\n    'tenant_cap': 2,\n    'tenant_rate': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],\n    5,\n    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],\n  ['random tenants',\n   {'global_cap': 5,\n    'global_rate': 2,\n    'requests': [[0, 'a', 3],\n                 [1, 'a', 3],\n                 [1, 'b', 3],\n                 [1, 'c', 2],\n                 [2, 'c', 2],\n                 [3, 'a', 2],\n                 [5, 'b', 2],\n                 [6, 'b', 3],\n                 [7, 'c', 1],\n                 [8, 'a', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow',\n     'deny-tenant',\n     'allow',\n     'deny-global',\n     'allow',\n     'allow',\n     'allow',\n     'deny-tenant',\n     'allow',\n     'allow'],\n    4,\n    [['a', 2], ['b', 2], ['c', 2]]]]],\n [['global exhaustion',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [6, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],\n  ['partial global remains usable',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [5, 'd', 2]],\n    'tenant_cap': 5,\n    'tenant_rate': 1},\n   [['allow', 'deny-global', 'allow', 'allow'], 2, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],\n  ['both short reports tenant',\n   {'global_cap': 2,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [5, 'b', 2]],\n    'tenant_cap': 2,\n    'tenant_rate': 1},\n   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],\n  ['tenant clock independent',\n   {'global_cap': 20,\n    'global_rate': 5,\n    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [10, 'a', 2]],\n    'tenant_cap': 4,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],\n  ['new tenant starts full',\n   {'global_cap': 10,\n    'global_rate': 2,\n    'requests': [[5, 'x', 3], [5, 'y', 2], [11, 'z', 3]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],\n  ['global capacity bound',\n   {'global_cap': 6,\n    'global_rate': 3,\n    'requests': [[0, 'a', 2],\n                 [0, 'b', 2],\n                 [0, 'c', 2],\n                 [10, 'a', 2],\n                 [10, 'b', 2],\n                 [10, 'c', 2],\n                 [15, 'd', 1]],\n    'tenant_cap': 2,\n    'tenant_rate': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],\n    5,\n    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],\n  ['random tenants',\n   {'global_cap': 5,\n    'global_rate': 2,\n    'requests': [[0, 'c', 3],\n                 [3, 'c', 1],\n                 [3, 'c', 2],\n                 [4, 'a', 1],\n                 [7, 'a', 2],\n                 [7, 'b', 1],\n                 [7, 'b', 1],\n                 [7, 'b', 2],\n                 [7, 'c', 1],\n                 [7, 'c', 2]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny-tenant',\n     'allow',\n     'deny-global'],\n    0,\n    [['a', 1], ['b', 1], ['c', 2]]]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"fixed":{"sha256":"049e21592079d6f8740cfc43678d3401fcd6b9bd1bb6e386cbf40a786ebc95c9","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    tc, tr = x['tenant_cap'], x['tenant_rate']\n    gc, gr = x['global_cap'], x['global_rate']\n    tenants = {}\n    g = [gc, 0]\n    out = []\n    for t, ten, cost in x['requests']:\n        st = tenants.setdefault(ten, [tc, t])\n        st[0] = min(tc, st[0] + (t - st[1]) * tr)\n        st[1] = t\n        g[0] = min(gc, g[0] + (t - g[1]) * gr)\n        g[1] = t\n        if st[0] < cost:\n            out.append('deny-tenant')\n        elif g[0] < cost:\n            out.append('deny-global')\n        else:\n            st[0] -= cost\n            g[0] -= cost\n            out.append('allow')\n    return [out, g[0], sorted([k, v[0]] for k, v in tenants.items())]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['global exhaustion',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [2, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 1, [['a', 1], ['b', 1], ['c', 2]]]],\n  ['partial global remains usable',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [1, 'd', 2]],\n    'tenant_cap': 5,\n    'tenant_rate': 1},\n   [['allow', 'deny-global', 'allow', 'deny-global'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 5]]]],\n  ['both short reports tenant',\n   {'global_cap': 2,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [1, 'b', 2]],\n    'tenant_cap': 2,\n    'tenant_rate': 1},\n   [['allow', 'deny-tenant', 'deny-global', 'deny-global'], 1, [['a', 0], ['b', 2]]]],\n  ['tenant clock independent',\n   {'global_cap': 20,\n    'global_rate': 5,\n    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [6, 'a', 2]],\n    'tenant_cap': 4,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 1], ['b', 3]]]],\n  ['new tenant starts full',\n   {'global_cap': 10,\n    'global_rate': 2,\n    'requests': [[5, 'x', 3], [5, 'y', 2], [7, 'z', 3]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow'], 6, [['x', 0], ['y', 1], ['z', 0]]]],\n  ['global capacity bound',\n   {'global_cap': 6,\n    'global_rate': 3,\n    'requests': [[0, 'a', 2],\n                 [0, 'b', 2],\n                 [0, 'c', 2],\n                 [10, 'a', 2],\n                 [10, 'b', 2],\n                 [10, 'c', 2],\n                 [11, 'd', 1]],\n    'tenant_cap': 2,\n    'tenant_rate': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],\n    2,\n    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],\n  ['random tenants',\n   {'global_cap': 5,\n    'global_rate': 2,\n    'requests': [[0, 'a', 2],\n                 [0, 'a', 3],\n                 [1, 'b', 3],\n                 [2, 'a', 1],\n                 [3, 'c', 1],\n                 [4, 'c', 3],\n                 [5, 'a', 2],\n                 [5, 'b', 1],\n                 [6, 'a', 1],\n                 [7, 'b', 2]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow',\n     'deny-tenant',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    2,\n    [['a', 1], ['b', 1], ['c', 0]]]]],\n [['global exhaustion',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [3, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 2, [['a', 1], ['b', 1], ['c', 2]]]],\n  ['partial global remains usable',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [2, 'd', 2]],\n    'tenant_cap': 5,\n    'tenant_rate': 1},\n   [['allow', 'deny-global', 'allow', 'allow'], 0, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],\n  ['both short reports tenant',\n   {'global_cap': 2,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [2, 'b', 2]],\n    'tenant_cap': 2,\n    'tenant_rate': 1},\n   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],\n  ['tenant clock independent',\n   {'global_cap': 20,\n    'global_rate': 5,\n    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [7, 'a', 2]],\n    'tenant_cap': 4,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],\n  ['new tenant starts full',\n   {'global_cap': 10,\n    'global_rate': 2,\n    'requests': [[5, 'x', 3], [5, 'y', 2], [8, 'z', 3]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],\n  ['global capacity bound',\n   {'global_cap': 6,\n    'global_rate': 3,\n    'requests': [[0, 'a', 2],\n                 [0, 'b', 2],\n                 [0, 'c', 2],\n                 [10, 'a', 2],\n                 [10, 'b', 2],\n                 [10, 'c', 2],\n                 [12, 'd', 1]],\n    'tenant_cap': 2,\n    'tenant_rate': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],\n    5,\n    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],\n  ['random tenants',\n   {'global_cap': 5,\n    'global_rate': 2,\n    'requests': [[0, 'a', 2],\n                 [0, 'c', 2],\n                 [0, 'c', 2],\n                 [2, 'b', 3],\n                 [3, 'a', 2],\n                 [3, 'c', 1],\n                 [3, 'c', 1],\n                 [4, 'a', 2],\n                 [8, 'b', 2],\n                 [8, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow',\n     'allow',\n     'deny-tenant',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    2,\n    [['a', 0], ['b', 1], ['c', 2]]]]],\n [['global exhaustion',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [4, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],\n  ['partial global remains usable',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [3, 'd', 2]],\n    'tenant_cap': 5,\n    'tenant_rate': 1},\n   [['allow', 'deny-global', 'allow', 'allow'], 1, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],\n  ['both short reports tenant',\n   {'global_cap': 2,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [3, 'b', 2]],\n    'tenant_cap': 2,\n    'tenant_rate': 1},\n   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],\n  ['tenant clock independent',\n   {'global_cap': 20,\n    'global_rate': 5,\n    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [8, 'a', 2]],\n    'tenant_cap': 4,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],\n  ['new tenant starts full',\n   {'global_cap': 10,\n    'global_rate': 2,\n    'requests': [[5, 'x', 3], [5, 'y', 2], [9, 'z', 3]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],\n  ['global capacity bound',\n   {'global_cap': 6,\n    'global_rate': 3,\n    'requests': [[0, 'a', 2],\n                 [0, 'b', 2],\n                 [0, 'c', 2],\n                 [10, 'a', 2],\n                 [10, 'b', 2],\n                 [10, 'c', 2],\n                 [13, 'd', 1]],\n    'tenant_cap': 2,\n    'tenant_rate': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],\n    5,\n    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],\n  ['random tenants',\n   {'global_cap': 5,\n    'global_rate': 2,\n    'requests': [[0, 'a', 2],\n                 [1, 'c', 2],\n                 [2, 'a', 1],\n                 [2, 'a', 2],\n                 [2, 'b', 1],\n                 [3, 'c', 2],\n                 [3, 'c', 3],\n                 [4, 'a', 3],\n                 [7, 'a', 1],\n                 [8, 'b', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny-tenant',\n     'deny-tenant',\n     'allow',\n     'allow'],\n    4,\n    [['a', 2], ['b', 2], ['c', 1]]]]],\n [['global exhaustion',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [5, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],\n  ['partial global remains usable',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [4, 'd', 2]],\n    'tenant_cap': 5,\n    'tenant_rate': 1},\n   [['allow', 'deny-global', 'allow', 'allow'], 2, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],\n  ['both short reports tenant',\n   {'global_cap': 2,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [4, 'b', 2]],\n    'tenant_cap': 2,\n    'tenant_rate': 1},\n   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],\n  ['tenant clock independent',\n   {'global_cap': 20,\n    'global_rate': 5,\n    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [9, 'a', 2]],\n    'tenant_cap': 4,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],\n  ['new tenant starts full',\n   {'global_cap': 10,\n    'global_rate': 2,\n    'requests': [[5, 'x', 3], [5, 'y', 2], [10, 'z', 3]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],\n  ['global capacity bound',\n   {'global_cap': 6,\n    'global_rate': 3,\n    'requests': [[0, 'a', 2],\n                 [0, 'b', 2],\n                 [0, 'c', 2],\n                 [10, 'a', 2],\n                 [10, 'b', 2],\n                 [10, 'c', 2],\n                 [14, 'd', 1]],\n    'tenant_cap': 2,\n    'tenant_rate': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],\n    5,\n    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],\n  ['random tenants',\n   {'global_cap': 5,\n    'global_rate': 2,\n    'requests': [[0, 'a', 3],\n                 [1, 'a', 3],\n                 [1, 'b', 3],\n                 [1, 'c', 2],\n                 [2, 'c', 2],\n                 [3, 'a', 2],\n                 [5, 'b', 2],\n                 [6, 'b', 3],\n                 [7, 'c', 1],\n                 [8, 'a', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow',\n     'deny-tenant',\n     'allow',\n     'deny-global',\n     'allow',\n     'allow',\n     'allow',\n     'deny-tenant',\n     'allow',\n     'allow'],\n    4,\n    [['a', 2], ['b', 2], ['c', 2]]]]],\n [['global exhaustion',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'b', 2], [0, 'c', 2], [0, 'a', 1], [6, 'c', 1]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'deny-global', 'deny-global', 'allow'], 3, [['a', 1], ['b', 1], ['c', 2]]]],\n  ['partial global remains usable',\n   {'global_cap': 4,\n    'global_rate': 1,\n    'requests': [[0, 'a', 3], [0, 'b', 2], [0, 'c', 1], [5, 'd', 2]],\n    'tenant_cap': 5,\n    'tenant_rate': 1},\n   [['allow', 'deny-global', 'allow', 'allow'], 2, [['a', 2], ['b', 5], ['c', 4], ['d', 3]]]],\n  ['both short reports tenant',\n   {'global_cap': 2,\n    'global_rate': 1,\n    'requests': [[0, 'a', 2], [0, 'a', 1], [0, 'b', 1], [5, 'b', 2]],\n    'tenant_cap': 2,\n    'tenant_rate': 1},\n   [['allow', 'deny-tenant', 'deny-global', 'allow'], 0, [['a', 0], ['b', 0]]]],\n  ['tenant clock independent',\n   {'global_cap': 20,\n    'global_rate': 5,\n    'requests': [[0, 'a', 4], [3, 'b', 1], [4, 'a', 3], [10, 'a', 2]],\n    'tenant_cap': 4,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow', 'allow'], 18, [['a', 2], ['b', 3]]]],\n  ['new tenant starts full',\n   {'global_cap': 10,\n    'global_rate': 2,\n    'requests': [[5, 'x', 3], [5, 'y', 2], [11, 'z', 3]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow', 'allow', 'allow'], 7, [['x', 0], ['y', 1], ['z', 0]]]],\n  ['global capacity bound',\n   {'global_cap': 6,\n    'global_rate': 3,\n    'requests': [[0, 'a', 2],\n                 [0, 'b', 2],\n                 [0, 'c', 2],\n                 [10, 'a', 2],\n                 [10, 'b', 2],\n                 [10, 'c', 2],\n                 [15, 'd', 1]],\n    'tenant_cap': 2,\n    'tenant_rate': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow'],\n    5,\n    [['a', 0], ['b', 0], ['c', 0], ['d', 1]]]],\n  ['random tenants',\n   {'global_cap': 5,\n    'global_rate': 2,\n    'requests': [[0, 'c', 3],\n                 [3, 'c', 1],\n                 [3, 'c', 2],\n                 [4, 'a', 1],\n                 [7, 'a', 2],\n                 [7, 'b', 1],\n                 [7, 'b', 1],\n                 [7, 'b', 2],\n                 [7, 'c', 1],\n                 [7, 'c', 2]],\n    'tenant_cap': 3,\n    'tenant_rate': 1},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny-tenant',\n     'allow',\n     'deny-global'],\n    0,\n    [['a', 1], ['b', 1], ['c', 2]]]]]]\nfor label, args, expected in cases[N - 1]:\n    check(label, solve(args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-rate_limiter_algorithms-hierarchical-buckets-global-cap","generated_at":"2026-09-29T14:48:48.583254+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Multi-tenant APIs enforce per-tenant and shared limits together; charging or refilling the wrong level leaks capacity between tenants.","repair":"Clamp the global bucket with the global capacity.","root_cause":"Global refill is clamped with the tenant capacity.","sha256":"b8d9421c3d5bb012003353d5e221ff2af77f74c26137abd71775013ae2f49041","title":"Hierarchical tenant and global token buckets: global bucket capped at tenant capacity · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":39.352,"exit_code":1,"observations":[{"actual":[["allow","allow","deny-global","deny-global","allow"],1,[["a",1],["b",1],["c",2]]],"check":"global exhaustion","expected":[["allow","allow","deny-global","deny-global","allow"],1,[["a",1],["b",1],["c",2]]],"passed":true},{"actual":[["allow","deny-global","allow","deny-global"],1,[["a",2],["b",5],["c",4],["d",5]]],"check":"partial global remains usable","expected":[["allow","deny-global","allow","deny-global"],1,[["a",2],["b",5],["c",4],["d",5]]],"passed":true},{"actual":[["allow","deny-tenant","deny-global","deny-global"],1,[["a",0],["b",2]]],"check":"both short reports tenant","expected":[["allow","deny-tenant","deny-global","deny-global"],1,[["a",0],["b",2]]],"passed":true},{"actual":[["allow","allow","allow","allow"],40,[["a",1],["b",3]]],"check":"tenant clock independent","expected":[["allow","allow","allow","allow"],18,[["a",1],["b",3]]],"passed":false},{"actual":[["allow","allow","allow"],16,[["x",0],["y",1],["z",0]]],"check":"new tenant starts full","expected":[["allow","allow","allow"],6,[["x",0],["y",1],["z",0]]],"passed":false},{"actual":[["allow","allow","allow","allow","allow","allow","allow"],26,[["a",0],["b",0],["c",0],["d",1]]],"check":"global capacity bound","expected":[["allow","allow","allow","allow","allow","allow","allow"],2,[["a",0],["b",0],["c",0],["d",1]]],"passed":false},{"actual":[["allow","deny-tenant","allow","allow","allow","allow","allow","allow","allow","allow"],3,[["a",1],["b",1],["c",0]]],"check":"random tenants","expected":[["allow","deny-tenant","allow","allow","allow","allow","allow","allow","allow","allow"],2,[["a",1],["b",1],["c",0]]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"global exhaustion\", \"actual\": [[\"allow\", \"allow\", \"deny-global\", \"deny-global\", \"allow\"], 1, [[\"a\", 1], [\"b\", 1], [\"c\", 2]]], \"expected\": [[\"allow\", \"allow\", \"deny-global\", \"deny-global\", \"allow\"], 1, [[\"a\", 1], [\"b\", 1], [\"c\", 2]]], \"passed\": true}, {\"check\": \"partial global remains usable\", \"actual\": [[\"allow\", \"deny-global\", \"allow\", \"deny-global\"], 1, [[\"a\", 2], [\"b\", 5], [\"c\", 4], [\"d\", 5]]], \"expected\": [[\"allow\", \"deny-global\", \"allow\", \"deny-global\"], 1, [[\"a\", 2], [\"b\", 5], [\"c\", 4], [\"d\", 5]]], \"passed\": true}, {\"check\": \"both short reports tenant\", \"actual\": [[\"allow\", \"deny-tenant\", \"deny-global\", \"deny-global\"], 1, [[\"a\", 0], [\"b\", 2]]], \"expected\": [[\"allow\", \"deny-tenant\", \"deny-global\", \"deny-global\"], 1, [[\"a\", 0], [\"b\", 2]]], \"passed\": true}, {\"check\": \"tenant clock independent\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\"], 40, [[\"a\", 1], [\"b\", 3]]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\"], 18, [[\"a\", 1], [\"b\", 3]]], \"passed\": false}, {\"check\": \"new tenant starts full\", \"actual\": [[\"allow\", \"allow\", \"allow\"], 16, [[\"x\", 0], [\"y\", 1], [\"z\", 0]]], \"expected\": [[\"allow\", \"allow\", \"allow\"], 6, [[\"x\", 0], [\"y\", 1], [\"z\", 0]]], \"passed\": false}, {\"check\": \"global capacity bound\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 26, [[\"a\", 0], [\"b\", 0], [\"c\", 0], [\"d\", 1]]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 2, [[\"a\", 0], [\"b\", 0], [\"c\", 0], [\"d\", 1]]], \"passed\": false}, {\"check\": \"random tenants\", \"actual\": [[\"allow\", \"deny-tenant\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 3, [[\"a\", 1], [\"b\", 1], [\"c\", 0]]], \"expected\": [[\"allow\", \"deny-tenant\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 2, [[\"a\", 1], [\"b\", 1], [\"c\", 0]]], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":40.151,"exit_code":1,"observations":[{"actual":[["allow","deny-global","deny-global","allow","allow"],1,[["a",0],["b",3],["c",2]]],"check":"global exhaustion","expected":[["allow","allow","deny-global","deny-global","allow"],1,[["a",1],["b",1],["c",2]]],"passed":false},{"actual":[["allow","deny-global","allow","deny-global"],1,[["a",2],["b",5],["c",4],["d",5]]],"check":"partial global remains usable","expected":[["allow","deny-global","allow","deny-global"],1,[["a",2],["b",5],["c",4],["d",5]]],"passed":true},{"actual":[["allow","deny-tenant","deny-global","deny-global"],1,[["a",0],["b",2]]],"check":"both short reports tenant","expected":[["allow","deny-tenant","deny-global","deny-global"],1,[["a",0],["b",2]]],"passed":true},{"actual":[["allow","allow","allow","allow"],2,[["a",1],["b",3]]],"check":"tenant clock independent","expected":[["allow","allow","allow","allow"],18,[["a",1],["b",3]]],"passed":false},{"actual":[["allow","deny-global","allow"],0,[["x",0],["y",3],["z",0]]],"check":"new tenant starts full","expected":[["allow","allow","allow"],6,[["x",0],["y",1],["z",0]]],"passed":false},{"actual":[["allow","deny-global","deny-global","allow","deny-global","deny-global","allow"],1,[["a",0],["b",2],["c",2],["d",1]]],"check":"global capacity bound","expected":[["allow","allow","allow","allow","allow","allow","allow"],2,[["a",0],["b",0],["c",0],["d",1]]],"passed":false},{"actual":[["allow","deny-tenant","allow","allow","allow","allow","allow","deny-global","allow","allow"],1,[["a",1],["b",1],["c",0]]],"check":"random tenants","expected":[["allow","deny-tenant","allow","allow","allow","allow","allow","allow","allow","allow"],2,[["a",1],["b",1],["c",0]]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"global exhaustion\", \"actual\": [[\"allow\", \"deny-global\", \"deny-global\", \"allow\", \"allow\"], 1, [[\"a\", 0], [\"b\", 3], [\"c\", 2]]], \"expected\": [[\"allow\", \"allow\", \"deny-global\", \"deny-global\", \"allow\"], 1, [[\"a\", 1], [\"b\", 1], [\"c\", 2]]], \"passed\": false}, {\"check\": \"partial global remains usable\", \"actual\": [[\"allow\", \"deny-global\", \"allow\", \"deny-global\"], 1, [[\"a\", 2], [\"b\", 5], [\"c\", 4], [\"d\", 5]]], \"expected\": [[\"allow\", \"deny-global\", \"allow\", \"deny-global\"], 1, [[\"a\", 2], [\"b\", 5], [\"c\", 4], [\"d\", 5]]], \"passed\": true}, {\"check\": \"both short reports tenant\", \"actual\": [[\"allow\", \"deny-tenant\", \"deny-global\", \"deny-global\"], 1, [[\"a\", 0], [\"b\", 2]]], \"expected\": [[\"allow\", \"deny-tenant\", \"deny-global\", \"deny-global\"], 1, [[\"a\", 0], [\"b\", 2]]], \"passed\": true}, {\"check\": \"tenant clock independent\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\"], 2, [[\"a\", 1], [\"b\", 3]]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\"], 18, [[\"a\", 1], [\"b\", 3]]], \"passed\": false}, {\"check\": \"new tenant starts full\", \"actual\": [[\"allow\", \"deny-global\", \"allow\"], 0, [[\"x\", 0], [\"y\", 3], [\"z\", 0]]], \"expected\": [[\"allow\", \"allow\", \"allow\"], 6, [[\"x\", 0], [\"y\", 1], [\"z\", 0]]], \"passed\": false}, {\"check\": \"global capacity bound\", \"actual\": [[\"allow\", \"deny-global\", \"deny-global\", \"allow\", \"deny-global\", \"deny-global\", \"allow\"], 1, [[\"a\", 0], [\"b\", 2], [\"c\", 2], [\"d\", 1]]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 2, [[\"a\", 0], [\"b\", 0], [\"c\", 0], [\"d\", 1]]], \"passed\": false}, {\"check\": \"random tenants\", \"actual\": [[\"allow\", \"deny-tenant\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny-global\", \"allow\", \"allow\"], 1, [[\"a\", 1], [\"b\", 1], [\"c\", 0]]], \"expected\": [[\"allow\", \"deny-tenant\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 2, [[\"a\", 1], [\"b\", 1], [\"c\", 0]]], \"passed\": false}], \"passed\": false}\n"},"fixed":{"elapsed_ms":42.775,"exit_code":0,"observations":[{"actual":[["allow","allow","deny-global","deny-global","allow"],1,[["a",1],["b",1],["c",2]]],"check":"global exhaustion","expected":[["allow","allow","deny-global","deny-global","allow"],1,[["a",1],["b",1],["c",2]]],"passed":true},{"actual":[["allow","deny-global","allow","deny-global"],1,[["a",2],["b",5],["c",4],["d",5]]],"check":"partial global remains usable","expected":[["allow","deny-global","allow","deny-global"],1,[["a",2],["b",5],["c",4],["d",5]]],"passed":true},{"actual":[["allow","deny-tenant","deny-global","deny-global"],1,[["a",0],["b",2]]],"check":"both short reports tenant","expected":[["allow","deny-tenant","deny-global","deny-global"],1,[["a",0],["b",2]]],"passed":true},{"actual":[["allow","allow","allow","allow"],18,[["a",1],["b",3]]],"check":"tenant clock independent","expected":[["allow","allow","allow","allow"],18,[["a",1],["b",3]]],"passed":true},{"actual":[["allow","allow","allow"],6,[["x",0],["y",1],["z",0]]],"check":"new tenant starts full","expected":[["allow","allow","allow"],6,[["x",0],["y",1],["z",0]]],"passed":true},{"actual":[["allow","allow","allow","allow","allow","allow","allow"],2,[["a",0],["b",0],["c",0],["d",1]]],"check":"global capacity bound","expected":[["allow","allow","allow","allow","allow","allow","allow"],2,[["a",0],["b",0],["c",0],["d",1]]],"passed":true},{"actual":[["allow","deny-tenant","allow","allow","allow","allow","allow","allow","allow","allow"],2,[["a",1],["b",1],["c",0]]],"check":"random tenants","expected":[["allow","deny-tenant","allow","allow","allow","allow","allow","allow","allow","allow"],2,[["a",1],["b",1],["c",0]]],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"global exhaustion\", \"actual\": [[\"allow\", \"allow\", \"deny-global\", \"deny-global\", \"allow\"], 1, [[\"a\", 1], [\"b\", 1], [\"c\", 2]]], \"expected\": [[\"allow\", \"allow\", \"deny-global\", \"deny-global\", \"allow\"], 1, [[\"a\", 1], [\"b\", 1], [\"c\", 2]]], \"passed\": true}, {\"check\": \"partial global remains usable\", \"actual\": [[\"allow\", \"deny-global\", \"allow\", \"deny-global\"], 1, [[\"a\", 2], [\"b\", 5], [\"c\", 4], [\"d\", 5]]], \"expected\": [[\"allow\", \"deny-global\", \"allow\", \"deny-global\"], 1, [[\"a\", 2], [\"b\", 5], [\"c\", 4], [\"d\", 5]]], \"passed\": true}, {\"check\": \"both short reports tenant\", \"actual\": [[\"allow\", \"deny-tenant\", \"deny-global\", \"deny-global\"], 1, [[\"a\", 0], [\"b\", 2]]], \"expected\": [[\"allow\", \"deny-tenant\", \"deny-global\", \"deny-global\"], 1, [[\"a\", 0], [\"b\", 2]]], \"passed\": true}, {\"check\": \"tenant clock independent\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\"], 18, [[\"a\", 1], [\"b\", 3]]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\"], 18, [[\"a\", 1], [\"b\", 3]]], \"passed\": true}, {\"check\": \"new tenant starts full\", \"actual\": [[\"allow\", \"allow\", \"allow\"], 6, [[\"x\", 0], [\"y\", 1], [\"z\", 0]]], \"expected\": [[\"allow\", \"allow\", \"allow\"], 6, [[\"x\", 0], [\"y\", 1], [\"z\", 0]]], \"passed\": true}, {\"check\": \"global capacity bound\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 2, [[\"a\", 0], [\"b\", 0], [\"c\", 0], [\"d\", 1]]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 2, [[\"a\", 0], [\"b\", 0], [\"c\", 0], [\"d\", 1]]], \"passed\": true}, {\"check\": \"random tenants\", \"actual\": [[\"allow\", \"deny-tenant\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 2, [[\"a\", 1], [\"b\", 1], [\"c\", 0]]], \"expected\": [[\"allow\", \"deny-tenant\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 2, [[\"a\", 1], [\"b\", 1], [\"c\", 0]]], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}