{"abstract":"A node that used up its first chunk denies everything for the rest of the window although quota remains.","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":"Refetching at one remaining unit overwrites and loses that unit.","family":"w2-rate_limiter_algorithms-quota-leasing-refetch-condition","id":"FA-73711","implementations":{"attempt":{"sha256":"4b37e2be3d1beb8eb503369b07409e2793c8f3aa9a66e3280ce29e3cea993143","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) <= 1:\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"},"broken":{"sha256":"cdcfa2b23d871394fbbfe3eab422956d1a74e5152af9f42c5cad20f881119a58","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 node not in local:\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"},"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-refetch-condition","generated_at":"2026-09-29T14:48:50.080661+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":"Fetch a new chunk whenever the node's lease is empty.","root_cause":"A lease is fetched only for nodes with no lease entry, not for nodes whose lease is exhausted.","sha256":"eda7f670b9e361d9e1a51de1ea8631df70970d8ccb87c710ca99301a01319abd","title":"Distributed limiter with leased quota chunks: exhausted lease never refetched · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":45.404,"exit_code":1,"observations":[{"actual":[["allow","allow","allow","allow","allow","deny","deny","deny","deny"],0,[["a",1],["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","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","deny"],0,[["a",0]]],"check":"window rollover voids leases","expected":[["allow","allow","allow","allow","allow"],0,[["a",1]]],"passed":false},{"actual":[["allow","allow","allow","allow","allow",1],1,[]],"check":"exhausted lease refetches","expected":[["allow","allow","allow","allow","allow",5],5,[]],"passed":false},{"actual":[["allow","allow","deny","deny","deny"],0,[["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",1,"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":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"partial last chunk\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\", \"deny\"], 0, [[\"a\", 1], [\"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\", \"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\", \"deny\"], 0, [[\"a\", 0]]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 0, [[\"a\", 1]]], \"passed\": false}, {\"check\": \"exhausted lease refetches\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", 1], 1, []], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", 5], 5, []], \"passed\": false}, {\"check\": \"global exhaustion\", \"actual\": [[\"allow\", \"allow\", \"deny\", \"deny\", \"deny\"], 0, [[\"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\", 1, \"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\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":42.665,"exit_code":1,"observations":[{"actual":[["allow","allow","allow","deny","allow","allow","allow","deny","allow"],0,[["a",0],["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","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","deny"],2,[["a",0]]],"check":"window rollover voids leases","expected":[["allow","allow","allow","allow","allow"],0,[["a",1]]],"passed":false},{"actual":[["allow","allow","deny","deny","deny",8],8,[]],"check":"exhausted lease refetches","expected":[["allow","allow","allow","allow","allow",5],5,[]],"passed":false},{"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","deny",3,"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":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"partial last chunk\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"deny\", \"allow\", \"allow\", \"allow\", \"deny\", \"allow\"], 0, [[\"a\", 0], [\"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\", \"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\", \"deny\"], 2, [[\"a\", 0]]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\"], 0, [[\"a\", 1]]], \"passed\": false}, {\"check\": \"exhausted lease refetches\", \"actual\": [[\"allow\", \"allow\", \"deny\", \"deny\", \"deny\", 8], 8, []], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", 5], 5, []], \"passed\": false}, {\"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\", \"deny\", 3, \"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\": false}], \"passed\": false}\n"},"fixed":{"elapsed_ms":39.416,"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"}