{"abstract":"Overdrawn clients start refilling from zero, so debt is never repaid.","category":"Rate limiter algorithms","checks":6,"contract":"Input {capacity, rate (tokens per second), max_debt, requests [[t_s, cost]]} with nondecreasing whole seconds. The bucket starts full; refill is min(capacity, tokens + elapsed*rate) and also repays debt. A request is admitted when the balance is positive and the post-charge balance stays >= -max_debt, so one expensive request may overdraw. Denials change nothing. Return [[decision, balance]].","evaluation_group":"w2-rate_limiter_algorithms-debt-bucket","failed_approach":"Freezing the balance while in debt means debt is never repaid.","family":"w2-rate_limiter_algorithms-debt-bucket-debt-repayment","id":"FA-73731","implementations":{"attempt":{"sha256":"b2ef8921ae19b0afe4cac85ecaf3a240ee8d4f011642a443b273be74684905af","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    cap = x['capacity']\n    rate = x['rate']\n    debt = x['max_debt']\n    tokens = cap\n    last = 0\n    out = []\n    for t, cost in x['requests']:\n        tokens = tokens if tokens < 0 else min(cap, tokens + (t - last) * rate)\n        last = t\n        if tokens > 0 and tokens - cost >= -debt:\n            tokens -= cost\n            out.append(['allow', tokens])\n        else:\n            out.append(['deny', tokens])\n    return out\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['overdraft then repay',\n   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [5, 2]]},\n   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]],\n  ['debt limit',\n   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 3]]},\n   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],\n  ['exactly zero balance',\n   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [3, 1]]},\n   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]],\n  ['refill repays debt',\n   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [6, 3]]},\n   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],\n  ['large cost at full balance',\n   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [22, 1]]},\n   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],\n  ['random costs',\n   {'capacity': 5,\n    'max_debt': 4,\n    'rate': 1,\n    'requests': [[0, 4], [3, 3], [3, 3], [5, 4], [5, 5], [6, 1], [8, 1], [9, 2], [12, 3]]},\n   [['allow', 1],\n    ['allow', 1],\n    ['allow', -2],\n    ['deny', 0],\n    ['deny', 0],\n    ['allow', 0],\n    ['allow', 1],\n    ['allow', 0],\n    ['allow', 0]]]],\n [['overdraft then repay',\n   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [6, 2]]},\n   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 1]]],\n  ['debt limit',\n   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 4]]},\n   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],\n  ['exactly zero balance',\n   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [4, 1]]},\n   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 1]]],\n  ['refill repays debt',\n   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [7, 3]]},\n   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],\n  ['large cost at full balance',\n   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [23, 1]]},\n   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],\n  ['random costs',\n   {'capacity': 5,\n    'max_debt': 4,\n    'rate': 1,\n    'requests': [[0, 4], [2, 1], [2, 2], [3, 5], [6, 1], [7, 4], [9, 5], [10, 2], [11, 4]]},\n   [['allow', 1],\n    ['allow', 2],\n    ['allow', 0],\n    ['allow', -4],\n    ['deny', -1],\n    ['deny', 0],\n    ['allow', -3],\n    ['deny', -2],\n    ['deny', -1]]]],\n [['overdraft then repay',\n   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [7, 2]]},\n   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 2]]],\n  ['debt limit',\n   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 5]]},\n   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],\n  ['exactly zero balance',\n   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [5, 1]]},\n   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],\n  ['refill repays debt',\n   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [8, 3]]},\n   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],\n  ['large cost at full balance',\n   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [24, 1]]},\n   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],\n  ['random costs',\n   {'capacity': 5,\n    'max_debt': 4,\n    'rate': 1,\n    'requests': [[2, 3], [2, 4], [3, 3], [4, 5], [10, 2], [10, 4], [10, 5], [11, 4], [12, 4]]},\n   [['allow', 2],\n    ['allow', -2],\n    ['deny', -1],\n    ['deny', 0],\n    ['allow', 3],\n    ['allow', -1],\n    ['deny', -1],\n    ['deny', 0],\n    ['allow', -3]]]],\n [['overdraft then repay',\n   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [8, 2]]},\n   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],\n  ['debt limit',\n   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 6]]},\n   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],\n  ['exactly zero balance',\n   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [6, 1]]},\n   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],\n  ['refill repays debt',\n   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [9, 3]]},\n   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],\n  ['large cost at full balance',\n   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [25, 1]]},\n   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],\n  ['random costs',\n   {'capacity': 5,\n    'max_debt': 4,\n    'rate': 1,\n    'requests': [[0, 1], [0, 2], [1, 5], [1, 5], [3, 1], [3, 2], [5, 2], [8, 4], [12, 2]]},\n   [['allow', 4],\n    ['allow', 2],\n    ['allow', -2],\n    ['deny', -2],\n    ['deny', 0],\n    ['deny', 0],\n    ['allow', 0],\n    ['allow', -1],\n    ['allow', 1]]]],\n [['overdraft then repay',\n   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [9, 2]]},\n   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],\n  ['debt limit',\n   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 7]]},\n   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],\n  ['exactly zero balance',\n   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [7, 1]]},\n   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],\n  ['refill repays debt',\n   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [10, 3]]},\n   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],\n  ['large cost at full balance',\n   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [26, 1]]},\n   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],\n  ['random costs',\n   {'capacity': 5,\n    'max_debt': 4,\n    'rate': 1,\n    'requests': [[1, 5], [3, 3], [3, 3], [5, 1], [5, 3], [7, 3], [8, 1], [8, 5], [12, 1]]},\n   [['allow', 0],\n    ['allow', -1],\n    ['deny', -1],\n    ['allow', 0],\n    ['deny', 0],\n    ['allow', -1],\n    ['deny', 0],\n    ['deny', 0],\n    ['allow', 3]]]]]\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":"7a74025a4bd41f465c738374162190a5a66bef2d562db2262e054856e3633a68","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    cap = x['capacity']\n    rate = x['rate']\n    debt = x['max_debt']\n    tokens = cap\n    last = 0\n    out = []\n    for t, cost in x['requests']:\n        tokens = min(cap, max(0, tokens) + (t - last) * rate)\n        last = t\n        if tokens > 0 and tokens - cost >= -debt:\n            tokens -= cost\n            out.append(['allow', tokens])\n        else:\n            out.append(['deny', tokens])\n    return out\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['overdraft then repay',\n   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [5, 2]]},\n   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]],\n  ['debt limit',\n   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 3]]},\n   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],\n  ['exactly zero balance',\n   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [3, 1]]},\n   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]],\n  ['refill repays debt',\n   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [6, 3]]},\n   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],\n  ['large cost at full balance',\n   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [22, 1]]},\n   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],\n  ['random costs',\n   {'capacity': 5,\n    'max_debt': 4,\n    'rate': 1,\n    'requests': [[0, 4], [3, 3], [3, 3], [5, 4], [5, 5], [6, 1], [8, 1], [9, 2], [12, 3]]},\n   [['allow', 1],\n    ['allow', 1],\n    ['allow', -2],\n    ['deny', 0],\n    ['deny', 0],\n    ['allow', 0],\n    ['allow', 1],\n    ['allow', 0],\n    ['allow', 0]]]],\n [['overdraft then repay',\n   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [6, 2]]},\n   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 1]]],\n  ['debt limit',\n   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 4]]},\n   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],\n  ['exactly zero balance',\n   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [4, 1]]},\n   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 1]]],\n  ['refill repays debt',\n   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [7, 3]]},\n   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],\n  ['large cost at full balance',\n   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [23, 1]]},\n   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],\n  ['random costs',\n   {'capacity': 5,\n    'max_debt': 4,\n    'rate': 1,\n    'requests': [[0, 4], [2, 1], [2, 2], [3, 5], [6, 1], [7, 4], [9, 5], [10, 2], [11, 4]]},\n   [['allow', 1],\n    ['allow', 2],\n    ['allow', 0],\n    ['allow', -4],\n    ['deny', -1],\n    ['deny', 0],\n    ['allow', -3],\n    ['deny', -2],\n    ['deny', -1]]]],\n [['overdraft then repay',\n   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [7, 2]]},\n   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 2]]],\n  ['debt limit',\n   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 5]]},\n   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],\n  ['exactly zero balance',\n   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [5, 1]]},\n   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],\n  ['refill repays debt',\n   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [8, 3]]},\n   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],\n  ['large cost at full balance',\n   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [24, 1]]},\n   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],\n  ['random costs',\n   {'capacity': 5,\n    'max_debt': 4,\n    'rate': 1,\n    'requests': [[2, 3], [2, 4], [3, 3], [4, 5], [10, 2], [10, 4], [10, 5], [11, 4], [12, 4]]},\n   [['allow', 2],\n    ['allow', -2],\n    ['deny', -1],\n    ['deny', 0],\n    ['allow', 3],\n    ['allow', -1],\n    ['deny', -1],\n    ['deny', 0],\n    ['allow', -3]]]],\n [['overdraft then repay',\n   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [8, 2]]},\n   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],\n  ['debt limit',\n   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 6]]},\n   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],\n  ['exactly zero balance',\n   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [6, 1]]},\n   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],\n  ['refill repays debt',\n   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [9, 3]]},\n   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],\n  ['large cost at full balance',\n   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [25, 1]]},\n   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],\n  ['random costs',\n   {'capacity': 5,\n    'max_debt': 4,\n    'rate': 1,\n    'requests': [[0, 1], [0, 2], [1, 5], [1, 5], [3, 1], [3, 2], [5, 2], [8, 4], [12, 2]]},\n   [['allow', 4],\n    ['allow', 2],\n    ['allow', -2],\n    ['deny', -2],\n    ['deny', 0],\n    ['deny', 0],\n    ['allow', 0],\n    ['allow', -1],\n    ['allow', 1]]]],\n [['overdraft then repay',\n   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [9, 2]]},\n   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],\n  ['debt limit',\n   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 7]]},\n   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],\n  ['exactly zero balance',\n   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [7, 1]]},\n   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],\n  ['refill repays debt',\n   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [10, 3]]},\n   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],\n  ['large cost at full balance',\n   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [26, 1]]},\n   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],\n  ['random costs',\n   {'capacity': 5,\n    'max_debt': 4,\n    'rate': 1,\n    'requests': [[1, 5], [3, 3], [3, 3], [5, 1], [5, 3], [7, 3], [8, 1], [8, 5], [12, 1]]},\n   [['allow', 0],\n    ['allow', -1],\n    ['deny', -1],\n    ['allow', 0],\n    ['deny', 0],\n    ['allow', -1],\n    ['deny', 0],\n    ['deny', 0],\n    ['allow', 3]]]]]\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":"2602f882f7b7bf23e6db51fd290fa8c43c184915e7d9678a08ed13f42d8ff70f","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    cap = x['capacity']\n    rate = x['rate']\n    debt = x['max_debt']\n    tokens = cap\n    last = 0\n    out = []\n    for t, cost in x['requests']:\n        tokens = min(cap, tokens + (t - last) * rate)\n        last = t\n        if tokens > 0 and tokens - cost >= -debt:\n            tokens -= cost\n            out.append(['allow', tokens])\n        else:\n            out.append(['deny', tokens])\n    return out\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['overdraft then repay',\n   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [5, 2]]},\n   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 0]]],\n  ['debt limit',\n   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 3]]},\n   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],\n  ['exactly zero balance',\n   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [3, 1]]},\n   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 0]]],\n  ['refill repays debt',\n   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [6, 3]]},\n   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],\n  ['large cost at full balance',\n   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [22, 1]]},\n   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],\n  ['random costs',\n   {'capacity': 5,\n    'max_debt': 4,\n    'rate': 1,\n    'requests': [[0, 4], [3, 3], [3, 3], [5, 4], [5, 5], [6, 1], [8, 1], [9, 2], [12, 3]]},\n   [['allow', 1],\n    ['allow', 1],\n    ['allow', -2],\n    ['deny', 0],\n    ['deny', 0],\n    ['allow', 0],\n    ['allow', 1],\n    ['allow', 0],\n    ['allow', 0]]]],\n [['overdraft then repay',\n   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [6, 2]]},\n   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 1]]],\n  ['debt limit',\n   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 4]]},\n   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],\n  ['exactly zero balance',\n   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [4, 1]]},\n   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 1]]],\n  ['refill repays debt',\n   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [7, 3]]},\n   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],\n  ['large cost at full balance',\n   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [23, 1]]},\n   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],\n  ['random costs',\n   {'capacity': 5,\n    'max_debt': 4,\n    'rate': 1,\n    'requests': [[0, 4], [2, 1], [2, 2], [3, 5], [6, 1], [7, 4], [9, 5], [10, 2], [11, 4]]},\n   [['allow', 1],\n    ['allow', 2],\n    ['allow', 0],\n    ['allow', -4],\n    ['deny', -1],\n    ['deny', 0],\n    ['allow', -3],\n    ['deny', -2],\n    ['deny', -1]]]],\n [['overdraft then repay',\n   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [7, 2]]},\n   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 2]]],\n  ['debt limit',\n   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 5]]},\n   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],\n  ['exactly zero balance',\n   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [5, 1]]},\n   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],\n  ['refill repays debt',\n   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [8, 3]]},\n   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],\n  ['large cost at full balance',\n   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [24, 1]]},\n   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],\n  ['random costs',\n   {'capacity': 5,\n    'max_debt': 4,\n    'rate': 1,\n    'requests': [[2, 3], [2, 4], [3, 3], [4, 5], [10, 2], [10, 4], [10, 5], [11, 4], [12, 4]]},\n   [['allow', 2],\n    ['allow', -2],\n    ['deny', -1],\n    ['deny', 0],\n    ['allow', 3],\n    ['allow', -1],\n    ['deny', -1],\n    ['deny', 0],\n    ['allow', -3]]]],\n [['overdraft then repay',\n   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [8, 2]]},\n   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],\n  ['debt limit',\n   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 6]]},\n   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],\n  ['exactly zero balance',\n   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [6, 1]]},\n   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],\n  ['refill repays debt',\n   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [9, 3]]},\n   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],\n  ['large cost at full balance',\n   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [25, 1]]},\n   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],\n  ['random costs',\n   {'capacity': 5,\n    'max_debt': 4,\n    'rate': 1,\n    'requests': [[0, 1], [0, 2], [1, 5], [1, 5], [3, 1], [3, 2], [5, 2], [8, 4], [12, 2]]},\n   [['allow', 4],\n    ['allow', 2],\n    ['allow', -2],\n    ['deny', -2],\n    ['deny', 0],\n    ['deny', 0],\n    ['allow', 0],\n    ['allow', -1],\n    ['allow', 1]]]],\n [['overdraft then repay',\n   {'capacity': 5, 'max_debt': 4, 'rate': 1, 'requests': [[0, 3], [0, 4], [1, 1], [3, 1], [9, 2]]},\n   [['allow', 2], ['allow', -2], ['deny', -1], ['allow', 0], ['allow', 3]]],\n  ['debt limit',\n   {'capacity': 4, 'max_debt': 3, 'rate': 2, 'requests': [[0, 2], [0, 5], [1, 1], [1, 7]]},\n   [['allow', 2], ['allow', -3], ['deny', -1], ['deny', -1]]],\n  ['exactly zero balance',\n   {'capacity': 3, 'max_debt': 5, 'rate': 1, 'requests': [[0, 3], [0, 1], [1, 2], [7, 1]]},\n   [['allow', 0], ['deny', 0], ['allow', -1], ['allow', 2]]],\n  ['refill repays debt',\n   {'capacity': 6, 'max_debt': 6, 'rate': 2, 'requests': [[0, 10], [2, 1], [3, 1], [10, 3]]},\n   [['allow', -4], ['deny', 0], ['allow', 1], ['allow', 3]]],\n  ['large cost at full balance',\n   {'capacity': 2, 'max_debt': 10, 'rate': 1, 'requests': [[0, 9], [20, 13], [20, 1], [26, 1]]},\n   [['allow', -7], ['deny', 2], ['allow', 1], ['allow', 1]]],\n  ['random costs',\n   {'capacity': 5,\n    'max_debt': 4,\n    'rate': 1,\n    'requests': [[1, 5], [3, 3], [3, 3], [5, 1], [5, 3], [7, 3], [8, 1], [8, 5], [12, 1]]},\n   [['allow', 0],\n    ['allow', -1],\n    ['deny', -1],\n    ['allow', 0],\n    ['deny', 0],\n    ['allow', -1],\n    ['deny', 0],\n    ['deny', 0],\n    ['allow', 3]]]]]\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-debt-bucket-debt-repayment","generated_at":"2026-09-29T14:48:50.210351+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Cost-weighted APIs (query units, LLM tokens) let an expensive call overdraw the bucket and repay it from future refill; the overdraft rules decide fairness between cheap and expensive callers.","repair":"Refill from the actual, possibly negative, balance.","root_cause":"Negative balances are reset to zero before refill.","sha256":"3e7dcc4debf2fd786bfe144071e5a59df50f0b91f093fac7cebfafbf6bc6fa6b","title":"Token bucket with bounded overdraft: refill forgives outstanding debt · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verification":{"attempt":{"elapsed_ms":39.573,"exit_code":1,"observations":[{"actual":[["allow",2],["allow",-2],["deny",-2],["deny",-2],["deny",-2]],"check":"overdraft then repay","expected":[["allow",2],["allow",-2],["deny",-1],["allow",0],["allow",0]],"passed":false},{"actual":[["allow",2],["allow",-3],["deny",-3],["deny",-3]],"check":"debt limit","expected":[["allow",2],["allow",-3],["deny",-1],["deny",-1]],"passed":false},{"actual":[["allow",0],["deny",0],["allow",-1],["deny",-1]],"check":"exactly zero balance","expected":[["allow",0],["deny",0],["allow",-1],["allow",0]],"passed":false},{"actual":[["allow",-4],["deny",-4],["deny",-4],["deny",-4]],"check":"refill repays debt","expected":[["allow",-4],["deny",0],["allow",1],["allow",3]],"passed":false},{"actual":[["allow",-7],["deny",-7],["deny",-7],["deny",-7]],"check":"large cost at full balance","expected":[["allow",-7],["deny",2],["allow",1],["allow",1]],"passed":false},{"actual":[["allow",1],["allow",1],["allow",-2],["deny",-2],["deny",-2],["deny",-2],["deny",-2],["deny",-2],["deny",-2]],"check":"random costs","expected":[["allow",1],["allow",1],["allow",-2],["deny",0],["deny",0],["allow",0],["allow",1],["allow",0],["allow",0]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"overdraft then repay\", \"actual\": [[\"allow\", 2], [\"allow\", -2], [\"deny\", -2], [\"deny\", -2], [\"deny\", -2]], \"expected\": [[\"allow\", 2], [\"allow\", -2], [\"deny\", -1], [\"allow\", 0], [\"allow\", 0]], \"passed\": false}, {\"check\": \"debt limit\", \"actual\": [[\"allow\", 2], [\"allow\", -3], [\"deny\", -3], [\"deny\", -3]], \"expected\": [[\"allow\", 2], [\"allow\", -3], [\"deny\", -1], [\"deny\", -1]], \"passed\": false}, {\"check\": \"exactly zero balance\", \"actual\": [[\"allow\", 0], [\"deny\", 0], [\"allow\", -1], [\"deny\", -1]], \"expected\": [[\"allow\", 0], [\"deny\", 0], [\"allow\", -1], [\"allow\", 0]], \"passed\": false}, {\"check\": \"refill repays debt\", \"actual\": [[\"allow\", -4], [\"deny\", -4], [\"deny\", -4], [\"deny\", -4]], \"expected\": [[\"allow\", -4], [\"deny\", 0], [\"allow\", 1], [\"allow\", 3]], \"passed\": false}, {\"check\": \"large cost at full balance\", \"actual\": [[\"allow\", -7], [\"deny\", -7], [\"deny\", -7], [\"deny\", -7]], \"expected\": [[\"allow\", -7], [\"deny\", 2], [\"allow\", 1], [\"allow\", 1]], \"passed\": false}, {\"check\": \"random costs\", \"actual\": [[\"allow\", 1], [\"allow\", 1], [\"allow\", -2], [\"deny\", -2], [\"deny\", -2], [\"deny\", -2], [\"deny\", -2], [\"deny\", -2], [\"deny\", -2]], \"expected\": [[\"allow\", 1], [\"allow\", 1], [\"allow\", -2], [\"deny\", 0], [\"deny\", 0], [\"allow\", 0], [\"allow\", 1], [\"allow\", 0], [\"allow\", 0]], \"passed\": false}], \"passed\": false}\n"},"broken":{"elapsed_ms":39.089,"exit_code":1,"observations":[{"actual":[["allow",2],["allow",-2],["allow",0],["allow",1],["allow",1]],"check":"overdraft then repay","expected":[["allow",2],["allow",-2],["deny",-1],["allow",0],["allow",0]],"passed":false},{"actual":[["allow",2],["allow",-3],["allow",1],["allow",-2]],"check":"debt limit","expected":[["allow",2],["allow",-3],["deny",-1],["deny",-1]],"passed":false},{"actual":[["allow",0],["deny",0],["allow",-1],["allow",1]],"check":"exactly zero balance","expected":[["allow",0],["deny",0],["allow",-1],["allow",0]],"passed":false},{"actual":[["allow",-4],["allow",3],["allow",4],["allow",3]],"check":"refill repays debt","expected":[["allow",-4],["deny",0],["allow",1],["allow",3]],"passed":false},{"actual":[["allow",-7],["deny",2],["allow",1],["allow",1]],"check":"large cost at full balance","expected":[["allow",-7],["deny",2],["allow",1],["allow",1]],"passed":true},{"actual":[["allow",1],["allow",1],["allow",-2],["allow",-2],["deny",0],["allow",0],["allow",1],["allow",0],["allow",0]],"check":"random costs","expected":[["allow",1],["allow",1],["allow",-2],["deny",0],["deny",0],["allow",0],["allow",1],["allow",0],["allow",0]],"passed":false}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"overdraft then repay\", \"actual\": [[\"allow\", 2], [\"allow\", -2], [\"allow\", 0], [\"allow\", 1], [\"allow\", 1]], \"expected\": [[\"allow\", 2], [\"allow\", -2], [\"deny\", -1], [\"allow\", 0], [\"allow\", 0]], \"passed\": false}, {\"check\": \"debt limit\", \"actual\": [[\"allow\", 2], [\"allow\", -3], [\"allow\", 1], [\"allow\", -2]], \"expected\": [[\"allow\", 2], [\"allow\", -3], [\"deny\", -1], [\"deny\", -1]], \"passed\": false}, {\"check\": \"exactly zero balance\", \"actual\": [[\"allow\", 0], [\"deny\", 0], [\"allow\", -1], [\"allow\", 1]], \"expected\": [[\"allow\", 0], [\"deny\", 0], [\"allow\", -1], [\"allow\", 0]], \"passed\": false}, {\"check\": \"refill repays debt\", \"actual\": [[\"allow\", -4], [\"allow\", 3], [\"allow\", 4], [\"allow\", 3]], \"expected\": [[\"allow\", -4], [\"deny\", 0], [\"allow\", 1], [\"allow\", 3]], \"passed\": false}, {\"check\": \"large cost at full balance\", \"actual\": [[\"allow\", -7], [\"deny\", 2], [\"allow\", 1], [\"allow\", 1]], \"expected\": [[\"allow\", -7], [\"deny\", 2], [\"allow\", 1], [\"allow\", 1]], \"passed\": true}, {\"check\": \"random costs\", \"actual\": [[\"allow\", 1], [\"allow\", 1], [\"allow\", -2], [\"allow\", -2], [\"deny\", 0], [\"allow\", 0], [\"allow\", 1], [\"allow\", 0], [\"allow\", 0]], \"expected\": [[\"allow\", 1], [\"allow\", 1], [\"allow\", -2], [\"deny\", 0], [\"deny\", 0], [\"allow\", 0], [\"allow\", 1], [\"allow\", 0], [\"allow\", 0]], \"passed\": false}], \"passed\": false}\n"},"fixed":{"elapsed_ms":40.467,"exit_code":0,"observations":[{"actual":[["allow",2],["allow",-2],["deny",-1],["allow",0],["allow",0]],"check":"overdraft then repay","expected":[["allow",2],["allow",-2],["deny",-1],["allow",0],["allow",0]],"passed":true},{"actual":[["allow",2],["allow",-3],["deny",-1],["deny",-1]],"check":"debt limit","expected":[["allow",2],["allow",-3],["deny",-1],["deny",-1]],"passed":true},{"actual":[["allow",0],["deny",0],["allow",-1],["allow",0]],"check":"exactly zero balance","expected":[["allow",0],["deny",0],["allow",-1],["allow",0]],"passed":true},{"actual":[["allow",-4],["deny",0],["allow",1],["allow",3]],"check":"refill repays debt","expected":[["allow",-4],["deny",0],["allow",1],["allow",3]],"passed":true},{"actual":[["allow",-7],["deny",2],["allow",1],["allow",1]],"check":"large cost at full balance","expected":[["allow",-7],["deny",2],["allow",1],["allow",1]],"passed":true},{"actual":[["allow",1],["allow",1],["allow",-2],["deny",0],["deny",0],["allow",0],["allow",1],["allow",0],["allow",0]],"check":"random costs","expected":[["allow",1],["allow",1],["allow",-2],["deny",0],["deny",0],["allow",0],["allow",1],["allow",0],["allow",0]],"passed":true}],"passed":true,"stderr":"","stdout":"{\"observations\": [{\"check\": \"overdraft then repay\", \"actual\": [[\"allow\", 2], [\"allow\", -2], [\"deny\", -1], [\"allow\", 0], [\"allow\", 0]], \"expected\": [[\"allow\", 2], [\"allow\", -2], [\"deny\", -1], [\"allow\", 0], [\"allow\", 0]], \"passed\": true}, {\"check\": \"debt limit\", \"actual\": [[\"allow\", 2], [\"allow\", -3], [\"deny\", -1], [\"deny\", -1]], \"expected\": [[\"allow\", 2], [\"allow\", -3], [\"deny\", -1], [\"deny\", -1]], \"passed\": true}, {\"check\": \"exactly zero balance\", \"actual\": [[\"allow\", 0], [\"deny\", 0], [\"allow\", -1], [\"allow\", 0]], \"expected\": [[\"allow\", 0], [\"deny\", 0], [\"allow\", -1], [\"allow\", 0]], \"passed\": true}, {\"check\": \"refill repays debt\", \"actual\": [[\"allow\", -4], [\"deny\", 0], [\"allow\", 1], [\"allow\", 3]], \"expected\": [[\"allow\", -4], [\"deny\", 0], [\"allow\", 1], [\"allow\", 3]], \"passed\": true}, {\"check\": \"large cost at full balance\", \"actual\": [[\"allow\", -7], [\"deny\", 2], [\"allow\", 1], [\"allow\", 1]], \"expected\": [[\"allow\", -7], [\"deny\", 2], [\"allow\", 1], [\"allow\", 1]], \"passed\": true}, {\"check\": \"random costs\", \"actual\": [[\"allow\", 1], [\"allow\", 1], [\"allow\", -2], [\"deny\", 0], [\"deny\", 0], [\"allow\", 0], [\"allow\", 1], [\"allow\", 0], [\"allow\", 0]], \"expected\": [[\"allow\", 1], [\"allow\", 1], [\"allow\", -2], [\"deny\", 0], [\"deny\", 0], [\"allow\", 0], [\"allow\", 1], [\"allow\", 0], [\"allow\", 0]], \"passed\": true}], \"passed\": true}\n"}},"verified":true,"visibility":"public"}