{"abstract":"Callers sleep slightly too little and run ahead of the configured rate.","category":"Rate limiter algorithms","checks":6,"contract":"Input {rate (permits per second), max_burst_s, requests [[t_ms, permits]]} with nondecreasing t. The interval is I = 1000/rate ms. When t is past next_free, idle time is converted into stored permits (capped at max_burst_s*rate) and next_free moves to t. A request waits max(0, next_free - t), i.e. it pays for the previous reservation, then consumes stored permits first and pushes next_free by I per fresh permit. Return [ceil waits in ms, stored, next_free] with exact fractions as strings.","evaluation_group":"w2-rate_limiter_algorithms-reservation-limiter","failed_approach":"Rounding to nearest still shortens waits with small fractions.","family":"w2-rate_limiter_algorithms-reservation-limiter-wait-rounding","id":"FA-73666","implementations":{"attempt":{"sha256":"819c0a16b3a3d2502064de6c1786cc58b432afa4543bdbbb9b835a1826fcf248","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nfrom fractions import Fraction\nN = 1\nobservations = []\ndef solve(x):\n    rate = x['rate']\n    I = Fraction(1000, rate)\n    max_stored = Fraction(x['max_burst_s'] * rate)\n    stored = Fraction(0)\n    next_free = Fraction(0)\n    out = []\n    for t, p in x['requests']:\n        if t > next_free:\n            stored = min(max_stored, stored + (t - next_free) / I)\n            next_free = Fraction(t)\n        wait = max(Fraction(0), next_free - t)\n        use = min(Fraction(p), stored)\n        fresh = p - use\n        next_free += fresh * I\n        stored -= use\n        out.append(round(wait))\n    return [out, str(stored), str(next_free)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['pay later for big request',\n   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [101, 1], [5000, 1]]},\n   [[0, 2000, 2099, 0], '0', '5200']],\n  ['stored permits capped',\n   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10001, 1]]},\n   [[0, 0, 500, 999], '0', '11500']],\n  ['stored permits consumed',\n   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3001, 1]]},\n   [[0, 0, 0, 499], '0', '3750']],\n  ['resync after idle',\n   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4001, 2], [4001, 4]]},\n   [[0, 0, 0, 0, 0], '3', '4001']],\n  ['fractional waits',\n   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [11, 1], [20, 2]]},\n   [[0, 334, 656, 980], '0', '5000/3']],\n  ['random acquires',\n   {'max_burst_s': 2,\n    'rate': 2,\n    'requests': [[610, 3],\n                 [1148, 4],\n                 [1339, 3],\n                 [2090, 3],\n                 [2093, 2],\n                 [2589, 1],\n                 [2607, 4],\n                 [2941, 2],\n                 [3090, 2]]},\n   [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']]],\n [['pay later for big request',\n   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [102, 1], [5000, 1]]},\n   [[0, 2000, 2098, 0], '0', '5200']],\n  ['stored permits capped',\n   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10002, 1]]},\n   [[0, 0, 500, 998], '0', '11500']],\n  ['stored permits consumed',\n   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3002, 1]]},\n   [[0, 0, 0, 498], '0', '3750']],\n  ['resync after idle',\n   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4002, 2], [4002, 4]]},\n   [[0, 0, 0, 0, 0], '3', '4002']],\n  ['fractional waits',\n   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [12, 1], [20, 2]]},\n   [[0, 334, 655, 980], '0', '5000/3']],\n  ['random acquires',\n   {'max_burst_s': 2,\n    'rate': 2,\n    'requests': [[142, 4],\n                 [325, 1],\n                 [548, 2],\n                 [901, 1],\n                 [1366, 1],\n                 [1827, 2],\n                 [1998, 3],\n                 [2374, 1],\n                 [2914, 2]]},\n   [[0, 1675, 1952, 2599, 2634, 2673, 3502, 4626, 4586], '0', '8500']]],\n [['pay later for big request',\n   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [103, 1], [5000, 1]]},\n   [[0, 2000, 2097, 0], '0', '5200']],\n  ['stored permits capped',\n   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10003, 1]]},\n   [[0, 0, 500, 997], '0', '11500']],\n  ['stored permits consumed',\n   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3003, 1]]},\n   [[0, 0, 0, 497], '0', '3750']],\n  ['resync after idle',\n   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4003, 2], [4003, 4]]},\n   [[0, 0, 0, 0, 0], '3', '4003']],\n  ['fractional waits',\n   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [13, 1], [20, 2]]},\n   [[0, 334, 654, 980], '0', '5000/3']],\n  ['random acquires',\n   {'max_burst_s': 2,\n    'rate': 2,\n    'requests': [[644, 4],\n                 [886, 4],\n                 [910, 3],\n                 [1485, 1],\n                 [1585, 2],\n                 [1776, 4],\n                 [2163, 2],\n                 [2628, 3],\n                 [2698, 2]]},\n   [[0, 1114, 3090, 4015, 4415, 5224, 6837, 7372, 8802], '0', '12500']]],\n [['pay later for big request',\n   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [104, 1], [5000, 1]]},\n   [[0, 2000, 2096, 0], '0', '5200']],\n  ['stored permits capped',\n   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10004, 1]]},\n   [[0, 0, 500, 996], '0', '11500']],\n  ['stored permits consumed',\n   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3004, 1]]},\n   [[0, 0, 0, 496], '0', '3750']],\n  ['resync after idle',\n   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4004, 2], [4004, 4]]},\n   [[0, 0, 0, 0, 0], '3', '4004']],\n  ['fractional waits',\n   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [14, 1], [20, 2]]},\n   [[0, 334, 653, 980], '0', '5000/3']],\n  ['random acquires',\n   {'max_burst_s': 2,\n    'rate': 2,\n    'requests': [[106, 2],\n                 [1122, 1],\n                 [1604, 3],\n                 [1998, 1],\n                 [2099, 1],\n                 [2549, 2],\n                 [2752, 1],\n                 [2983, 1],\n                 [3690, 4]]},\n   [[0, 0, 0, 1002, 1401, 1451, 2248, 2517, 2310], '0', '8000']]],\n [['pay later for big request',\n   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [105, 1], [5000, 1]]},\n   [[0, 2000, 2095, 0], '0', '5200']],\n  ['stored permits capped',\n   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10005, 1]]},\n   [[0, 0, 500, 995], '0', '11500']],\n  ['stored permits consumed',\n   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3005, 1]]},\n   [[0, 0, 0, 495], '0', '3750']],\n  ['resync after idle',\n   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4005, 2], [4005, 4]]},\n   [[0, 0, 0, 0, 0], '3', '4005']],\n  ['fractional waits',\n   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [15, 1], [20, 2]]},\n   [[0, 334, 652, 980], '0', '5000/3']],\n  ['random acquires',\n   {'max_burst_s': 2,\n    'rate': 2,\n    'requests': [[2392, 4],\n                 [2748, 2],\n                 [3147, 1],\n                 [3291, 2],\n                 [3293, 2],\n                 [3431, 2],\n                 [3441, 1],\n                 [3672, 1],\n                 [3732, 4]]},\n   [[0, 0, 245, 601, 1599, 2461, 3451, 3720, 4160], '0', '9892']]]]\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":"51847578b31306c4f773b1d1ea2593d586785ac8f932d64223377df35457bb8e","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nfrom fractions import Fraction\nN = 1\nobservations = []\ndef solve(x):\n    rate = x['rate']\n    I = Fraction(1000, rate)\n    max_stored = Fraction(x['max_burst_s'] * rate)\n    stored = Fraction(0)\n    next_free = Fraction(0)\n    out = []\n    for t, p in x['requests']:\n        if t > next_free:\n            stored = min(max_stored, stored + (t - next_free) / I)\n            next_free = Fraction(t)\n        wait = max(Fraction(0), next_free - t)\n        use = min(Fraction(p), stored)\n        fresh = p - use\n        next_free += fresh * I\n        stored -= use\n        out.append(int(wait))\n    return [out, str(stored), str(next_free)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['pay later for big request',\n   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [101, 1], [5000, 1]]},\n   [[0, 2000, 2099, 0], '0', '5200']],\n  ['stored permits capped',\n   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10001, 1]]},\n   [[0, 0, 500, 999], '0', '11500']],\n  ['stored permits consumed',\n   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3001, 1]]},\n   [[0, 0, 0, 499], '0', '3750']],\n  ['resync after idle',\n   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4001, 2], [4001, 4]]},\n   [[0, 0, 0, 0, 0], '3', '4001']],\n  ['fractional waits',\n   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [11, 1], [20, 2]]},\n   [[0, 334, 656, 980], '0', '5000/3']],\n  ['random acquires',\n   {'max_burst_s': 2,\n    'rate': 2,\n    'requests': [[610, 3],\n                 [1148, 4],\n                 [1339, 3],\n                 [2090, 3],\n                 [2093, 2],\n                 [2589, 1],\n                 [2607, 4],\n                 [2941, 2],\n                 [3090, 2]]},\n   [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']]],\n [['pay later for big request',\n   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [102, 1], [5000, 1]]},\n   [[0, 2000, 2098, 0], '0', '5200']],\n  ['stored permits capped',\n   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10002, 1]]},\n   [[0, 0, 500, 998], '0', '11500']],\n  ['stored permits consumed',\n   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3002, 1]]},\n   [[0, 0, 0, 498], '0', '3750']],\n  ['resync after idle',\n   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4002, 2], [4002, 4]]},\n   [[0, 0, 0, 0, 0], '3', '4002']],\n  ['fractional waits',\n   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [12, 1], [20, 2]]},\n   [[0, 334, 655, 980], '0', '5000/3']],\n  ['random acquires',\n   {'max_burst_s': 2,\n    'rate': 2,\n    'requests': [[142, 4],\n                 [325, 1],\n                 [548, 2],\n                 [901, 1],\n                 [1366, 1],\n                 [1827, 2],\n                 [1998, 3],\n                 [2374, 1],\n                 [2914, 2]]},\n   [[0, 1675, 1952, 2599, 2634, 2673, 3502, 4626, 4586], '0', '8500']]],\n [['pay later for big request',\n   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [103, 1], [5000, 1]]},\n   [[0, 2000, 2097, 0], '0', '5200']],\n  ['stored permits capped',\n   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10003, 1]]},\n   [[0, 0, 500, 997], '0', '11500']],\n  ['stored permits consumed',\n   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3003, 1]]},\n   [[0, 0, 0, 497], '0', '3750']],\n  ['resync after idle',\n   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4003, 2], [4003, 4]]},\n   [[0, 0, 0, 0, 0], '3', '4003']],\n  ['fractional waits',\n   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [13, 1], [20, 2]]},\n   [[0, 334, 654, 980], '0', '5000/3']],\n  ['random acquires',\n   {'max_burst_s': 2,\n    'rate': 2,\n    'requests': [[644, 4],\n                 [886, 4],\n                 [910, 3],\n                 [1485, 1],\n                 [1585, 2],\n                 [1776, 4],\n                 [2163, 2],\n                 [2628, 3],\n                 [2698, 2]]},\n   [[0, 1114, 3090, 4015, 4415, 5224, 6837, 7372, 8802], '0', '12500']]],\n [['pay later for big request',\n   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [104, 1], [5000, 1]]},\n   [[0, 2000, 2096, 0], '0', '5200']],\n  ['stored permits capped',\n   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10004, 1]]},\n   [[0, 0, 500, 996], '0', '11500']],\n  ['stored permits consumed',\n   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3004, 1]]},\n   [[0, 0, 0, 496], '0', '3750']],\n  ['resync after idle',\n   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4004, 2], [4004, 4]]},\n   [[0, 0, 0, 0, 0], '3', '4004']],\n  ['fractional waits',\n   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [14, 1], [20, 2]]},\n   [[0, 334, 653, 980], '0', '5000/3']],\n  ['random acquires',\n   {'max_burst_s': 2,\n    'rate': 2,\n    'requests': [[106, 2],\n                 [1122, 1],\n                 [1604, 3],\n                 [1998, 1],\n                 [2099, 1],\n                 [2549, 2],\n                 [2752, 1],\n                 [2983, 1],\n                 [3690, 4]]},\n   [[0, 0, 0, 1002, 1401, 1451, 2248, 2517, 2310], '0', '8000']]],\n [['pay later for big request',\n   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [105, 1], [5000, 1]]},\n   [[0, 2000, 2095, 0], '0', '5200']],\n  ['stored permits capped',\n   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10005, 1]]},\n   [[0, 0, 500, 995], '0', '11500']],\n  ['stored permits consumed',\n   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3005, 1]]},\n   [[0, 0, 0, 495], '0', '3750']],\n  ['resync after idle',\n   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4005, 2], [4005, 4]]},\n   [[0, 0, 0, 0, 0], '3', '4005']],\n  ['fractional waits',\n   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [15, 1], [20, 2]]},\n   [[0, 334, 652, 980], '0', '5000/3']],\n  ['random acquires',\n   {'max_burst_s': 2,\n    'rate': 2,\n    'requests': [[2392, 4],\n                 [2748, 2],\n                 [3147, 1],\n                 [3291, 2],\n                 [3293, 2],\n                 [3431, 2],\n                 [3441, 1],\n                 [3672, 1],\n                 [3732, 4]]},\n   [[0, 0, 245, 601, 1599, 2461, 3451, 3720, 4160], '0', '9892']]]]\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":"b798c6d97203ed2d5704773d4a8bb502d77df750b3c29bb6f94eddd87cdd2dcb","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\nimport math\nfrom fractions import Fraction\nN = 1\nobservations = []\ndef solve(x):\n    rate = x['rate']\n    I = Fraction(1000, rate)\n    max_stored = Fraction(x['max_burst_s'] * rate)\n    stored = Fraction(0)\n    next_free = Fraction(0)\n    out = []\n    for t, p in x['requests']:\n        if t > next_free:\n            stored = min(max_stored, stored + (t - next_free) / I)\n            next_free = Fraction(t)\n        wait = max(Fraction(0), next_free - t)\n        use = min(Fraction(p), stored)\n        fresh = p - use\n        next_free += fresh * I\n        stored -= use\n        out.append(math.ceil(wait))\n    return [out, str(stored), str(next_free)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['pay later for big request',\n   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [101, 1], [5000, 1]]},\n   [[0, 2000, 2099, 0], '0', '5200']],\n  ['stored permits capped',\n   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10001, 1]]},\n   [[0, 0, 500, 999], '0', '11500']],\n  ['stored permits consumed',\n   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3001, 1]]},\n   [[0, 0, 0, 499], '0', '3750']],\n  ['resync after idle',\n   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4001, 2], [4001, 4]]},\n   [[0, 0, 0, 0, 0], '3', '4001']],\n  ['fractional waits',\n   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [11, 1], [20, 2]]},\n   [[0, 334, 656, 980], '0', '5000/3']],\n  ['random acquires',\n   {'max_burst_s': 2,\n    'rate': 2,\n    'requests': [[610, 3],\n                 [1148, 4],\n                 [1339, 3],\n                 [2090, 3],\n                 [2093, 2],\n                 [2589, 1],\n                 [2607, 4],\n                 [2941, 2],\n                 [3090, 2]]},\n   [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']]],\n [['pay later for big request',\n   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [102, 1], [5000, 1]]},\n   [[0, 2000, 2098, 0], '0', '5200']],\n  ['stored permits capped',\n   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10002, 1]]},\n   [[0, 0, 500, 998], '0', '11500']],\n  ['stored permits consumed',\n   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3002, 1]]},\n   [[0, 0, 0, 498], '0', '3750']],\n  ['resync after idle',\n   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4002, 2], [4002, 4]]},\n   [[0, 0, 0, 0, 0], '3', '4002']],\n  ['fractional waits',\n   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [12, 1], [20, 2]]},\n   [[0, 334, 655, 980], '0', '5000/3']],\n  ['random acquires',\n   {'max_burst_s': 2,\n    'rate': 2,\n    'requests': [[142, 4],\n                 [325, 1],\n                 [548, 2],\n                 [901, 1],\n                 [1366, 1],\n                 [1827, 2],\n                 [1998, 3],\n                 [2374, 1],\n                 [2914, 2]]},\n   [[0, 1675, 1952, 2599, 2634, 2673, 3502, 4626, 4586], '0', '8500']]],\n [['pay later for big request',\n   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [103, 1], [5000, 1]]},\n   [[0, 2000, 2097, 0], '0', '5200']],\n  ['stored permits capped',\n   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10003, 1]]},\n   [[0, 0, 500, 997], '0', '11500']],\n  ['stored permits consumed',\n   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3003, 1]]},\n   [[0, 0, 0, 497], '0', '3750']],\n  ['resync after idle',\n   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4003, 2], [4003, 4]]},\n   [[0, 0, 0, 0, 0], '3', '4003']],\n  ['fractional waits',\n   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [13, 1], [20, 2]]},\n   [[0, 334, 654, 980], '0', '5000/3']],\n  ['random acquires',\n   {'max_burst_s': 2,\n    'rate': 2,\n    'requests': [[644, 4],\n                 [886, 4],\n                 [910, 3],\n                 [1485, 1],\n                 [1585, 2],\n                 [1776, 4],\n                 [2163, 2],\n                 [2628, 3],\n                 [2698, 2]]},\n   [[0, 1114, 3090, 4015, 4415, 5224, 6837, 7372, 8802], '0', '12500']]],\n [['pay later for big request',\n   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [104, 1], [5000, 1]]},\n   [[0, 2000, 2096, 0], '0', '5200']],\n  ['stored permits capped',\n   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10004, 1]]},\n   [[0, 0, 500, 996], '0', '11500']],\n  ['stored permits consumed',\n   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3004, 1]]},\n   [[0, 0, 0, 496], '0', '3750']],\n  ['resync after idle',\n   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4004, 2], [4004, 4]]},\n   [[0, 0, 0, 0, 0], '3', '4004']],\n  ['fractional waits',\n   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [14, 1], [20, 2]]},\n   [[0, 334, 653, 980], '0', '5000/3']],\n  ['random acquires',\n   {'max_burst_s': 2,\n    'rate': 2,\n    'requests': [[106, 2],\n                 [1122, 1],\n                 [1604, 3],\n                 [1998, 1],\n                 [2099, 1],\n                 [2549, 2],\n                 [2752, 1],\n                 [2983, 1],\n                 [3690, 4]]},\n   [[0, 0, 0, 1002, 1401, 1451, 2248, 2517, 2310], '0', '8000']]],\n [['pay later for big request',\n   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [105, 1], [5000, 1]]},\n   [[0, 2000, 2095, 0], '0', '5200']],\n  ['stored permits capped',\n   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10005, 1]]},\n   [[0, 0, 500, 995], '0', '11500']],\n  ['stored permits consumed',\n   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3005, 1]]},\n   [[0, 0, 0, 495], '0', '3750']],\n  ['resync after idle',\n   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4005, 2], [4005, 4]]},\n   [[0, 0, 0, 0, 0], '3', '4005']],\n  ['fractional waits',\n   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [15, 1], [20, 2]]},\n   [[0, 334, 652, 980], '0', '5000/3']],\n  ['random acquires',\n   {'max_burst_s': 2,\n    'rate': 2,\n    'requests': [[2392, 4],\n                 [2748, 2],\n                 [3147, 1],\n                 [3291, 2],\n                 [3293, 2],\n                 [3431, 2],\n                 [3441, 1],\n                 [3672, 1],\n                 [3732, 4]]},\n   [[0, 0, 245, 601, 1599, 2461, 3451, 3720, 4160], '0', '9892']]]]\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-reservation-limiter-wait-rounding","generated_at":"2026-09-29T14:48:49.602498+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Client-side reservation limiters (as in smooth-bursty designs) let a large request proceed now and make the next caller wait; getting who pays wrong starves or floods the backend.","repair":"Round the wait up to whole milliseconds.","root_cause":"The fractional wait is truncated instead of rounded up.","sha256":"3a6bf490098f0c3010c9fa818b0c0a7af9ac49fb8a1913ff2ddcc924d767aa1b","title":"Reservation limiter with stored permits: wait truncated · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":41.511,"exit_code":1,"observations":[{"actual":[[0,2000,2099,0],"0","5200"],"check":"pay later for big request","expected":[[0,2000,2099,0],"0","5200"],"passed":true},{"actual":[[0,0,500,999],"0","11500"],"check":"stored permits capped","expected":[[0,0,500,999],"0","11500"],"passed":true},{"actual":[[0,0,0,499],"0","3750"],"check":"stored permits consumed","expected":[[0,0,0,499],"0","3750"],"passed":true},{"actual":[[0,0,0,0,0],"3","4001"],"check":"resync after idle","expected":[[0,0,0,0,0],"3","4001"],"passed":true},{"actual":[[0,333,656,980],"0","5000/3"],"check":"fractional waits","expected":[[0,334,656,980],"0","5000/3"],"passed":false},{"actual":[[0,352,2161,2910,4407,4911,5393,7059,7910],"0","12000"],"check":"random acquires","expected":[[0,352,2161,2910,4407,4911,5393,7059,7910],"0","12000"],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"pay later for big request\", \"actual\": [[0, 2000, 2099, 0], \"0\", \"5200\"], \"expected\": [[0, 2000, 2099, 0], \"0\", \"5200\"], \"passed\": true}, {\"check\": \"stored permits capped\", \"actual\": [[0, 0, 500, 999], \"0\", \"11500\"], \"expected\": [[0, 0, 500, 999], \"0\", \"11500\"], \"passed\": true}, {\"check\": \"stored permits consumed\", \"actual\": [[0, 0, 0, 499], \"0\", \"3750\"], \"expected\": [[0, 0, 0, 499], \"0\", \"3750\"], \"passed\": true}, {\"check\": \"resync after idle\", \"actual\": [[0, 0, 0, 0, 0], \"3\", \"4001\"], \"expected\": [[0, 0, 0, 0, 0], \"3\", \"4001\"], \"passed\": true}, {\"check\": \"fractional waits\", \"actual\": [[0, 333, 656, 980], \"0\", \"5000/3\"], \"expected\": [[0, 334, 656, 980], \"0\", \"5000/3\"], \"passed\": false}, {\"check\": \"random acquires\", \"actual\": [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], \"0\", \"12000\"], \"expected\": [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], \"0\", \"12000\"], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":40.445,"exit_code":1,"observations":[{"actual":[[0,2000,2099,0],"0","5200"],"check":"pay later for big request","expected":[[0,2000,2099,0],"0","5200"],"passed":true},{"actual":[[0,0,500,999],"0","11500"],"check":"stored permits capped","expected":[[0,0,500,999],"0","11500"],"passed":true},{"actual":[[0,0,0,499],"0","3750"],"check":"stored permits consumed","expected":[[0,0,0,499],"0","3750"],"passed":true},{"actual":[[0,0,0,0,0],"3","4001"],"check":"resync after idle","expected":[[0,0,0,0,0],"3","4001"],"passed":true},{"actual":[[0,333,655,980],"0","5000/3"],"check":"fractional waits","expected":[[0,334,656,980],"0","5000/3"],"passed":false},{"actual":[[0,352,2161,2910,4407,4911,5393,7059,7910],"0","12000"],"check":"random acquires","expected":[[0,352,2161,2910,4407,4911,5393,7059,7910],"0","12000"],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"pay later for big request\", \"actual\": [[0, 2000, 2099, 0], \"0\", \"5200\"], \"expected\": [[0, 2000, 2099, 0], \"0\", \"5200\"], \"passed\": true}, {\"check\": \"stored permits capped\", \"actual\": [[0, 0, 500, 999], \"0\", \"11500\"], \"expected\": [[0, 0, 500, 999], \"0\", \"11500\"], \"passed\": true}, {\"check\": \"stored permits consumed\", \"actual\": [[0, 0, 0, 499], \"0\", \"3750\"], \"expected\": [[0, 0, 0, 499], \"0\", \"3750\"], \"passed\": true}, {\"check\": \"resync after idle\", \"actual\": [[0, 0, 0, 0, 0], \"3\", \"4001\"], \"expected\": [[0, 0, 0, 0, 0], \"3\", \"4001\"], \"passed\": true}, {\"check\": \"fractional waits\", \"actual\": [[0, 333, 655, 980], \"0\", \"5000/3\"], \"expected\": [[0, 334, 656, 980], \"0\", \"5000/3\"], \"passed\": false}, {\"check\": \"random acquires\", \"actual\": [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], \"0\", \"12000\"], \"expected\": [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], \"0\", \"12000\"], \"passed\": true}], \"passed\": false}\n"},"fixed":{"elapsed_ms":43.681,"exit_code":0,"observations":[{"actual":[[0,2000,2099,0],"0","5200"],"check":"pay later for big request","expected":[[0,2000,2099,0],"0","5200"],"passed":true},{"actual":[[0,0,500,999],"0","11500"],"check":"stored permits capped","expected":[[0,0,500,999],"0","11500"],"passed":true},{"actual":[[0,0,0,499],"0","3750"],"check":"stored permits consumed","expected":[[0,0,0,499],"0","3750"],"passed":true},{"actual":[[0,0,0,0,0],"3","4001"],"check":"resync after idle","expected":[[0,0,0,0,0],"3","4001"],"passed":true},{"actual":[[0,334,656,980],"0","5000/3"],"check":"fractional waits","expected":[[0,334,656,980],"0","5000/3"],"passed":true},{"actual":[[0,352,2161,2910,4407,4911,5393,7059,7910],"0","12000"],"check":"random acquires","expected":[[0,352,2161,2910,4407,4911,5393,7059,7910],"0","12000"],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"pay later for big request\", \"actual\": [[0, 2000, 2099, 0], \"0\", \"5200\"], \"expected\": [[0, 2000, 2099, 0], \"0\", \"5200\"], \"passed\": true}, {\"check\": \"stored permits capped\", \"actual\": [[0, 0, 500, 999], \"0\", \"11500\"], \"expected\": [[0, 0, 500, 999], \"0\", \"11500\"], \"passed\": true}, {\"check\": \"stored permits consumed\", \"actual\": [[0, 0, 0, 499], \"0\", \"3750\"], \"expected\": [[0, 0, 0, 499], \"0\", \"3750\"], \"passed\": true}, {\"check\": \"resync after idle\", \"actual\": [[0, 0, 0, 0, 0], \"3\", \"4001\"], \"expected\": [[0, 0, 0, 0, 0], \"3\", \"4001\"], \"passed\": true}, {\"check\": \"fractional waits\", \"actual\": [[0, 334, 656, 980], \"0\", \"5000/3\"], \"expected\": [[0, 334, 656, 980], \"0\", \"5000/3\"], \"passed\": true}, {\"check\": \"random acquires\", \"actual\": [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], \"0\", \"12000\"], \"expected\": [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], \"0\", \"12000\"], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}