Lab Robot Job Dispatcher with Backoff, Quarantine and Prereqs

A genomics lab runs sample-preparation steps (extraction, amplification, labeling, sequencing) on a pool of liquid-handling robots. Robots jam and runs get aborted, so a step that fails must be retried after a per-step backoff (time to clear the robot, reload reagents, and so on). Each step is a job in the dispatcher. A job that fails too many times is moved to a quarantine list and is never handed out again. Implement the dispatcher in memory. Time is passed in explicitly as an integer, and now never decreases across calls.

Part 1: Backoff and quarantine

class LabDispatcher:
    def __init__(self, max_failures: int): ...
    def submit(self, job_id: str, backoff: int, now: int) -> None: ...
    def claim(self, now: int) -> str | None: ...
    def report_failure(self, job_id: str, now: int) -> None: ...
    def quarantined(self) -> list[str]: ...

Rules:

• claim(now) returns the eligible job that was submitted earliest and marks it claimed, or None if nothing is eligible.
• report_failure applies only to a claimed job. The job's failure count goes up by one. If it reaches max_failures, the job goes to quarantine. Otherwise it becomes eligible again at now + backoff, where now is the failure time.
• A retried job keeps its original submission position: it is not moved to the back of the line.
• quarantined() lists jobs in the order they were quarantined.
• Reject duplicate ids, unknown ids, and failures reported for jobs that are not claimed.

d = LabDispatcher(max_failures=2)
submit("a", backoff=5, now=0); submit("b", backoff=3, now=1); submit("c", backoff=10, now=2)
claim(3) -> "a"      claim(3) -> "b"
report_failure("a", 4)          # a eligible again at 9
claim(5) -> "c"
report_failure("b", 6)          # b eligible again at 9
claim(8) -> None
claim(9) -> "a"                 # a and b both eligible; a was submitted first
report_failure("a", 10)         # second failure: a is quarantined
claim(10) -> "b"     quarantined() -> ["a"]

Part 2: Prerequisites

Extend submit(job_id, backoff, now, after=()), where after lists job ids that must complete before this job can be claimed. Add complete(job_id, now) for claimed jobs. If any prerequisite is quarantined (now or later), every job that transitively depends on it is quarantined too. Prerequisites must already exist when a job is submitted.

d = LabDispatcher(max_failures=2)
submit("extract", 2, 0)
submit("amplify", 2, 0, after=["extract"])
submit("label",   2, 0, after=["extract"])
submit("sequence", 1, 0, after=["amplify"])
claim(1) -> "extract"    claim(1) -> None
complete("extract", 2)
claim(2) -> "amplify"    claim(2) -> "label"
report_failure("amplify", 3)
claim(5) -> "amplify"
report_failure("amplify", 6)
quarantined() -> ["amplify", "sequence"]
complete("label",  7);   claim(8) -> None

Constraints

• Up to 2 * 10^5 operations. Every operation should run in O(log n) amortized time, not a scan over all jobs.