{"abstract":"The fleet collectively admits more than the global quota.","category":"Rate limiter algorithms","checks":6,"contract":"Input {quota, window_s, chunk, events [[t, node, \"req\"|\"return\"]]} with nondecreasing t. Each epoch window starts with the full global quota and voids all node leases. A node with an empty lease fetches min(chunk, remaining) from the coordinator; each request spends one leased unit or is denied when none is available. \"return\" credits the node's unused lease back and reports the new remaining. Return [results, remaining, sorted [node, lease]].","evaluation_group":"w2-rate_limiter_algorithms-quota-leasing","failed_approach":"All-or-nothing grants strand the final partial chunk.","family":"w2-rate_limiter_algorithms-quota-leasing-grant-clamp","id":"FA-73696","implementations":{"attempt":{"sha256":"5c53985e34daadd57cc1c801eb96d31ab8506d9300a804c69e7068813c1b4127","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    Q = x['quota']\n    W = x['window_s']\n    L = x['chunk']\n    win = None\n    remaining = 0\n    local = {}\n    out = []\n    for t, node, op in x['events']:\n        w = t // W\n        if w != win:\n            win, remaining, local = w, Q, {}\n        if op == 'return':\n            remaining += local.pop(node, 0)\n            out.append(remaining)\n            continue\n        if local.get(node, 0) == 0:\n            grant = L if remaining >= L else 0\n            remaining -= grant\n            local[node] = grant\n        if local[node] > 0:\n            local[node] -= 1\n            out.append('allow')\n        else:\n            out.append('deny')\n    return [out, remaining, sorted([k, v] for k, v in local.items())]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['partial last chunk',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [3, 'c', 'req']],\n    'quota': 7,\n    'window_s': 60},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],\n    0,\n    [['a', 2], ['b', 0], ['c', 0]]]],\n  ['return credits leftover',\n   {'chunk': 4,\n    'events': [[0, 'a', 'req'],\n               [1, 'a', 'return'],\n               [2, 'b', 'req'],\n               [3, 'b', 'req'],\n               [5, 'c', 'req']],\n    'quota': 6,\n    'window_s': 60},\n   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],\n  ['window rollover voids leases',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [3, 'b', 'req'],\n               [11, 'a', 'req'],\n               [12, 'a', 'req'],\n               [14, 'a', 'req']],\n    'quota': 4,\n    'window_s': 10},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],\n  ['exhausted lease refetches',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [2, 'a', 'return']],\n    'quota': 10,\n    'window_s': 100},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],\n  ['global exhaustion',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [4, 'a', 'req']],\n    'quota': 3,\n    'window_s': 100},\n   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],\n  ['random nodes',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [5, 'a', 'req'],\n               [6, 'b', 'req'],\n               [10, 'a', 'return'],\n               [14, 'a', 'return'],\n               [20, 'b', 'req'],\n               [23, 'b', 'req'],\n               [24, 'b', 'req'],\n               [24, 'b', 'return'],\n               [25, 'a', 'req'],\n               [25, 'b', 'req'],\n               [31, 'b', 'return'],\n               [38, 'a', 'req'],\n               [38, 'b', 'req']],\n    'quota': 8,\n    'window_s': 30},\n   [['allow',\n     'allow',\n     'allow',\n     3,\n     3,\n     'allow',\n     'allow',\n     'allow',\n     2,\n     'allow',\n     'deny',\n     8,\n     'allow',\n     'allow'],\n    2,\n    [['a', 2], ['b', 2]]]]],\n [['partial last chunk',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [4, 'c', 'req']],\n    'quota': 7,\n    'window_s': 60},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],\n    0,\n    [['a', 2], ['b', 0], ['c', 0]]]],\n  ['return credits leftover',\n   {'chunk': 4,\n    'events': [[0, 'a', 'req'],\n               [1, 'a', 'return'],\n               [2, 'b', 'req'],\n               [3, 'b', 'req'],\n               [6, 'c', 'req']],\n    'quota': 6,\n    'window_s': 60},\n   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],\n  ['window rollover voids leases',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [3, 'b', 'req'],\n               [11, 'a', 'req'],\n               [12, 'a', 'req'],\n               [15, 'a', 'req']],\n    'quota': 4,\n    'window_s': 10},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],\n  ['exhausted lease refetches',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [3, 'a', 'return']],\n    'quota': 10,\n    'window_s': 100},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],\n  ['global exhaustion',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [5, 'a', 'req']],\n    'quota': 3,\n    'window_s': 100},\n   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],\n  ['random nodes',\n   {'chunk': 3,\n    'events': [[1, 'a', 'req'],\n               [13, 'a', 'req'],\n               [15, 'b', 'req'],\n               [22, 'a', 'req'],\n               [25, 'a', 'req'],\n               [25, 'a', 'return'],\n               [26, 'b', 'req'],\n               [26, 'b', 'return'],\n               [29, 'b', 'req'],\n               [39, 'b', 'req'],\n               [44, 'a', 'req'],\n               [48, 'a', 'req'],\n               [48, 'a', 'return'],\n               [49, 'b', 'req']],\n    'quota': 8,\n    'window_s': 30},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     1,\n     'allow',\n     2,\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     3,\n     'allow'],\n    3,\n    [['b', 1]]]]],\n [['partial last chunk',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [5, 'c', 'req']],\n    'quota': 7,\n    'window_s': 60},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],\n    0,\n    [['a', 2], ['b', 0], ['c', 0]]]],\n  ['return credits leftover',\n   {'chunk': 4,\n    'events': [[0, 'a', 'req'],\n               [1, 'a', 'return'],\n               [2, 'b', 'req'],\n               [3, 'b', 'req'],\n               [7, 'c', 'req']],\n    'quota': 6,\n    'window_s': 60},\n   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],\n  ['window rollover voids leases',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [3, 'b', 'req'],\n               [11, 'a', 'req'],\n               [12, 'a', 'req'],\n               [16, 'a', 'req']],\n    'quota': 4,\n    'window_s': 10},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],\n  ['exhausted lease refetches',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [4, 'a', 'return']],\n    'quota': 10,\n    'window_s': 100},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],\n  ['global exhaustion',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [6, 'a', 'req']],\n    'quota': 3,\n    'window_s': 100},\n   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],\n  ['random nodes',\n   {'chunk': 3,\n    'events': [[0, 'a', 'return'],\n               [9, 'a', 'req'],\n               [9, 'a', 'return'],\n               [16, 'a', 'req'],\n               [22, 'a', 'req'],\n               [24, 'a', 'req'],\n               [32, 'b', 'req'],\n               [34, 'a', 'req'],\n               [35, 'b', 'return'],\n               [36, 'b', 'req'],\n               [40, 'a', 'req'],\n               [44, 'a', 'return'],\n               [45, 'b', 'req'],\n               [48, 'a', 'req']],\n    'quota': 8,\n    'window_s': 30},\n   [[8,\n     'allow',\n     7,\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     4,\n     'allow',\n     'allow',\n     2,\n     'allow',\n     'allow'],\n    0,\n    [['a', 1], ['b', 1]]]]],\n [['partial last chunk',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [6, 'c', 'req']],\n    'quota': 7,\n    'window_s': 60},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],\n    0,\n    [['a', 2], ['b', 0], ['c', 0]]]],\n  ['return credits leftover',\n   {'chunk': 4,\n    'events': [[0, 'a', 'req'],\n               [1, 'a', 'return'],\n               [2, 'b', 'req'],\n               [3, 'b', 'req'],\n               [8, 'c', 'req']],\n    'quota': 6,\n    'window_s': 60},\n   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],\n  ['window rollover voids leases',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [3, 'b', 'req'],\n               [11, 'a', 'req'],\n               [12, 'a', 'req'],\n               [17, 'a', 'req']],\n    'quota': 4,\n    'window_s': 10},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],\n  ['exhausted lease refetches',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [5, 'a', 'return']],\n    'quota': 10,\n    'window_s': 100},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],\n  ['global exhaustion',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [7, 'a', 'req']],\n    'quota': 3,\n    'window_s': 100},\n   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],\n  ['random nodes',\n   {'chunk': 3,\n    'events': [[4, 'b', 'req'],\n               [8, 'a', 'req'],\n               [17, 'b', 'req'],\n               [20, 'b', 'req'],\n               [26, 'a', 'return'],\n               [28, 'b', 'req'],\n               [32, 'b', 'req'],\n               [36, 'a', 'req'],\n               [38, 'b', 'req'],\n               [40, 'a', 'req'],\n               [41, 'a', 'req'],\n               [42, 'a', 'req'],\n               [42, 'a', 'return'],\n               [43, 'a', 'req']],\n    'quota': 8,\n    'window_s': 30},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     4,\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     1,\n     'allow'],\n    0,\n    [['a', 0], ['b', 1]]]]],\n [['partial last chunk',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [7, 'c', 'req']],\n    'quota': 7,\n    'window_s': 60},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],\n    0,\n    [['a', 2], ['b', 0], ['c', 0]]]],\n  ['return credits leftover',\n   {'chunk': 4,\n    'events': [[0, 'a', 'req'],\n               [1, 'a', 'return'],\n               [2, 'b', 'req'],\n               [3, 'b', 'req'],\n               [9, 'c', 'req']],\n    'quota': 6,\n    'window_s': 60},\n   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],\n  ['window rollover voids leases',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [3, 'b', 'req'],\n               [11, 'a', 'req'],\n               [12, 'a', 'req'],\n               [18, 'a', 'req']],\n    'quota': 4,\n    'window_s': 10},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],\n  ['exhausted lease refetches',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [6, 'a', 'return']],\n    'quota': 10,\n    'window_s': 100},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],\n  ['global exhaustion',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [8, 'a', 'req']],\n    'quota': 3,\n    'window_s': 100},\n   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],\n  ['random nodes',\n   {'chunk': 3,\n    'events': [[8, 'b', 'return'],\n               [10, 'b', 'req'],\n               [11, 'a', 'req'],\n               [11, 'a', 'return'],\n               [14, 'b', 'req'],\n               [25, 'a', 'req'],\n               [26, 'b', 'req'],\n               [35, 'a', 'req'],\n               [35, 'a', 'return'],\n               [39, 'a', 'req'],\n               [40, 'a', 'req'],\n               [43, 'b', 'req'],\n               [44, 'b', 'return'],\n               [47, 'a', 'return']],\n    'quota': 8,\n    'window_s': 30},\n   [[8,\n     'allow',\n     'allow',\n     4,\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     7,\n     'allow',\n     'allow',\n     'allow',\n     3,\n     4],\n    4,\n    []]]]]\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":"2b25906ae978458f34333be909a29d332ebe7f77285d6c4b4dee3a285b93dd8b","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    Q = x['quota']\n    W = x['window_s']\n    L = x['chunk']\n    win = None\n    remaining = 0\n    local = {}\n    out = []\n    for t, node, op in x['events']:\n        w = t // W\n        if w != win:\n            win, remaining, local = w, Q, {}\n        if op == 'return':\n            remaining += local.pop(node, 0)\n            out.append(remaining)\n            continue\n        if local.get(node, 0) == 0:\n            grant = L\n            remaining -= grant\n            local[node] = grant\n        if local[node] > 0:\n            local[node] -= 1\n            out.append('allow')\n        else:\n            out.append('deny')\n    return [out, remaining, sorted([k, v] for k, v in local.items())]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['partial last chunk',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [3, 'c', 'req']],\n    'quota': 7,\n    'window_s': 60},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],\n    0,\n    [['a', 2], ['b', 0], ['c', 0]]]],\n  ['return credits leftover',\n   {'chunk': 4,\n    'events': [[0, 'a', 'req'],\n               [1, 'a', 'return'],\n               [2, 'b', 'req'],\n               [3, 'b', 'req'],\n               [5, 'c', 'req']],\n    'quota': 6,\n    'window_s': 60},\n   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],\n  ['window rollover voids leases',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [3, 'b', 'req'],\n               [11, 'a', 'req'],\n               [12, 'a', 'req'],\n               [14, 'a', 'req']],\n    'quota': 4,\n    'window_s': 10},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],\n  ['exhausted lease refetches',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [2, 'a', 'return']],\n    'quota': 10,\n    'window_s': 100},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],\n  ['global exhaustion',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [4, 'a', 'req']],\n    'quota': 3,\n    'window_s': 100},\n   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],\n  ['random nodes',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [5, 'a', 'req'],\n               [6, 'b', 'req'],\n               [10, 'a', 'return'],\n               [14, 'a', 'return'],\n               [20, 'b', 'req'],\n               [23, 'b', 'req'],\n               [24, 'b', 'req'],\n               [24, 'b', 'return'],\n               [25, 'a', 'req'],\n               [25, 'b', 'req'],\n               [31, 'b', 'return'],\n               [38, 'a', 'req'],\n               [38, 'b', 'req']],\n    'quota': 8,\n    'window_s': 30},\n   [['allow',\n     'allow',\n     'allow',\n     3,\n     3,\n     'allow',\n     'allow',\n     'allow',\n     2,\n     'allow',\n     'deny',\n     8,\n     'allow',\n     'allow'],\n    2,\n    [['a', 2], ['b', 2]]]]],\n [['partial last chunk',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [4, 'c', 'req']],\n    'quota': 7,\n    'window_s': 60},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],\n    0,\n    [['a', 2], ['b', 0], ['c', 0]]]],\n  ['return credits leftover',\n   {'chunk': 4,\n    'events': [[0, 'a', 'req'],\n               [1, 'a', 'return'],\n               [2, 'b', 'req'],\n               [3, 'b', 'req'],\n               [6, 'c', 'req']],\n    'quota': 6,\n    'window_s': 60},\n   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],\n  ['window rollover voids leases',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [3, 'b', 'req'],\n               [11, 'a', 'req'],\n               [12, 'a', 'req'],\n               [15, 'a', 'req']],\n    'quota': 4,\n    'window_s': 10},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],\n  ['exhausted lease refetches',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [3, 'a', 'return']],\n    'quota': 10,\n    'window_s': 100},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],\n  ['global exhaustion',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [5, 'a', 'req']],\n    'quota': 3,\n    'window_s': 100},\n   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],\n  ['random nodes',\n   {'chunk': 3,\n    'events': [[1, 'a', 'req'],\n               [13, 'a', 'req'],\n               [15, 'b', 'req'],\n               [22, 'a', 'req'],\n               [25, 'a', 'req'],\n               [25, 'a', 'return'],\n               [26, 'b', 'req'],\n               [26, 'b', 'return'],\n               [29, 'b', 'req'],\n               [39, 'b', 'req'],\n               [44, 'a', 'req'],\n               [48, 'a', 'req'],\n               [48, 'a', 'return'],\n               [49, 'b', 'req']],\n    'quota': 8,\n    'window_s': 30},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     1,\n     'allow',\n     2,\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     3,\n     'allow'],\n    3,\n    [['b', 1]]]]],\n [['partial last chunk',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [5, 'c', 'req']],\n    'quota': 7,\n    'window_s': 60},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],\n    0,\n    [['a', 2], ['b', 0], ['c', 0]]]],\n  ['return credits leftover',\n   {'chunk': 4,\n    'events': [[0, 'a', 'req'],\n               [1, 'a', 'return'],\n               [2, 'b', 'req'],\n               [3, 'b', 'req'],\n               [7, 'c', 'req']],\n    'quota': 6,\n    'window_s': 60},\n   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],\n  ['window rollover voids leases',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [3, 'b', 'req'],\n               [11, 'a', 'req'],\n               [12, 'a', 'req'],\n               [16, 'a', 'req']],\n    'quota': 4,\n    'window_s': 10},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],\n  ['exhausted lease refetches',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [4, 'a', 'return']],\n    'quota': 10,\n    'window_s': 100},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],\n  ['global exhaustion',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [6, 'a', 'req']],\n    'quota': 3,\n    'window_s': 100},\n   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],\n  ['random nodes',\n   {'chunk': 3,\n    'events': [[0, 'a', 'return'],\n               [9, 'a', 'req'],\n               [9, 'a', 'return'],\n               [16, 'a', 'req'],\n               [22, 'a', 'req'],\n               [24, 'a', 'req'],\n               [32, 'b', 'req'],\n               [34, 'a', 'req'],\n               [35, 'b', 'return'],\n               [36, 'b', 'req'],\n               [40, 'a', 'req'],\n               [44, 'a', 'return'],\n               [45, 'b', 'req'],\n               [48, 'a', 'req']],\n    'quota': 8,\n    'window_s': 30},\n   [[8,\n     'allow',\n     7,\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     4,\n     'allow',\n     'allow',\n     2,\n     'allow',\n     'allow'],\n    0,\n    [['a', 1], ['b', 1]]]]],\n [['partial last chunk',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [6, 'c', 'req']],\n    'quota': 7,\n    'window_s': 60},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],\n    0,\n    [['a', 2], ['b', 0], ['c', 0]]]],\n  ['return credits leftover',\n   {'chunk': 4,\n    'events': [[0, 'a', 'req'],\n               [1, 'a', 'return'],\n               [2, 'b', 'req'],\n               [3, 'b', 'req'],\n               [8, 'c', 'req']],\n    'quota': 6,\n    'window_s': 60},\n   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],\n  ['window rollover voids leases',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [3, 'b', 'req'],\n               [11, 'a', 'req'],\n               [12, 'a', 'req'],\n               [17, 'a', 'req']],\n    'quota': 4,\n    'window_s': 10},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],\n  ['exhausted lease refetches',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [5, 'a', 'return']],\n    'quota': 10,\n    'window_s': 100},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],\n  ['global exhaustion',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [7, 'a', 'req']],\n    'quota': 3,\n    'window_s': 100},\n   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],\n  ['random nodes',\n   {'chunk': 3,\n    'events': [[4, 'b', 'req'],\n               [8, 'a', 'req'],\n               [17, 'b', 'req'],\n               [20, 'b', 'req'],\n               [26, 'a', 'return'],\n               [28, 'b', 'req'],\n               [32, 'b', 'req'],\n               [36, 'a', 'req'],\n               [38, 'b', 'req'],\n               [40, 'a', 'req'],\n               [41, 'a', 'req'],\n               [42, 'a', 'req'],\n               [42, 'a', 'return'],\n               [43, 'a', 'req']],\n    'quota': 8,\n    'window_s': 30},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     4,\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     1,\n     'allow'],\n    0,\n    [['a', 0], ['b', 1]]]]],\n [['partial last chunk',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [7, 'c', 'req']],\n    'quota': 7,\n    'window_s': 60},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],\n    0,\n    [['a', 2], ['b', 0], ['c', 0]]]],\n  ['return credits leftover',\n   {'chunk': 4,\n    'events': [[0, 'a', 'req'],\n               [1, 'a', 'return'],\n               [2, 'b', 'req'],\n               [3, 'b', 'req'],\n               [9, 'c', 'req']],\n    'quota': 6,\n    'window_s': 60},\n   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],\n  ['window rollover voids leases',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [3, 'b', 'req'],\n               [11, 'a', 'req'],\n               [12, 'a', 'req'],\n               [18, 'a', 'req']],\n    'quota': 4,\n    'window_s': 10},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],\n  ['exhausted lease refetches',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [6, 'a', 'return']],\n    'quota': 10,\n    'window_s': 100},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],\n  ['global exhaustion',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [8, 'a', 'req']],\n    'quota': 3,\n    'window_s': 100},\n   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],\n  ['random nodes',\n   {'chunk': 3,\n    'events': [[8, 'b', 'return'],\n               [10, 'b', 'req'],\n               [11, 'a', 'req'],\n               [11, 'a', 'return'],\n               [14, 'b', 'req'],\n               [25, 'a', 'req'],\n               [26, 'b', 'req'],\n               [35, 'a', 'req'],\n               [35, 'a', 'return'],\n               [39, 'a', 'req'],\n               [40, 'a', 'req'],\n               [43, 'b', 'req'],\n               [44, 'b', 'return'],\n               [47, 'a', 'return']],\n    'quota': 8,\n    'window_s': 30},\n   [[8,\n     'allow',\n     'allow',\n     4,\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     7,\n     'allow',\n     'allow',\n     'allow',\n     3,\n     4],\n    4,\n    []]]]]\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":"7a242cde12e85329d71b51a99c4258b4a9d9e81ab4d883a0cec47012b8ba9ecd","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    Q = x['quota']\n    W = x['window_s']\n    L = x['chunk']\n    win = None\n    remaining = 0\n    local = {}\n    out = []\n    for t, node, op in x['events']:\n        w = t // W\n        if w != win:\n            win, remaining, local = w, Q, {}\n        if op == 'return':\n            remaining += local.pop(node, 0)\n            out.append(remaining)\n            continue\n        if local.get(node, 0) == 0:\n            grant = min(L, remaining)\n            remaining -= grant\n            local[node] = grant\n        if local[node] > 0:\n            local[node] -= 1\n            out.append('allow')\n        else:\n            out.append('deny')\n    return [out, remaining, sorted([k, v] for k, v in local.items())]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['partial last chunk',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [3, 'c', 'req']],\n    'quota': 7,\n    'window_s': 60},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],\n    0,\n    [['a', 2], ['b', 0], ['c', 0]]]],\n  ['return credits leftover',\n   {'chunk': 4,\n    'events': [[0, 'a', 'req'],\n               [1, 'a', 'return'],\n               [2, 'b', 'req'],\n               [3, 'b', 'req'],\n               [5, 'c', 'req']],\n    'quota': 6,\n    'window_s': 60},\n   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],\n  ['window rollover voids leases',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [3, 'b', 'req'],\n               [11, 'a', 'req'],\n               [12, 'a', 'req'],\n               [14, 'a', 'req']],\n    'quota': 4,\n    'window_s': 10},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],\n  ['exhausted lease refetches',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [2, 'a', 'return']],\n    'quota': 10,\n    'window_s': 100},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],\n  ['global exhaustion',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [4, 'a', 'req']],\n    'quota': 3,\n    'window_s': 100},\n   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],\n  ['random nodes',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [5, 'a', 'req'],\n               [6, 'b', 'req'],\n               [10, 'a', 'return'],\n               [14, 'a', 'return'],\n               [20, 'b', 'req'],\n               [23, 'b', 'req'],\n               [24, 'b', 'req'],\n               [24, 'b', 'return'],\n               [25, 'a', 'req'],\n               [25, 'b', 'req'],\n               [31, 'b', 'return'],\n               [38, 'a', 'req'],\n               [38, 'b', 'req']],\n    'quota': 8,\n    'window_s': 30},\n   [['allow',\n     'allow',\n     'allow',\n     3,\n     3,\n     'allow',\n     'allow',\n     'allow',\n     2,\n     'allow',\n     'deny',\n     8,\n     'allow',\n     'allow'],\n    2,\n    [['a', 2], ['b', 2]]]]],\n [['partial last chunk',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [4, 'c', 'req']],\n    'quota': 7,\n    'window_s': 60},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],\n    0,\n    [['a', 2], ['b', 0], ['c', 0]]]],\n  ['return credits leftover',\n   {'chunk': 4,\n    'events': [[0, 'a', 'req'],\n               [1, 'a', 'return'],\n               [2, 'b', 'req'],\n               [3, 'b', 'req'],\n               [6, 'c', 'req']],\n    'quota': 6,\n    'window_s': 60},\n   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],\n  ['window rollover voids leases',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [3, 'b', 'req'],\n               [11, 'a', 'req'],\n               [12, 'a', 'req'],\n               [15, 'a', 'req']],\n    'quota': 4,\n    'window_s': 10},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],\n  ['exhausted lease refetches',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [3, 'a', 'return']],\n    'quota': 10,\n    'window_s': 100},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],\n  ['global exhaustion',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [5, 'a', 'req']],\n    'quota': 3,\n    'window_s': 100},\n   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],\n  ['random nodes',\n   {'chunk': 3,\n    'events': [[1, 'a', 'req'],\n               [13, 'a', 'req'],\n               [15, 'b', 'req'],\n               [22, 'a', 'req'],\n               [25, 'a', 'req'],\n               [25, 'a', 'return'],\n               [26, 'b', 'req'],\n               [26, 'b', 'return'],\n               [29, 'b', 'req'],\n               [39, 'b', 'req'],\n               [44, 'a', 'req'],\n               [48, 'a', 'req'],\n               [48, 'a', 'return'],\n               [49, 'b', 'req']],\n    'quota': 8,\n    'window_s': 30},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     1,\n     'allow',\n     2,\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     3,\n     'allow'],\n    3,\n    [['b', 1]]]]],\n [['partial last chunk',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [5, 'c', 'req']],\n    'quota': 7,\n    'window_s': 60},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],\n    0,\n    [['a', 2], ['b', 0], ['c', 0]]]],\n  ['return credits leftover',\n   {'chunk': 4,\n    'events': [[0, 'a', 'req'],\n               [1, 'a', 'return'],\n               [2, 'b', 'req'],\n               [3, 'b', 'req'],\n               [7, 'c', 'req']],\n    'quota': 6,\n    'window_s': 60},\n   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],\n  ['window rollover voids leases',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [3, 'b', 'req'],\n               [11, 'a', 'req'],\n               [12, 'a', 'req'],\n               [16, 'a', 'req']],\n    'quota': 4,\n    'window_s': 10},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],\n  ['exhausted lease refetches',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [4, 'a', 'return']],\n    'quota': 10,\n    'window_s': 100},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],\n  ['global exhaustion',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [6, 'a', 'req']],\n    'quota': 3,\n    'window_s': 100},\n   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],\n  ['random nodes',\n   {'chunk': 3,\n    'events': [[0, 'a', 'return'],\n               [9, 'a', 'req'],\n               [9, 'a', 'return'],\n               [16, 'a', 'req'],\n               [22, 'a', 'req'],\n               [24, 'a', 'req'],\n               [32, 'b', 'req'],\n               [34, 'a', 'req'],\n               [35, 'b', 'return'],\n               [36, 'b', 'req'],\n               [40, 'a', 'req'],\n               [44, 'a', 'return'],\n               [45, 'b', 'req'],\n               [48, 'a', 'req']],\n    'quota': 8,\n    'window_s': 30},\n   [[8,\n     'allow',\n     7,\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     4,\n     'allow',\n     'allow',\n     2,\n     'allow',\n     'allow'],\n    0,\n    [['a', 1], ['b', 1]]]]],\n [['partial last chunk',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [6, 'c', 'req']],\n    'quota': 7,\n    'window_s': 60},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],\n    0,\n    [['a', 2], ['b', 0], ['c', 0]]]],\n  ['return credits leftover',\n   {'chunk': 4,\n    'events': [[0, 'a', 'req'],\n               [1, 'a', 'return'],\n               [2, 'b', 'req'],\n               [3, 'b', 'req'],\n               [8, 'c', 'req']],\n    'quota': 6,\n    'window_s': 60},\n   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],\n  ['window rollover voids leases',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [3, 'b', 'req'],\n               [11, 'a', 'req'],\n               [12, 'a', 'req'],\n               [17, 'a', 'req']],\n    'quota': 4,\n    'window_s': 10},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],\n  ['exhausted lease refetches',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [5, 'a', 'return']],\n    'quota': 10,\n    'window_s': 100},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],\n  ['global exhaustion',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [7, 'a', 'req']],\n    'quota': 3,\n    'window_s': 100},\n   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],\n  ['random nodes',\n   {'chunk': 3,\n    'events': [[4, 'b', 'req'],\n               [8, 'a', 'req'],\n               [17, 'b', 'req'],\n               [20, 'b', 'req'],\n               [26, 'a', 'return'],\n               [28, 'b', 'req'],\n               [32, 'b', 'req'],\n               [36, 'a', 'req'],\n               [38, 'b', 'req'],\n               [40, 'a', 'req'],\n               [41, 'a', 'req'],\n               [42, 'a', 'req'],\n               [42, 'a', 'return'],\n               [43, 'a', 'req']],\n    'quota': 8,\n    'window_s': 30},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     4,\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     1,\n     'allow'],\n    0,\n    [['a', 0], ['b', 1]]]]],\n [['partial last chunk',\n   {'chunk': 3,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [1, 'b', 'req'],\n               [7, 'c', 'req']],\n    'quota': 7,\n    'window_s': 60},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'deny'],\n    0,\n    [['a', 2], ['b', 0], ['c', 0]]]],\n  ['return credits leftover',\n   {'chunk': 4,\n    'events': [[0, 'a', 'req'],\n               [1, 'a', 'return'],\n               [2, 'b', 'req'],\n               [3, 'b', 'req'],\n               [9, 'c', 'req']],\n    'quota': 6,\n    'window_s': 60},\n   [['allow', 5, 'allow', 'allow', 'allow'], 0, [['b', 2], ['c', 0]]]],\n  ['window rollover voids leases',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [3, 'b', 'req'],\n               [11, 'a', 'req'],\n               [12, 'a', 'req'],\n               [18, 'a', 'req']],\n    'quota': 4,\n    'window_s': 10},\n   [['allow', 'allow', 'allow', 'allow', 'allow'], 0, [['a', 1]]]],\n  ['exhausted lease refetches',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [0, 'a', 'req'],\n               [6, 'a', 'return']],\n    'quota': 10,\n    'window_s': 100},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 5], 5, []]],\n  ['global exhaustion',\n   {'chunk': 2,\n    'events': [[0, 'a', 'req'], [0, 'b', 'req'], [1, 'b', 'req'], [2, 'c', 'req'], [8, 'a', 'req']],\n    'quota': 3,\n    'window_s': 100},\n   [['allow', 'allow', 'deny', 'deny', 'allow'], 0, [['a', 0], ['b', 0], ['c', 0]]]],\n  ['random nodes',\n   {'chunk': 3,\n    'events': [[8, 'b', 'return'],\n               [10, 'b', 'req'],\n               [11, 'a', 'req'],\n               [11, 'a', 'return'],\n               [14, 'b', 'req'],\n               [25, 'a', 'req'],\n               [26, 'b', 'req'],\n               [35, 'a', 'req'],\n               [35, 'a', 'return'],\n               [39, 'a', 'req'],\n               [40, 'a', 'req'],\n               [43, 'b', 'req'],\n               [44, 'b', 'return'],\n               [47, 'a', 'return']],\n    'quota': 8,\n    'window_s': 30},\n   [[8,\n     'allow',\n     'allow',\n     4,\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     7,\n     'allow',\n     'allow',\n     'allow',\n     3,\n     4],\n    4,\n    []]]]]\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-quota-leasing-grant-clamp","generated_at":"2026-09-29T14:48:49.990656+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Large-scale limiters hand out quota in chunks to avoid a coordinator round trip per request; lease accounting errors oversubscribe the global limit or strand quota.","repair":"Lease min(chunk, remaining).","root_cause":"A full chunk is leased even when less quota remains.","sha256":"0641a218021b75944691f28884ad22707088073f1b9e06b6c3fc65f87e167fef","title":"Distributed limiter with leased quota chunks: chunk granted beyond the remaining quota · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":40.985,"exit_code":1,"observations":[{"actual":[["allow","allow","allow","allow","deny","deny","deny","deny","deny"],1,[["a",2],["b",0],["c",0]]],"check":"partial last chunk","expected":[["allow","allow","allow","allow","allow","deny","deny","deny","deny"],0,[["a",2],["b",0],["c",0]]],"passed":false},{"actual":[["allow",5,"allow","allow","deny"],1,[["b",2],["c",0]]],"check":"return credits leftover","expected":[["allow",5,"allow","allow","allow"],0,[["b",2],["c",0]]],"passed":false},{"actual":[["allow","allow","allow","allow","allow"],0,[["a",1]]],"check":"window rollover voids leases","expected":[["allow","allow","allow","allow","allow"],0,[["a",1]]],"passed":true},{"actual":[["allow","allow","allow","allow","allow",5],5,[]],"check":"exhausted lease refetches","expected":[["allow","allow","allow","allow","allow",5],5,[]],"passed":true},{"actual":[["allow","deny","deny","deny","allow"],1,[["a",0],["b",0],["c",0]]],"check":"global exhaustion","expected":[["allow","allow","deny","deny","allow"],0,[["a",0],["b",0],["c",0]]],"passed":false},{"actual":[["allow","allow","allow",3,3,"allow","allow","allow",2,"deny","deny",8,"allow","allow"],2,[["a",2],["b",2]]],"check":"random nodes","expected":[["allow","allow","allow",3,3,"allow","allow","allow",2,"allow","deny",8,"allow","allow"],2,[["a",2],["b",2]]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"partial last chunk\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\", \"deny\", \"deny\"], 1, [[\"a\", 2], [\"b\", 0], [\"c\", 0]]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\", \"deny\"], 0, [[\"a\", 2], [\"b\", 0], [\"c\", 0]]], \"passed\": false}, {\"check\": \"return credits leftover\", \"actual\": [[\"allow\", 5, \"allow\", \"allow\", \"deny\"], 1, [[\"b\", 2], [\"c\", 0]]], \"expected\": [[\"allow\", 5, \"allow\", \"allow\", \"allow\"], 0, [[\"b\", 2], [\"c\", 0]]], \"passed\": false}, {\"check\": \"window rollover voids leases\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 0, [[\"a\", 1]]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 0, [[\"a\", 1]]], \"passed\": true}, {\"check\": \"exhausted lease refetches\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", 5], 5, []], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", 5], 5, []], \"passed\": true}, {\"check\": \"global exhaustion\", \"actual\": [[\"allow\", \"deny\", \"deny\", \"deny\", \"allow\"], 1, [[\"a\", 0], [\"b\", 0], [\"c\", 0]]], \"expected\": [[\"allow\", \"allow\", \"deny\", \"deny\", \"allow\"], 0, [[\"a\", 0], [\"b\", 0], [\"c\", 0]]], \"passed\": false}, {\"check\": \"random nodes\", \"actual\": [[\"allow\", \"allow\", \"allow\", 3, 3, \"allow\", \"allow\", \"allow\", 2, \"deny\", \"deny\", 8, \"allow\", \"allow\"], 2, [[\"a\", 2], [\"b\", 2]]], \"expected\": [[\"allow\", \"allow\", \"allow\", 3, 3, \"allow\", \"allow\", \"allow\", 2, \"allow\", \"deny\", 8, \"allow\", \"allow\"], 2, [[\"a\", 2], [\"b\", 2]]], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":40.39,"exit_code":1,"observations":[{"actual":[["allow","allow","allow","allow","allow","allow","allow","allow","allow"],-8,[["a",2],["b",2],["c",2]]],"check":"partial last chunk","expected":[["allow","allow","allow","allow","allow","deny","deny","deny","deny"],0,[["a",2],["b",0],["c",0]]],"passed":false},{"actual":[["allow",5,"allow","allow","allow"],-3,[["b",2],["c",3]]],"check":"return credits leftover","expected":[["allow",5,"allow","allow","allow"],0,[["b",2],["c",0]]],"passed":false},{"actual":[["allow","allow","allow","allow","allow"],0,[["a",1]]],"check":"window rollover voids leases","expected":[["allow","allow","allow","allow","allow"],0,[["a",1]]],"passed":true},{"actual":[["allow","allow","allow","allow","allow",5],5,[]],"check":"exhausted lease refetches","expected":[["allow","allow","allow","allow","allow",5],5,[]],"passed":true},{"actual":[["allow","allow","allow","allow","allow"],-3,[["a",0],["b",0],["c",1]]],"check":"global exhaustion","expected":[["allow","allow","deny","deny","allow"],0,[["a",0],["b",0],["c",0]]],"passed":false},{"actual":[["allow","allow","allow",3,3,"allow","allow","allow",2,"allow","allow",8,"allow","allow"],2,[["a",2],["b",2]]],"check":"random nodes","expected":[["allow","allow","allow",3,3,"allow","allow","allow",2,"allow","deny",8,"allow","allow"],2,[["a",2],["b",2]]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"partial last chunk\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], -8, [[\"a\", 2], [\"b\", 2], [\"c\", 2]]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\", \"deny\"], 0, [[\"a\", 2], [\"b\", 0], [\"c\", 0]]], \"passed\": false}, {\"check\": \"return credits leftover\", \"actual\": [[\"allow\", 5, \"allow\", \"allow\", \"allow\"], -3, [[\"b\", 2], [\"c\", 3]]], \"expected\": [[\"allow\", 5, \"allow\", \"allow\", \"allow\"], 0, [[\"b\", 2], [\"c\", 0]]], \"passed\": false}, {\"check\": \"window rollover voids leases\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 0, [[\"a\", 1]]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 0, [[\"a\", 1]]], \"passed\": true}, {\"check\": \"exhausted lease refetches\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", 5], 5, []], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", 5], 5, []], \"passed\": true}, {\"check\": \"global exhaustion\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], -3, [[\"a\", 0], [\"b\", 0], [\"c\", 1]]], \"expected\": [[\"allow\", \"allow\", \"deny\", \"deny\", \"allow\"], 0, [[\"a\", 0], [\"b\", 0], [\"c\", 0]]], \"passed\": false}, {\"check\": \"random nodes\", \"actual\": [[\"allow\", \"allow\", \"allow\", 3, 3, \"allow\", \"allow\", \"allow\", 2, \"allow\", \"allow\", 8, \"allow\", \"allow\"], 2, [[\"a\", 2], [\"b\", 2]]], \"expected\": [[\"allow\", \"allow\", \"allow\", 3, 3, \"allow\", \"allow\", \"allow\", 2, \"allow\", \"deny\", 8, \"allow\", \"allow\"], 2, [[\"a\", 2], [\"b\", 2]]], \"passed\": false}], \"passed\": false}\n"},"fixed":{"elapsed_ms":43.885,"exit_code":0,"observations":[{"actual":[["allow","allow","allow","allow","allow","deny","deny","deny","deny"],0,[["a",2],["b",0],["c",0]]],"check":"partial last chunk","expected":[["allow","allow","allow","allow","allow","deny","deny","deny","deny"],0,[["a",2],["b",0],["c",0]]],"passed":true},{"actual":[["allow",5,"allow","allow","allow"],0,[["b",2],["c",0]]],"check":"return credits leftover","expected":[["allow",5,"allow","allow","allow"],0,[["b",2],["c",0]]],"passed":true},{"actual":[["allow","allow","allow","allow","allow"],0,[["a",1]]],"check":"window rollover voids leases","expected":[["allow","allow","allow","allow","allow"],0,[["a",1]]],"passed":true},{"actual":[["allow","allow","allow","allow","allow",5],5,[]],"check":"exhausted lease refetches","expected":[["allow","allow","allow","allow","allow",5],5,[]],"passed":true},{"actual":[["allow","allow","deny","deny","allow"],0,[["a",0],["b",0],["c",0]]],"check":"global exhaustion","expected":[["allow","allow","deny","deny","allow"],0,[["a",0],["b",0],["c",0]]],"passed":true},{"actual":[["allow","allow","allow",3,3,"allow","allow","allow",2,"allow","deny",8,"allow","allow"],2,[["a",2],["b",2]]],"check":"random nodes","expected":[["allow","allow","allow",3,3,"allow","allow","allow",2,"allow","deny",8,"allow","allow"],2,[["a",2],["b",2]]],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"partial last chunk\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\", \"deny\"], 0, [[\"a\", 2], [\"b\", 0], [\"c\", 0]]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\", \"deny\"], 0, [[\"a\", 2], [\"b\", 0], [\"c\", 0]]], \"passed\": true}, {\"check\": \"return credits leftover\", \"actual\": [[\"allow\", 5, \"allow\", \"allow\", \"allow\"], 0, [[\"b\", 2], [\"c\", 0]]], \"expected\": [[\"allow\", 5, \"allow\", \"allow\", \"allow\"], 0, [[\"b\", 2], [\"c\", 0]]], \"passed\": true}, {\"check\": \"window rollover voids leases\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 0, [[\"a\", 1]]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 0, [[\"a\", 1]]], \"passed\": true}, {\"check\": \"exhausted lease refetches\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", 5], 5, []], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", 5], 5, []], \"passed\": true}, {\"check\": \"global exhaustion\", \"actual\": [[\"allow\", \"allow\", \"deny\", \"deny\", \"allow\"], 0, [[\"a\", 0], [\"b\", 0], [\"c\", 0]]], \"expected\": [[\"allow\", \"allow\", \"deny\", \"deny\", \"allow\"], 0, [[\"a\", 0], [\"b\", 0], [\"c\", 0]]], \"passed\": true}, {\"check\": \"random nodes\", \"actual\": [[\"allow\", \"allow\", \"allow\", 3, 3, \"allow\", \"allow\", \"allow\", 2, \"allow\", \"deny\", 8, \"allow\", \"allow\"], 2, [[\"a\", 2], [\"b\", 2]]], \"expected\": [[\"allow\", \"allow\", \"allow\", 3, 3, \"allow\", \"allow\", \"allow\", 2, \"allow\", \"deny\", 8, \"allow\", \"allow\"], 2, [[\"a\", 2], [\"b\", 2]]], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}