Fault-Tolerant Work Queue with Leases, Fencing Tokens and DAG Task Dependencies

Implement a fault-tolerant work queue for an infrastructure platform. Producers submit tasks; a pool of workers repeatedly claims a task, runs it, and reports the outcome. Workers can crash or hang at any moment without reporting anything, and every task must still eventually run to completion or be marked as failed. Tasks can also depend on other tasks: a task may only run after all of its dependencies have completed, and the dependencies must form a directed acyclic graph (DAG). ### Clarifying Questions - Can a task depend on tasks submitted earlier, on tasks in the same submission, or on tasks that have not been submitted yet? - How long may a task run, and can a worker extend its claim while it is still working? - How many attempts should a task get before it is marked as failed, and what happens to the tasks that depend on it? - Do task side effects need to happen exactly once, or is at-least-once acceptable if tasks are idempotent? - Is this a single in-memory service for the interview, with persistence discussed afterward, or must it be durable from the start? ### Part 1 — Claim, lease and acknowledge Implement `claim(now)`, which gives a worker a runnable task, and the calls a worker uses to report success or failure. Make sure a task claimed by a worker that crashes is eventually handed to another worker, and that a slow worker whose claim was taken away cannot corrupt the task's state when it finally reports back. ```hint Time-limited ownership Think about giving each claim an expiry and an identity, and what the queue should do when a report arrives from a worker whose claim has already expired and been reassigned. ``` #### What This Part Should Cover - Leases with expiry and renewal, and reclaiming tasks from crashed workers - Rejection of late reports from workers whose lease was lost - Retry limits and a terminal failed state - Efficient detection of expired leases ### Part 2 — DAG dependencies Add dependencies: a task becomes runnable only when all of its dependencies have completed. Reject any submission that would create a cycle, and decide what happens to dependents when a dependency permanently fails. ```hint Count what is still missing For each task, consider tracking how many of its dependencies are still unfinished, and what should happen to that number as tasks complete. ``` #### What This Part Should Cover - Release of dependents in topological order as tasks complete - Cycle detection at submission time, with a useful error - Failure propagation to downstream tasks - Validation of unknown or duplicate task IDs ### Part 3 — Delivery guarantees Explain whether your queue provides at-most-once, at-least-once or exactly-once execution. What would it take to get effectively exactly-once results, and what are the costs? ```hint Where duplicates come from Identify the precise moment a task's work can be performed twice even with a perfect queue, and ask who is able to detect that it happened. ``` #### What This Part Should Cover - Why leases imply at-least-once execution - Idempotency keys, fencing tokens and transactional outcome recording - Why exactly-once side effects in external systems are not achievable by the queue alone ### What a Strong Answer Covers - A working implementation of claims, leases, acknowledgments and dependency release, with tests of crash scenarios - A clearly stated state machine for tasks - Correct reasoning about delivery semantics and the races between workers and lease expiry - A path to persistence and to multiple queue servers ### Follow-up Questions - How would you persist the queue so that a restart loses no tasks and does not run finished tasks again? - How would you scale to many queue servers without two of them handing out the same task? - Some tasks are far more important than others. How do you add priorities without starving the rest? - How would you let an operator retry a failed task and everything downstream of it?