{"abstract":"Traffic from one full window ago is counted again when its slot comes around.","category":"Rate limiter algorithms","checks":6,"contract":"Input {slots N, slot_ms B, limit, requests [t]} with nondecreasing t. Epoch e = t div B maps to slot e mod N; each slot remembers the epoch it counts and is zeroed when reused for a newer epoch. The rolling total sums slots whose epoch lies in (e - N, e]. Admit while total < limit and count the request in the current slot. Return [decisions, slot counts, slot epochs].","contract_signature":"x","evaluation_group":"w2-rate_limiter_algorithms-ring-subwindows","failed_approach":"Zeroing only saturated slots still replays partial counts from the previous lap.","family":"w2-rate_limiter_algorithms-ring-subwindows-stale-slot","id":"FA-73786","implementations":{"attempt":{"sha256":"41f074a571de946b421d980f02ec5fb8a0e8de894628d0363b2fbcf126bc56eb","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    N = x['slots']\n    B = x['slot_ms']\n    lim = x['limit']\n    cnt = [0] * N\n    ep = [-1] * N\n    out = []\n    for t in x['requests']:\n        e = t // B\n        s = e % N\n        if ep[s] != e and cnt[s] >= lim:\n            cnt[s] = 0\n        ep[s] = e\n        total = sum(cnt[i] for i in range(N) if e - N < ep[i] <= e)\n        if total < lim:\n            cnt[s] += 1\n            out.append('allow')\n        else:\n            out.append('deny')\n    return [out, cnt, ep]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['slot reused after a lap',\n   {'limit': 3, 'requests': [0, 10, 20, 401, 410, 420, 430], 'slot_ms': 100, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],\n  ['old slots leave the window',\n   {'limit': 4, 'requests': [0, 100, 200, 300, 501, 610, 620, 630], 'slot_ms': 100, 'slots': 5},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],\n    [1, 1, 1, 1, 0],\n    [5, 6, 2, 3, -1]]],\n  ['long idle gap',\n   {'limit': 2, 'requests': [0, 250, 5001, 5010, 5020], 'slot_ms': 200, 'slots': 3},\n   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],\n  ['slot index uses epoch',\n   {'limit': 5, 'requests': [0, 1, 2, 3, 252, 252, 503, 999], 'slot_ms': 250, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],\n    [4, 1, 0, 0],\n    [0, 1, 2, 3]]],\n  ['partial saturation reuse',\n   {'limit': 5, 'requests': [0, 1, 150, 201, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],\n  ['random traffic',\n   {'limit': 4,\n    'requests': [46, 120, 415, 554, 645, 818, 865, 1373, 1525, 1554, 1664, 1801, 1833, 1867],\n    'slot_ms': 100,\n    'slots': 5},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny',\n     'deny'],\n    [2, 1, 0, 1, 1],\n    [15, 16, -1, 18, 4]]]],\n [['slot reused after a lap',\n   {'limit': 3, 'requests': [0, 10, 20, 402, 410, 420, 430], 'slot_ms': 100, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],\n  ['old slots leave the window',\n   {'limit': 4, 'requests': [0, 100, 200, 300, 502, 610, 620, 630], 'slot_ms': 100, 'slots': 5},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],\n    [1, 1, 1, 1, 0],\n    [5, 6, 2, 3, -1]]],\n  ['long idle gap',\n   {'limit': 2, 'requests': [0, 250, 5002, 5010, 5020], 'slot_ms': 200, 'slots': 3},\n   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],\n  ['slot index uses epoch',\n   {'limit': 5, 'requests': [0, 1, 2, 3, 253, 252, 503, 999], 'slot_ms': 250, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],\n    [4, 1, 0, 0],\n    [0, 1, 2, 3]]],\n  ['partial saturation reuse',\n   {'limit': 5, 'requests': [0, 1, 150, 202, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],\n  ['random traffic',\n   {'limit': 4,\n    'requests': [98, 199, 284, 322, 376, 477, 477, 489, 1105, 1133, 1150, 1440, 1769, 1950],\n    'slot_ms': 100,\n    'slots': 5},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny',\n     'deny',\n     'deny',\n     'deny',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    [1, 3, 1, 1, 1],\n    [0, 11, 17, 3, 19]]]],\n [['slot reused after a lap',\n   {'limit': 3, 'requests': [0, 10, 20, 403, 410, 420, 430], 'slot_ms': 100, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],\n  ['old slots leave the window',\n   {'limit': 4, 'requests': [0, 100, 200, 300, 503, 610, 620, 630], 'slot_ms': 100, 'slots': 5},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],\n    [1, 1, 1, 1, 0],\n    [5, 6, 2, 3, -1]]],\n  ['long idle gap',\n   {'limit': 2, 'requests': [0, 250, 5003, 5010, 5020], 'slot_ms': 200, 'slots': 3},\n   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],\n  ['slot index uses epoch',\n   {'limit': 5, 'requests': [0, 1, 2, 3, 254, 252, 503, 999], 'slot_ms': 250, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],\n    [4, 1, 0, 0],\n    [0, 1, 2, 3]]],\n  ['partial saturation reuse',\n   {'limit': 5, 'requests': [0, 1, 150, 203, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],\n  ['random traffic',\n   {'limit': 4,\n    'requests': [81, 356, 399, 715, 737, 761, 1248, 1286, 1450, 1484, 1518, 1539, 1635, 1691],\n    'slot_ms': 100,\n    'slots': 5},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny',\n     'deny',\n     'deny',\n     'deny'],\n    [0, 0, 2, 2, 2],\n    [15, 16, 12, 3, 14]]]],\n [['slot reused after a lap',\n   {'limit': 3, 'requests': [0, 10, 20, 404, 410, 420, 430], 'slot_ms': 100, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],\n  ['old slots leave the window',\n   {'limit': 4, 'requests': [0, 100, 200, 300, 504, 610, 620, 630], 'slot_ms': 100, 'slots': 5},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],\n    [1, 1, 1, 1, 0],\n    [5, 6, 2, 3, -1]]],\n  ['long idle gap',\n   {'limit': 2, 'requests': [0, 250, 5004, 5010, 5020], 'slot_ms': 200, 'slots': 3},\n   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],\n  ['slot index uses epoch',\n   {'limit': 5, 'requests': [0, 1, 2, 3, 255, 252, 503, 999], 'slot_ms': 250, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],\n    [4, 1, 0, 0],\n    [0, 1, 2, 3]]],\n  ['partial saturation reuse',\n   {'limit': 5, 'requests': [0, 1, 150, 204, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],\n  ['random traffic',\n   {'limit': 4,\n    'requests': [39, 260, 414, 610, 686, 731, 892, 1075, 1107, 1491, 1496, 1594, 1832, 1860],\n    'slot_ms': 100,\n    'slots': 5},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny'],\n    [1, 1, 1, 1, 2],\n    [15, 11, 7, 18, 14]]]],\n [['slot reused after a lap',\n   {'limit': 3, 'requests': [0, 10, 20, 405, 410, 420, 430], 'slot_ms': 100, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],\n  ['old slots leave the window',\n   {'limit': 4, 'requests': [0, 100, 200, 300, 505, 610, 620, 630], 'slot_ms': 100, 'slots': 5},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],\n    [1, 1, 1, 1, 0],\n    [5, 6, 2, 3, -1]]],\n  ['long idle gap',\n   {'limit': 2, 'requests': [0, 250, 5005, 5010, 5020], 'slot_ms': 200, 'slots': 3},\n   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],\n  ['slot index uses epoch',\n   {'limit': 5, 'requests': [0, 1, 2, 3, 256, 252, 503, 999], 'slot_ms': 250, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],\n    [4, 1, 0, 0],\n    [0, 1, 2, 3]]],\n  ['partial saturation reuse',\n   {'limit': 5, 'requests': [0, 1, 150, 205, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],\n  ['random traffic',\n   {'limit': 4,\n    'requests': [2, 79, 224, 260, 340, 480, 497, 648, 755, 916, 1103, 1554, 1762, 1944],\n    'slot_ms': 100,\n    'slots': 5},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny',\n     'deny',\n     'deny',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    [1, 1, 1, 0, 1],\n    [15, 11, 17, 3, 19]]]]]\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":"de6ae0d7c247c8e8508fa92ed2c6b127c2d45249a74cbb3d0dfb59c5447542b9","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    N = x['slots']\n    B = x['slot_ms']\n    lim = x['limit']\n    cnt = [0] * N\n    ep = [-1] * N\n    out = []\n    for t in x['requests']:\n        e = t // B\n        s = e % N\n        ep[s] = e\n        total = sum(cnt[i] for i in range(N) if e - N < ep[i] <= e)\n        if total < lim:\n            cnt[s] += 1\n            out.append('allow')\n        else:\n            out.append('deny')\n    return [out, cnt, ep]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['slot reused after a lap',\n   {'limit': 3, 'requests': [0, 10, 20, 401, 410, 420, 430], 'slot_ms': 100, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],\n  ['old slots leave the window',\n   {'limit': 4, 'requests': [0, 100, 200, 300, 501, 610, 620, 630], 'slot_ms': 100, 'slots': 5},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],\n    [1, 1, 1, 1, 0],\n    [5, 6, 2, 3, -1]]],\n  ['long idle gap',\n   {'limit': 2, 'requests': [0, 250, 5001, 5010, 5020], 'slot_ms': 200, 'slots': 3},\n   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],\n  ['slot index uses epoch',\n   {'limit': 5, 'requests': [0, 1, 2, 3, 252, 252, 503, 999], 'slot_ms': 250, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],\n    [4, 1, 0, 0],\n    [0, 1, 2, 3]]],\n  ['partial saturation reuse',\n   {'limit': 5, 'requests': [0, 1, 150, 201, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],\n  ['random traffic',\n   {'limit': 4,\n    'requests': [46, 120, 415, 554, 645, 818, 865, 1373, 1525, 1554, 1664, 1801, 1833, 1867],\n    'slot_ms': 100,\n    'slots': 5},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny',\n     'deny'],\n    [2, 1, 0, 1, 1],\n    [15, 16, -1, 18, 4]]]],\n [['slot reused after a lap',\n   {'limit': 3, 'requests': [0, 10, 20, 402, 410, 420, 430], 'slot_ms': 100, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],\n  ['old slots leave the window',\n   {'limit': 4, 'requests': [0, 100, 200, 300, 502, 610, 620, 630], 'slot_ms': 100, 'slots': 5},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],\n    [1, 1, 1, 1, 0],\n    [5, 6, 2, 3, -1]]],\n  ['long idle gap',\n   {'limit': 2, 'requests': [0, 250, 5002, 5010, 5020], 'slot_ms': 200, 'slots': 3},\n   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],\n  ['slot index uses epoch',\n   {'limit': 5, 'requests': [0, 1, 2, 3, 253, 252, 503, 999], 'slot_ms': 250, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],\n    [4, 1, 0, 0],\n    [0, 1, 2, 3]]],\n  ['partial saturation reuse',\n   {'limit': 5, 'requests': [0, 1, 150, 202, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],\n  ['random traffic',\n   {'limit': 4,\n    'requests': [98, 199, 284, 322, 376, 477, 477, 489, 1105, 1133, 1150, 1440, 1769, 1950],\n    'slot_ms': 100,\n    'slots': 5},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny',\n     'deny',\n     'deny',\n     'deny',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    [1, 3, 1, 1, 1],\n    [0, 11, 17, 3, 19]]]],\n [['slot reused after a lap',\n   {'limit': 3, 'requests': [0, 10, 20, 403, 410, 420, 430], 'slot_ms': 100, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],\n  ['old slots leave the window',\n   {'limit': 4, 'requests': [0, 100, 200, 300, 503, 610, 620, 630], 'slot_ms': 100, 'slots': 5},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],\n    [1, 1, 1, 1, 0],\n    [5, 6, 2, 3, -1]]],\n  ['long idle gap',\n   {'limit': 2, 'requests': [0, 250, 5003, 5010, 5020], 'slot_ms': 200, 'slots': 3},\n   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],\n  ['slot index uses epoch',\n   {'limit': 5, 'requests': [0, 1, 2, 3, 254, 252, 503, 999], 'slot_ms': 250, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],\n    [4, 1, 0, 0],\n    [0, 1, 2, 3]]],\n  ['partial saturation reuse',\n   {'limit': 5, 'requests': [0, 1, 150, 203, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],\n  ['random traffic',\n   {'limit': 4,\n    'requests': [81, 356, 399, 715, 737, 761, 1248, 1286, 1450, 1484, 1518, 1539, 1635, 1691],\n    'slot_ms': 100,\n    'slots': 5},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny',\n     'deny',\n     'deny',\n     'deny'],\n    [0, 0, 2, 2, 2],\n    [15, 16, 12, 3, 14]]]],\n [['slot reused after a lap',\n   {'limit': 3, 'requests': [0, 10, 20, 404, 410, 420, 430], 'slot_ms': 100, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],\n  ['old slots leave the window',\n   {'limit': 4, 'requests': [0, 100, 200, 300, 504, 610, 620, 630], 'slot_ms': 100, 'slots': 5},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],\n    [1, 1, 1, 1, 0],\n    [5, 6, 2, 3, -1]]],\n  ['long idle gap',\n   {'limit': 2, 'requests': [0, 250, 5004, 5010, 5020], 'slot_ms': 200, 'slots': 3},\n   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],\n  ['slot index uses epoch',\n   {'limit': 5, 'requests': [0, 1, 2, 3, 255, 252, 503, 999], 'slot_ms': 250, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],\n    [4, 1, 0, 0],\n    [0, 1, 2, 3]]],\n  ['partial saturation reuse',\n   {'limit': 5, 'requests': [0, 1, 150, 204, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],\n  ['random traffic',\n   {'limit': 4,\n    'requests': [39, 260, 414, 610, 686, 731, 892, 1075, 1107, 1491, 1496, 1594, 1832, 1860],\n    'slot_ms': 100,\n    'slots': 5},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny'],\n    [1, 1, 1, 1, 2],\n    [15, 11, 7, 18, 14]]]],\n [['slot reused after a lap',\n   {'limit': 3, 'requests': [0, 10, 20, 405, 410, 420, 430], 'slot_ms': 100, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [3, 0, 0, 0], [4, -1, -1, -1]]],\n  ['old slots leave the window',\n   {'limit': 4, 'requests': [0, 100, 200, 300, 505, 610, 620, 630], 'slot_ms': 100, 'slots': 5},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny'],\n    [1, 1, 1, 1, 0],\n    [5, 6, 2, 3, -1]]],\n  ['long idle gap',\n   {'limit': 2, 'requests': [0, 250, 5005, 5010, 5020], 'slot_ms': 200, 'slots': 3},\n   [['allow', 'allow', 'allow', 'allow', 'deny'], [1, 2, 0], [0, 25, -1]]],\n  ['slot index uses epoch',\n   {'limit': 5, 'requests': [0, 1, 2, 3, 256, 252, 503, 999], 'slot_ms': 250, 'slots': 4},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny'],\n    [4, 1, 0, 0],\n    [0, 1, 2, 3]]],\n  ['partial saturation reuse',\n   {'limit': 5, 'requests': [0, 1, 150, 205, 201, 202, 203, 204], 'slot_ms': 100, 'slots': 2},\n   [['allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [4, 1], [2, 1]]],\n  ['random traffic',\n   {'limit': 4,\n    'requests': [2, 79, 224, 260, 340, 480, 497, 648, 755, 916, 1103, 1554, 1762, 1944],\n    'slot_ms': 100,\n    'slots': 5},\n   [['allow',\n     'allow',\n     'allow',\n     'allow',\n     'deny',\n     'deny',\n     'deny',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow',\n     'allow'],\n    [1, 1, 1, 0, 1],\n    [15, 11, 17, 3, 19]]]]]\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-ring-subwindows-stale-slot","generated_at":"2026-09-29T14:48:50.709786+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Rolling-window limiters in service meshes keep a ring of small buckets; forgetting to zero reused buckets or summing stale ones replays old traffic into current decisions.","root_cause":"A slot is relabelled with the new epoch without zeroing its count.","sha256":"5148d83f8c55319e017bdd5936aaf18acdd6992456ba6b3db913981cbf7a9686","title":"Rolling window over a ring of sub-window counters: reused slot keeps a lapped count · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verified":true,"visibility":"public","verification":{"attempt":{"elapsed_ms":40.387,"exit_code":1,"observations":[{"actual":[["allow","allow","allow","allow","allow","allow","deny"],[3,0,0,0],[4,-1,-1,-1]],"check":"slot reused after a lap","expected":[["allow","allow","allow","allow","allow","allow","deny"],[3,0,0,0],[4,-1,-1,-1]],"passed":true},{"actual":[["allow","allow","allow","allow","deny","deny","deny","deny"],[1,1,1,1,0],[5,6,2,3,-1]],"check":"old slots leave the window","expected":[["allow","allow","allow","allow","allow","allow","deny","deny"],[1,1,1,1,0],[5,6,2,3,-1]],"passed":false},{"actual":[["allow","allow","allow","deny","deny"],[1,2,0],[0,25,-1]],"check":"long idle gap","expected":[["allow","allow","allow","allow","deny"],[1,2,0],[0,25,-1]],"passed":false},{"actual":[["allow","allow","allow","allow","allow","deny","deny","deny"],[4,1,0,0],[0,1,2,3]],"check":"slot index uses epoch","expected":[["allow","allow","allow","allow","allow","deny","deny","deny"],[4,1,0,0],[0,1,2,3]],"passed":true},{"actual":[["allow","allow","allow","allow","allow","deny","deny","deny"],[4,1],[2,1]],"check":"partial saturation reuse","expected":[["allow","allow","allow","allow","allow","allow","allow","deny"],[4,1],[2,1]],"passed":false},{"actual":[["allow","allow","allow","allow","deny","deny","deny","allow","allow","deny","deny","deny","deny","deny"],[3,1,0,1,1],[15,16,-1,18,4]],"check":"random traffic","expected":[["allow","allow","allow","allow","allow","allow","deny","allow","allow","allow","allow","allow","deny","deny"],[2,1,0,1,1],[15,16,-1,18,4]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"slot reused after a lap\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\"], [3, 0, 0, 0], [4, -1, -1, -1]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\"], [3, 0, 0, 0], [4, -1, -1, -1]], \"passed\": true}, {\"check\": \"old slots leave the window\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\", \"deny\"], [1, 1, 1, 1, 0], [5, 6, 2, 3, -1]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\"], [1, 1, 1, 1, 0], [5, 6, 2, 3, -1]], \"passed\": false}, {\"check\": \"long idle gap\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"deny\", \"deny\"], [1, 2, 0], [0, 25, -1]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"deny\"], [1, 2, 0], [0, 25, -1]], \"passed\": false}, {\"check\": \"slot index uses epoch\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\"], [4, 1, 0, 0], [0, 1, 2, 3]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\"], [4, 1, 0, 0], [0, 1, 2, 3]], \"passed\": true}, {\"check\": \"partial saturation reuse\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\"], [4, 1], [2, 1]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\"], [4, 1], [2, 1]], \"passed\": false}, {\"check\": \"random traffic\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\", \"deny\", \"deny\"], [3, 1, 0, 1, 1], [15, 16, -1, 18, 4]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\"], [2, 1, 0, 1, 1], [15, 16, -1, 18, 4]], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":38.512,"exit_code":1,"observations":[{"actual":[["allow","allow","allow","deny","deny","deny","deny"],[3,0,0,0],[4,-1,-1,-1]],"check":"slot reused after a lap","expected":[["allow","allow","allow","allow","allow","allow","deny"],[3,0,0,0],[4,-1,-1,-1]],"passed":false},{"actual":[["allow","allow","allow","allow","deny","deny","deny","deny"],[1,1,1,1,0],[5,6,2,3,-1]],"check":"old slots leave the window","expected":[["allow","allow","allow","allow","allow","allow","deny","deny"],[1,1,1,1,0],[5,6,2,3,-1]],"passed":false},{"actual":[["allow","allow","allow","deny","deny"],[1,2,0],[0,25,-1]],"check":"long idle gap","expected":[["allow","allow","allow","allow","deny"],[1,2,0],[0,25,-1]],"passed":false},{"actual":[["allow","allow","allow","allow","allow","deny","deny","deny"],[4,1,0,0],[0,1,2,3]],"check":"slot index uses epoch","expected":[["allow","allow","allow","allow","allow","deny","deny","deny"],[4,1,0,0],[0,1,2,3]],"passed":true},{"actual":[["allow","allow","allow","allow","allow","deny","deny","deny"],[4,1],[2,1]],"check":"partial saturation reuse","expected":[["allow","allow","allow","allow","allow","allow","allow","deny"],[4,1],[2,1]],"passed":false},{"actual":[["allow","allow","allow","allow","deny","deny","deny","allow","allow","deny","deny","deny","deny","deny"],[3,1,0,1,1],[15,16,-1,18,4]],"check":"random traffic","expected":[["allow","allow","allow","allow","allow","allow","deny","allow","allow","allow","allow","allow","deny","deny"],[2,1,0,1,1],[15,16,-1,18,4]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"slot reused after a lap\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\", \"deny\"], [3, 0, 0, 0], [4, -1, -1, -1]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\"], [3, 0, 0, 0], [4, -1, -1, -1]], \"passed\": false}, {\"check\": \"old slots leave the window\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\", \"deny\"], [1, 1, 1, 1, 0], [5, 6, 2, 3, -1]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\"], [1, 1, 1, 1, 0], [5, 6, 2, 3, -1]], \"passed\": false}, {\"check\": \"long idle gap\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"deny\", \"deny\"], [1, 2, 0], [0, 25, -1]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"deny\"], [1, 2, 0], [0, 25, -1]], \"passed\": false}, {\"check\": \"slot index uses epoch\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\"], [4, 1, 0, 0], [0, 1, 2, 3]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\"], [4, 1, 0, 0], [0, 1, 2, 3]], \"passed\": true}, {\"check\": \"partial saturation reuse\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\"], [4, 1], [2, 1]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\"], [4, 1], [2, 1]], \"passed\": false}, {\"check\": \"random traffic\", \"actual\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\", \"allow\", \"allow\", \"deny\", \"deny\", \"deny\", \"deny\", \"deny\"], [3, 1, 0, 1, 1], [15, 16, -1, 18, 4]], \"expected\": [[\"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"allow\", \"allow\", \"allow\", \"allow\", \"allow\", \"deny\", \"deny\"], [2, 1, 0, 1, 1], [15, 16, -1, 18, 4]], \"passed\": false}], \"passed\": false}\n"}},"member_only":{"stages":["fixed"],"fields":["implementations.fixed","verification.fixed","harness","repair"],"note":"The verified repair, its recorded checks, the repair description, and the scoring harness are available to members."}}