Retry Queue Correctness: Duplicate Work, Retry Boundaries, and Cancellation

A retry queue has to answer a deceptively hard question: which attempt is allowed to change the job now? If an old worker reports success after a retry has already started, accepting that stale acknowledgement can erase work that is still active.

The retrying job queue exercise models this with one queue owner and explicit operations. Jobs wait in FIFO order. A reservation moves the oldest waiting job in flight and gives it an attempt number. A retry returns it to the tail; its next reservation gets the next attempt number. An acknowledgement or retry succeeds only when the job is in flight and the supplied attempt matches the current attempt.

Fence every result by its attempt

Suppose job a is reserved as attempt 1, retried, and reserved again as attempt 2. A delayed ack(a, 1) must fail without changing state. So must a delayed retry(a, 1). Only ack(a, 2) can complete the current reservation. This is a small fencing rule: the attempt number identifies which reservation a result belongs to.

The fence prevents stale state transitions inside this model. It does not make the work itself happen exactly once. A real worker can perform an external side effect and lose its connection before reporting success; the queue may then retry work whose side effect already happened. The exercise has no network calls or external side effects, so it cannot demonstrate how a production system resolves that ambiguous outcome. In a real integration, the effect may need its own idempotency key or reconciliation step.

Define what counts as active

Capacity belongs to all active jobs, both waiting and in flight. Reserving work does not free a slot. Only acknowledgement or cancellation does. If capacity counted just the waiting list, workers could reserve jobs indefinitely while enqueue continued to admit more work than the configured limit.

IDs also have a lifecycle. Rejecting a duplicate active ID prevents two jobs from occupying the same logical identity. In this exercise, once an ID has been accepted, it remains reserved for the lifetime of that queue, even after completion or cancellation. Rejected enqueues do not reserve their IDs. That rule is stricter than many production queues, which may support reuse with a separate generation or idempotency scheme; follow the contract you actually have.

Make cancellation's boundary explicit

Cancellation removes an active waiting or in-flight job immediately and invalidates its reservation. It preserves the order of jobs that remain waiting. Therefore, a later acknowledgement for the cancelled reservation must fail.

This is a deterministic state-machine contract, not a description of stopping a real process. A real worker may still be running after cancellation is requested. Its resource cleanup can require a separate signal or acknowledgement before capacity is released. The related bounded worker schedule exercise calls out that distinction: its simulated cancel event frees a worker immediately, while real cancellation can need cleanup confirmation.

Keep retry policy separate from queue transitions

The exercise's Retry operation is an explicit event. It does not decide whether an error is transient, choose a delay, cap the number of attempts, or retry automatically. Those are policy choices outside this small queue contract. Keeping the transition explicit makes its correctness inspectable: reject an unknown job, a waiting job, a completed job, or an attempt that is stale, future, or zero without changing state.

Try the retrying job queue by writing event sequences before implementation. Include a stale acknowledgement after a retry, a duplicate enqueue while a job is in flight, a cancellation followed by an old acknowledgement, and a retry that moves behind another waiting job. Check every output and the queue state after each operation. The exercise is single-owner and uses no threads, clocks, network calls, or automatic retries; it tests the transition contract rather than a hosted worker system.

The public problem page is available to browse. Hosted code execution on Beyond Big O is restricted to the verified owner, so this guide does not promise anonymous hosted runs. The exercise can also be used as a contract for your own local implementation.

For another example of turning a requirement into a small counterexample, see how to review code boundaries.