{"abstract":"Releasing an already expired lease is reported as a successful release.","category":"Rate limiter algorithms","checks":6,"contract":"Input {max_concurrent, lease_ms, events [[t, op, id]]}. Before every event, leases with start + lease_ms <= t expire. acquire returns \"duplicate\" (no change) for a held id, \"granted\" (recording t) when fewer than max_concurrent leases are held, else \"rejected\". release returns \"released\" for a held id and \"unknown\" otherwise, changing nothing. Return [results, sorted held ids].","contract_signature":"x","evaluation_group":"w2-rate_limiter_algorithms-concurrency-leases","failed_approach":"Exempting the event's own id from expiry lets an expired holder release or re-acquire as if it still held the slot.","family":"w2-rate_limiter_algorithms-concurrency-leases-expiry-scope","id":"FA-73596","implementations":{"attempt":{"sha256":"cf76c6aeda4b6d60b86afdcb723209107f5c3ce7bd33b15c9b1866ec6ad5b3c1","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    cap = x['max_concurrent']\n    D = x['lease_ms']\n    held = {}\n    out = []\n    for t, op, ident in x['events']:\n        for k in [k for k, s in held.items() if s + D <= t and k != ident]:\n            del held[k]\n        if op == 'acquire':\n            if ident in held:\n                out.append('duplicate')\n            elif len(held) < cap:\n                held[ident] = t\n                out.append('granted')\n            else:\n                out.append('rejected')\n        else:\n            if ident in held:\n                del held[ident]\n                out.append('released')\n            else:\n                out.append('unknown')\n    return [out, sorted(held)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['lease expires exactly',\n   {'events': [[0, 'acquire', 'a'],\n               [999, 'acquire', 'b'],\n               [1000, 'acquire', 'b'],\n               [1501, 'release', 'b']],\n    'lease_ms': 1000,\n    'max_concurrent': 1},\n   [['granted', 'rejected', 'granted', 'released'], []]],\n  ['unknown release',\n   {'events': [[0, 'acquire', 'a'],\n               [10, 'acquire', 'b'],\n               [20, 'release', 'zz'],\n               [30, 'acquire', 'c'],\n               [41, 'release', 'a']],\n    'lease_ms': 5000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],\n  ['duplicate acquire',\n   {'events': [[0, 'acquire', 'a'],\n               [800, 'acquire', 'a'],\n               [1001, 'acquire', 'b'],\n               [1100, 'acquire', 'c']],\n    'lease_ms': 1000,\n    'max_concurrent': 2},\n   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],\n  ['release after expiry',\n   {'events': [[0, 'acquire', 'a'], [301, 'release', 'a'], [302, 'acquire', 'b']],\n    'lease_ms': 300,\n    'max_concurrent': 1},\n   [['granted', 'unknown', 'granted'], ['b']]],\n  ['random leases',\n   {'events': [[8, 'acquire', 'b'],\n               [172, 'acquire', 'c'],\n               [317, 'acquire', 'd'],\n               [462, 'acquire', 'a'],\n               [606, 'acquire', 'c'],\n               [769, 'acquire', 'd'],\n               [900, 'acquire', 'a'],\n               [1064, 'release', 'a'],\n               [1238, 'release', 'b'],\n               [1372, 'acquire', 'c'],\n               [1516, 'acquire', 'c'],\n               [1668, 'acquire', 'd']],\n    'lease_ms': 600,\n    'max_concurrent': 2},\n   [['granted',\n     'granted',\n     'rejected',\n     'rejected',\n     'duplicate',\n     'granted',\n     'granted',\n     'released',\n     'unknown',\n     'granted',\n     'duplicate',\n     'granted'],\n    ['c', 'd']]],\n  ['full pool',\n   {'events': [[0, 'acquire', 'a'],\n               [1, 'acquire', 'b'],\n               [2, 'acquire', 'c'],\n               [3, 'release', 'a'],\n               [5, 'acquire', 'c']],\n    'lease_ms': 10000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],\n [['lease expires exactly',\n   {'events': [[0, 'acquire', 'a'],\n               [999, 'acquire', 'b'],\n               [1000, 'acquire', 'b'],\n               [1502, 'release', 'b']],\n    'lease_ms': 1000,\n    'max_concurrent': 1},\n   [['granted', 'rejected', 'granted', 'released'], []]],\n  ['unknown release',\n   {'events': [[0, 'acquire', 'a'],\n               [10, 'acquire', 'b'],\n               [20, 'release', 'zz'],\n               [30, 'acquire', 'c'],\n               [42, 'release', 'a']],\n    'lease_ms': 5000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],\n  ['duplicate acquire',\n   {'events': [[0, 'acquire', 'a'],\n               [800, 'acquire', 'a'],\n               [1002, 'acquire', 'b'],\n               [1100, 'acquire', 'c']],\n    'lease_ms': 1000,\n    'max_concurrent': 2},\n   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],\n  ['release after expiry',\n   {'events': [[0, 'acquire', 'a'], [302, 'release', 'a'], [303, 'acquire', 'b']],\n    'lease_ms': 300,\n    'max_concurrent': 1},\n   [['granted', 'unknown', 'granted'], ['b']]],\n  ['random leases',\n   {'events': [[20, 'acquire', 'a'],\n               [161, 'acquire', 'a'],\n               [304, 'release', 'b'],\n               [482, 'acquire', 'c'],\n               [635, 'acquire', 'b'],\n               [780, 'acquire', 'd'],\n               [922, 'release', 'c'],\n               [1055, 'acquire', 'a'],\n               [1209, 'release', 'b'],\n               [1366, 'release', 'a'],\n               [1534, 'acquire', 'a'],\n               [1689, 'acquire', 'b']],\n    'lease_ms': 600,\n    'max_concurrent': 2},\n   [['granted',\n     'duplicate',\n     'unknown',\n     'granted',\n     'granted',\n     'rejected',\n     'released',\n     'granted',\n     'released',\n     'released',\n     'granted',\n     'granted'],\n    ['a', 'b']]],\n  ['full pool',\n   {'events': [[0, 'acquire', 'a'],\n               [1, 'acquire', 'b'],\n               [2, 'acquire', 'c'],\n               [3, 'release', 'a'],\n               [6, 'acquire', 'c']],\n    'lease_ms': 10000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],\n [['lease expires exactly',\n   {'events': [[0, 'acquire', 'a'],\n               [999, 'acquire', 'b'],\n               [1000, 'acquire', 'b'],\n               [1503, 'release', 'b']],\n    'lease_ms': 1000,\n    'max_concurrent': 1},\n   [['granted', 'rejected', 'granted', 'released'], []]],\n  ['unknown release',\n   {'events': [[0, 'acquire', 'a'],\n               [10, 'acquire', 'b'],\n               [20, 'release', 'zz'],\n               [30, 'acquire', 'c'],\n               [43, 'release', 'a']],\n    'lease_ms': 5000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],\n  ['duplicate acquire',\n   {'events': [[0, 'acquire', 'a'],\n               [800, 'acquire', 'a'],\n               [1003, 'acquire', 'b'],\n               [1100, 'acquire', 'c']],\n    'lease_ms': 1000,\n    'max_concurrent': 2},\n   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],\n  ['release after expiry',\n   {'events': [[0, 'acquire', 'a'], [303, 'release', 'a'], [304, 'acquire', 'b']],\n    'lease_ms': 300,\n    'max_concurrent': 1},\n   [['granted', 'unknown', 'granted'], ['b']]],\n  ['random leases',\n   {'events': [[7, 'acquire', 'a'],\n               [186, 'release', 'a'],\n               [319, 'acquire', 'a'],\n               [456, 'acquire', 'c'],\n               [610, 'acquire', 'a'],\n               [778, 'acquire', 'd'],\n               [935, 'acquire', 'c'],\n               [1055, 'acquire', 'a'],\n               [1219, 'release', 'a'],\n               [1368, 'acquire', 'b'],\n               [1500, 'acquire', 'a'],\n               [1677, 'acquire', 'b']],\n    'lease_ms': 600,\n    'max_concurrent': 2},\n   [['granted',\n     'released',\n     'granted',\n     'granted',\n     'duplicate',\n     'rejected',\n     'duplicate',\n     'granted',\n     'released',\n     'granted',\n     'granted',\n     'duplicate'],\n    ['a', 'b']]],\n  ['full pool',\n   {'events': [[0, 'acquire', 'a'],\n               [1, 'acquire', 'b'],\n               [2, 'acquire', 'c'],\n               [3, 'release', 'a'],\n               [7, 'acquire', 'c']],\n    'lease_ms': 10000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],\n [['lease expires exactly',\n   {'events': [[0, 'acquire', 'a'],\n               [999, 'acquire', 'b'],\n               [1000, 'acquire', 'b'],\n               [1504, 'release', 'b']],\n    'lease_ms': 1000,\n    'max_concurrent': 1},\n   [['granted', 'rejected', 'granted', 'released'], []]],\n  ['unknown release',\n   {'events': [[0, 'acquire', 'a'],\n               [10, 'acquire', 'b'],\n               [20, 'release', 'zz'],\n               [30, 'acquire', 'c'],\n               [44, 'release', 'a']],\n    'lease_ms': 5000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],\n  ['duplicate acquire',\n   {'events': [[0, 'acquire', 'a'],\n               [800, 'acquire', 'a'],\n               [1004, 'acquire', 'b'],\n               [1100, 'acquire', 'c']],\n    'lease_ms': 1000,\n    'max_concurrent': 2},\n   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],\n  ['release after expiry',\n   {'events': [[0, 'acquire', 'a'], [304, 'release', 'a'], [305, 'acquire', 'b']],\n    'lease_ms': 300,\n    'max_concurrent': 1},\n   [['granted', 'unknown', 'granted'], ['b']]],\n  ['random leases',\n   {'events': [[9, 'acquire', 'c'],\n               [172, 'acquire', 'd'],\n               [315, 'acquire', 'a'],\n               [473, 'acquire', 'a'],\n               [611, 'acquire', 'd'],\n               [785, 'acquire', 'c'],\n               [926, 'release', 'd'],\n               [1088, 'release', 'd'],\n               [1239, 'acquire', 'a'],\n               [1373, 'release', 'b'],\n               [1536, 'release', 'a'],\n               [1672, 'acquire', 'a']],\n    'lease_ms': 600,\n    'max_concurrent': 2},\n   [['granted',\n     'granted',\n     'rejected',\n     'rejected',\n     'duplicate',\n     'granted',\n     'unknown',\n     'unknown',\n     'granted',\n     'unknown',\n     'released',\n     'granted'],\n    ['a']]],\n  ['full pool',\n   {'events': [[0, 'acquire', 'a'],\n               [1, 'acquire', 'b'],\n               [2, 'acquire', 'c'],\n               [3, 'release', 'a'],\n               [8, 'acquire', 'c']],\n    'lease_ms': 10000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],\n [['lease expires exactly',\n   {'events': [[0, 'acquire', 'a'],\n               [999, 'acquire', 'b'],\n               [1000, 'acquire', 'b'],\n               [1505, 'release', 'b']],\n    'lease_ms': 1000,\n    'max_concurrent': 1},\n   [['granted', 'rejected', 'granted', 'released'], []]],\n  ['unknown release',\n   {'events': [[0, 'acquire', 'a'],\n               [10, 'acquire', 'b'],\n               [20, 'release', 'zz'],\n               [30, 'acquire', 'c'],\n               [45, 'release', 'a']],\n    'lease_ms': 5000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],\n  ['duplicate acquire',\n   {'events': [[0, 'acquire', 'a'],\n               [800, 'acquire', 'a'],\n               [1005, 'acquire', 'b'],\n               [1100, 'acquire', 'c']],\n    'lease_ms': 1000,\n    'max_concurrent': 2},\n   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],\n  ['release after expiry',\n   {'events': [[0, 'acquire', 'a'], [305, 'release', 'a'], [306, 'acquire', 'b']],\n    'lease_ms': 300,\n    'max_concurrent': 1},\n   [['granted', 'unknown', 'granted'], ['b']]],\n  ['random leases',\n   {'events': [[14, 'acquire', 'b'],\n               [177, 'release', 'a'],\n               [334, 'release', 'd'],\n               [476, 'acquire', 'a'],\n               [631, 'release', 'a'],\n               [764, 'acquire', 'b'],\n               [901, 'acquire', 'a'],\n               [1084, 'release', 'b'],\n               [1200, 'acquire', 'b'],\n               [1376, 'release', 'd'],\n               [1506, 'release', 'a'],\n               [1680, 'acquire', 'a']],\n    'lease_ms': 600,\n    'max_concurrent': 2},\n   [['granted',\n     'unknown',\n     'unknown',\n     'granted',\n     'released',\n     'granted',\n     'granted',\n     'released',\n     'granted',\n     'unknown',\n     'unknown',\n     'granted'],\n    ['a', 'b']]],\n  ['full pool',\n   {'events': [[0, 'acquire', 'a'],\n               [1, 'acquire', 'b'],\n               [2, 'acquire', 'c'],\n               [3, 'release', 'a'],\n               [9, 'acquire', 'c']],\n    'lease_ms': 10000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]]]\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":"e27e16739b5ab120c9d6e0da5e3799d819c1693e2a116d2c4965089b284c1bcd","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(x):\n    cap = x['max_concurrent']\n    D = x['lease_ms']\n    held = {}\n    out = []\n    for t, op, ident in x['events']:\n        if op == 'acquire':\n            for k in [k for k, s in held.items() if s + D <= t]:\n                del held[k]\n            if ident in held:\n                out.append('duplicate')\n            elif len(held) < cap:\n                held[ident] = t\n                out.append('granted')\n            else:\n                out.append('rejected')\n        else:\n            if ident in held:\n                del held[ident]\n                out.append('released')\n            else:\n                out.append('unknown')\n    return [out, sorted(held)]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = [[['lease expires exactly',\n   {'events': [[0, 'acquire', 'a'],\n               [999, 'acquire', 'b'],\n               [1000, 'acquire', 'b'],\n               [1501, 'release', 'b']],\n    'lease_ms': 1000,\n    'max_concurrent': 1},\n   [['granted', 'rejected', 'granted', 'released'], []]],\n  ['unknown release',\n   {'events': [[0, 'acquire', 'a'],\n               [10, 'acquire', 'b'],\n               [20, 'release', 'zz'],\n               [30, 'acquire', 'c'],\n               [41, 'release', 'a']],\n    'lease_ms': 5000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],\n  ['duplicate acquire',\n   {'events': [[0, 'acquire', 'a'],\n               [800, 'acquire', 'a'],\n               [1001, 'acquire', 'b'],\n               [1100, 'acquire', 'c']],\n    'lease_ms': 1000,\n    'max_concurrent': 2},\n   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],\n  ['release after expiry',\n   {'events': [[0, 'acquire', 'a'], [301, 'release', 'a'], [302, 'acquire', 'b']],\n    'lease_ms': 300,\n    'max_concurrent': 1},\n   [['granted', 'unknown', 'granted'], ['b']]],\n  ['random leases',\n   {'events': [[8, 'acquire', 'b'],\n               [172, 'acquire', 'c'],\n               [317, 'acquire', 'd'],\n               [462, 'acquire', 'a'],\n               [606, 'acquire', 'c'],\n               [769, 'acquire', 'd'],\n               [900, 'acquire', 'a'],\n               [1064, 'release', 'a'],\n               [1238, 'release', 'b'],\n               [1372, 'acquire', 'c'],\n               [1516, 'acquire', 'c'],\n               [1668, 'acquire', 'd']],\n    'lease_ms': 600,\n    'max_concurrent': 2},\n   [['granted',\n     'granted',\n     'rejected',\n     'rejected',\n     'duplicate',\n     'granted',\n     'granted',\n     'released',\n     'unknown',\n     'granted',\n     'duplicate',\n     'granted'],\n    ['c', 'd']]],\n  ['full pool',\n   {'events': [[0, 'acquire', 'a'],\n               [1, 'acquire', 'b'],\n               [2, 'acquire', 'c'],\n               [3, 'release', 'a'],\n               [5, 'acquire', 'c']],\n    'lease_ms': 10000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],\n [['lease expires exactly',\n   {'events': [[0, 'acquire', 'a'],\n               [999, 'acquire', 'b'],\n               [1000, 'acquire', 'b'],\n               [1502, 'release', 'b']],\n    'lease_ms': 1000,\n    'max_concurrent': 1},\n   [['granted', 'rejected', 'granted', 'released'], []]],\n  ['unknown release',\n   {'events': [[0, 'acquire', 'a'],\n               [10, 'acquire', 'b'],\n               [20, 'release', 'zz'],\n               [30, 'acquire', 'c'],\n               [42, 'release', 'a']],\n    'lease_ms': 5000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],\n  ['duplicate acquire',\n   {'events': [[0, 'acquire', 'a'],\n               [800, 'acquire', 'a'],\n               [1002, 'acquire', 'b'],\n               [1100, 'acquire', 'c']],\n    'lease_ms': 1000,\n    'max_concurrent': 2},\n   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],\n  ['release after expiry',\n   {'events': [[0, 'acquire', 'a'], [302, 'release', 'a'], [303, 'acquire', 'b']],\n    'lease_ms': 300,\n    'max_concurrent': 1},\n   [['granted', 'unknown', 'granted'], ['b']]],\n  ['random leases',\n   {'events': [[20, 'acquire', 'a'],\n               [161, 'acquire', 'a'],\n               [304, 'release', 'b'],\n               [482, 'acquire', 'c'],\n               [635, 'acquire', 'b'],\n               [780, 'acquire', 'd'],\n               [922, 'release', 'c'],\n               [1055, 'acquire', 'a'],\n               [1209, 'release', 'b'],\n               [1366, 'release', 'a'],\n               [1534, 'acquire', 'a'],\n               [1689, 'acquire', 'b']],\n    'lease_ms': 600,\n    'max_concurrent': 2},\n   [['granted',\n     'duplicate',\n     'unknown',\n     'granted',\n     'granted',\n     'rejected',\n     'released',\n     'granted',\n     'released',\n     'released',\n     'granted',\n     'granted'],\n    ['a', 'b']]],\n  ['full pool',\n   {'events': [[0, 'acquire', 'a'],\n               [1, 'acquire', 'b'],\n               [2, 'acquire', 'c'],\n               [3, 'release', 'a'],\n               [6, 'acquire', 'c']],\n    'lease_ms': 10000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],\n [['lease expires exactly',\n   {'events': [[0, 'acquire', 'a'],\n               [999, 'acquire', 'b'],\n               [1000, 'acquire', 'b'],\n               [1503, 'release', 'b']],\n    'lease_ms': 1000,\n    'max_concurrent': 1},\n   [['granted', 'rejected', 'granted', 'released'], []]],\n  ['unknown release',\n   {'events': [[0, 'acquire', 'a'],\n               [10, 'acquire', 'b'],\n               [20, 'release', 'zz'],\n               [30, 'acquire', 'c'],\n               [43, 'release', 'a']],\n    'lease_ms': 5000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],\n  ['duplicate acquire',\n   {'events': [[0, 'acquire', 'a'],\n               [800, 'acquire', 'a'],\n               [1003, 'acquire', 'b'],\n               [1100, 'acquire', 'c']],\n    'lease_ms': 1000,\n    'max_concurrent': 2},\n   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],\n  ['release after expiry',\n   {'events': [[0, 'acquire', 'a'], [303, 'release', 'a'], [304, 'acquire', 'b']],\n    'lease_ms': 300,\n    'max_concurrent': 1},\n   [['granted', 'unknown', 'granted'], ['b']]],\n  ['random leases',\n   {'events': [[7, 'acquire', 'a'],\n               [186, 'release', 'a'],\n               [319, 'acquire', 'a'],\n               [456, 'acquire', 'c'],\n               [610, 'acquire', 'a'],\n               [778, 'acquire', 'd'],\n               [935, 'acquire', 'c'],\n               [1055, 'acquire', 'a'],\n               [1219, 'release', 'a'],\n               [1368, 'acquire', 'b'],\n               [1500, 'acquire', 'a'],\n               [1677, 'acquire', 'b']],\n    'lease_ms': 600,\n    'max_concurrent': 2},\n   [['granted',\n     'released',\n     'granted',\n     'granted',\n     'duplicate',\n     'rejected',\n     'duplicate',\n     'granted',\n     'released',\n     'granted',\n     'granted',\n     'duplicate'],\n    ['a', 'b']]],\n  ['full pool',\n   {'events': [[0, 'acquire', 'a'],\n               [1, 'acquire', 'b'],\n               [2, 'acquire', 'c'],\n               [3, 'release', 'a'],\n               [7, 'acquire', 'c']],\n    'lease_ms': 10000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],\n [['lease expires exactly',\n   {'events': [[0, 'acquire', 'a'],\n               [999, 'acquire', 'b'],\n               [1000, 'acquire', 'b'],\n               [1504, 'release', 'b']],\n    'lease_ms': 1000,\n    'max_concurrent': 1},\n   [['granted', 'rejected', 'granted', 'released'], []]],\n  ['unknown release',\n   {'events': [[0, 'acquire', 'a'],\n               [10, 'acquire', 'b'],\n               [20, 'release', 'zz'],\n               [30, 'acquire', 'c'],\n               [44, 'release', 'a']],\n    'lease_ms': 5000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],\n  ['duplicate acquire',\n   {'events': [[0, 'acquire', 'a'],\n               [800, 'acquire', 'a'],\n               [1004, 'acquire', 'b'],\n               [1100, 'acquire', 'c']],\n    'lease_ms': 1000,\n    'max_concurrent': 2},\n   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],\n  ['release after expiry',\n   {'events': [[0, 'acquire', 'a'], [304, 'release', 'a'], [305, 'acquire', 'b']],\n    'lease_ms': 300,\n    'max_concurrent': 1},\n   [['granted', 'unknown', 'granted'], ['b']]],\n  ['random leases',\n   {'events': [[9, 'acquire', 'c'],\n               [172, 'acquire', 'd'],\n               [315, 'acquire', 'a'],\n               [473, 'acquire', 'a'],\n               [611, 'acquire', 'd'],\n               [785, 'acquire', 'c'],\n               [926, 'release', 'd'],\n               [1088, 'release', 'd'],\n               [1239, 'acquire', 'a'],\n               [1373, 'release', 'b'],\n               [1536, 'release', 'a'],\n               [1672, 'acquire', 'a']],\n    'lease_ms': 600,\n    'max_concurrent': 2},\n   [['granted',\n     'granted',\n     'rejected',\n     'rejected',\n     'duplicate',\n     'granted',\n     'unknown',\n     'unknown',\n     'granted',\n     'unknown',\n     'released',\n     'granted'],\n    ['a']]],\n  ['full pool',\n   {'events': [[0, 'acquire', 'a'],\n               [1, 'acquire', 'b'],\n               [2, 'acquire', 'c'],\n               [3, 'release', 'a'],\n               [8, 'acquire', 'c']],\n    'lease_ms': 10000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]],\n [['lease expires exactly',\n   {'events': [[0, 'acquire', 'a'],\n               [999, 'acquire', 'b'],\n               [1000, 'acquire', 'b'],\n               [1505, 'release', 'b']],\n    'lease_ms': 1000,\n    'max_concurrent': 1},\n   [['granted', 'rejected', 'granted', 'released'], []]],\n  ['unknown release',\n   {'events': [[0, 'acquire', 'a'],\n               [10, 'acquire', 'b'],\n               [20, 'release', 'zz'],\n               [30, 'acquire', 'c'],\n               [45, 'release', 'a']],\n    'lease_ms': 5000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'unknown', 'rejected', 'released'], ['b']]],\n  ['duplicate acquire',\n   {'events': [[0, 'acquire', 'a'],\n               [800, 'acquire', 'a'],\n               [1005, 'acquire', 'b'],\n               [1100, 'acquire', 'c']],\n    'lease_ms': 1000,\n    'max_concurrent': 2},\n   [['granted', 'duplicate', 'granted', 'granted'], ['b', 'c']]],\n  ['release after expiry',\n   {'events': [[0, 'acquire', 'a'], [305, 'release', 'a'], [306, 'acquire', 'b']],\n    'lease_ms': 300,\n    'max_concurrent': 1},\n   [['granted', 'unknown', 'granted'], ['b']]],\n  ['random leases',\n   {'events': [[14, 'acquire', 'b'],\n               [177, 'release', 'a'],\n               [334, 'release', 'd'],\n               [476, 'acquire', 'a'],\n               [631, 'release', 'a'],\n               [764, 'acquire', 'b'],\n               [901, 'acquire', 'a'],\n               [1084, 'release', 'b'],\n               [1200, 'acquire', 'b'],\n               [1376, 'release', 'd'],\n               [1506, 'release', 'a'],\n               [1680, 'acquire', 'a']],\n    'lease_ms': 600,\n    'max_concurrent': 2},\n   [['granted',\n     'unknown',\n     'unknown',\n     'granted',\n     'released',\n     'granted',\n     'granted',\n     'released',\n     'granted',\n     'unknown',\n     'unknown',\n     'granted'],\n    ['a', 'b']]],\n  ['full pool',\n   {'events': [[0, 'acquire', 'a'],\n               [1, 'acquire', 'b'],\n               [2, 'acquire', 'c'],\n               [3, 'release', 'a'],\n               [9, 'acquire', 'c']],\n    'lease_ms': 10000,\n    'max_concurrent': 2},\n   [['granted', 'granted', 'rejected', 'released', 'granted'], ['b', 'c']]]]]\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-concurrency-leases-expiry-scope","generated_at":"2026-09-29T14:48:48.966336+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Concurrency limiters for workers and database pools use leases so that crashed holders eventually free their slot; expiry and release bookkeeping determine whether slots leak or double-count.","root_cause":"Expired leases are reclaimed only when an acquire event arrives.","sha256":"74e800c5a70583597b09b1bfd1cba690d217ca0ff0474a0b6fec340f965979b2","title":"Concurrency limiter with expiring leases: expiry runs only on acquire · 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":39.477,"exit_code":1,"observations":[{"actual":[["granted","rejected","granted","released"],[]],"check":"lease expires exactly","expected":[["granted","rejected","granted","released"],[]],"passed":true},{"actual":[["granted","granted","unknown","rejected","released"],["b"]],"check":"unknown release","expected":[["granted","granted","unknown","rejected","released"],["b"]],"passed":true},{"actual":[["granted","duplicate","granted","granted"],["b","c"]],"check":"duplicate acquire","expected":[["granted","duplicate","granted","granted"],["b","c"]],"passed":true},{"actual":[["granted","released","granted"],["b"]],"check":"release after expiry","expected":[["granted","unknown","granted"],["b"]],"passed":false},{"actual":[["granted","granted","rejected","rejected","duplicate","granted","granted","released","unknown","granted","duplicate","granted"],["c","d"]],"check":"random leases","expected":[["granted","granted","rejected","rejected","duplicate","granted","granted","released","unknown","granted","duplicate","granted"],["c","d"]],"passed":true},{"actual":[["granted","granted","rejected","released","granted"],["b","c"]],"check":"full pool","expected":[["granted","granted","rejected","released","granted"],["b","c"]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"lease expires exactly\", \"actual\": [[\"granted\", \"rejected\", \"granted\", \"released\"], []], \"expected\": [[\"granted\", \"rejected\", \"granted\", \"released\"], []], \"passed\": true}, {\"check\": \"unknown release\", \"actual\": [[\"granted\", \"granted\", \"unknown\", \"rejected\", \"released\"], [\"b\"]], \"expected\": [[\"granted\", \"granted\", \"unknown\", \"rejected\", \"released\"], [\"b\"]], \"passed\": true}, {\"check\": \"duplicate acquire\", \"actual\": [[\"granted\", \"duplicate\", \"granted\", \"granted\"], [\"b\", \"c\"]], \"expected\": [[\"granted\", \"duplicate\", \"granted\", \"granted\"], [\"b\", \"c\"]], \"passed\": true}, {\"check\": \"release after expiry\", \"actual\": [[\"granted\", \"released\", \"granted\"], [\"b\"]], \"expected\": [[\"granted\", \"unknown\", \"granted\"], [\"b\"]], \"passed\": false}, {\"check\": \"random leases\", \"actual\": [[\"granted\", \"granted\", \"rejected\", \"rejected\", \"duplicate\", \"granted\", \"granted\", \"released\", \"unknown\", \"granted\", \"duplicate\", \"granted\"], [\"c\", \"d\"]], \"expected\": [[\"granted\", \"granted\", \"rejected\", \"rejected\", \"duplicate\", \"granted\", \"granted\", \"released\", \"unknown\", \"granted\", \"duplicate\", \"granted\"], [\"c\", \"d\"]], \"passed\": true}, {\"check\": \"full pool\", \"actual\": [[\"granted\", \"granted\", \"rejected\", \"released\", \"granted\"], [\"b\", \"c\"]], \"expected\": [[\"granted\", \"granted\", \"rejected\", \"released\", \"granted\"], [\"b\", \"c\"]], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":37.765,"exit_code":1,"observations":[{"actual":[["granted","rejected","granted","released"],[]],"check":"lease expires exactly","expected":[["granted","rejected","granted","released"],[]],"passed":true},{"actual":[["granted","granted","unknown","rejected","released"],["b"]],"check":"unknown release","expected":[["granted","granted","unknown","rejected","released"],["b"]],"passed":true},{"actual":[["granted","duplicate","granted","granted"],["b","c"]],"check":"duplicate acquire","expected":[["granted","duplicate","granted","granted"],["b","c"]],"passed":true},{"actual":[["granted","released","granted"],["b"]],"check":"release after expiry","expected":[["granted","unknown","granted"],["b"]],"passed":false},{"actual":[["granted","granted","rejected","rejected","duplicate","granted","granted","released","unknown","granted","duplicate","granted"],["c","d"]],"check":"random leases","expected":[["granted","granted","rejected","rejected","duplicate","granted","granted","released","unknown","granted","duplicate","granted"],["c","d"]],"passed":true},{"actual":[["granted","granted","rejected","released","granted"],["b","c"]],"check":"full pool","expected":[["granted","granted","rejected","released","granted"],["b","c"]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"lease expires exactly\", \"actual\": [[\"granted\", \"rejected\", \"granted\", \"released\"], []], \"expected\": [[\"granted\", \"rejected\", \"granted\", \"released\"], []], \"passed\": true}, {\"check\": \"unknown release\", \"actual\": [[\"granted\", \"granted\", \"unknown\", \"rejected\", \"released\"], [\"b\"]], \"expected\": [[\"granted\", \"granted\", \"unknown\", \"rejected\", \"released\"], [\"b\"]], \"passed\": true}, {\"check\": \"duplicate acquire\", \"actual\": [[\"granted\", \"duplicate\", \"granted\", \"granted\"], [\"b\", \"c\"]], \"expected\": [[\"granted\", \"duplicate\", \"granted\", \"granted\"], [\"b\", \"c\"]], \"passed\": true}, {\"check\": \"release after expiry\", \"actual\": [[\"granted\", \"released\", \"granted\"], [\"b\"]], \"expected\": [[\"granted\", \"unknown\", \"granted\"], [\"b\"]], \"passed\": false}, {\"check\": \"random leases\", \"actual\": [[\"granted\", \"granted\", \"rejected\", \"rejected\", \"duplicate\", \"granted\", \"granted\", \"released\", \"unknown\", \"granted\", \"duplicate\", \"granted\"], [\"c\", \"d\"]], \"expected\": [[\"granted\", \"granted\", \"rejected\", \"rejected\", \"duplicate\", \"granted\", \"granted\", \"released\", \"unknown\", \"granted\", \"duplicate\", \"granted\"], [\"c\", \"d\"]], \"passed\": true}, {\"check\": \"full pool\", \"actual\": [[\"granted\", \"granted\", \"rejected\", \"released\", \"granted\"], [\"b\", \"c\"]], \"expected\": [[\"granted\", \"granted\", \"rejected\", \"released\", \"granted\"], [\"b\", \"c\"]], \"passed\": true}], \"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."}}