Completion-Shock Queues: Departure-Induced Invalidation and Endogenous Service Correlation

In the study of how things move through systems, from cars on a highway to data packets across a network, scientists often rely on a simple mental model: a line of people waiting for a service. In the most basic version of this model, when one person finishes their turn and leaves, the work required by the people waiting behind them remains exactly the same. The line simply gets shorter. This assumption makes the math manageable and works well for many situations, but it fails to capture the reality of complex, interconnected tasks. In software development, engineering, or data processing, finishing one task can sometimes change the nature of the work waiting in the queue. A new code update might invalidate a ticket that was already prepared, or a design decision might force a team to redo work that was already completed. When the act of finishing a job changes the requirements of the jobs waiting behind it, the system behaves very differently than standard models predict.

A researcher at the Holon Institute of Technology has built a new mathematical model to explore exactly this phenomenon, calling it a "completion-shock" queue. The study focuses on a single server handling a stream of jobs that arrive randomly. Under normal circumstances, a job is "clean" and takes a certain amount of time to finish. However, the model introduces a twist: every time a job leaves the system, there is a chance that a "shock" occurs. This shock does not affect the job that just left; instead, it looks at the next two jobs waiting in line. If those waiting jobs are still in their original, clean state, the shock marks them as "invalidated." An invalidated job cannot be processed immediately; it must first go through a remediation phase to fix the issue before it can return to the front of the line for its normal service. Crucially, this shock is generated by the system itself—the departure of one job triggers the extra work for the others.

The researcher found that this self-generated feedback loop dramatically reduces the capacity of the system. In a standard line where jobs do not affect one another, the system can handle an arrival rate up to a certain limit before it becomes unstable and the line grows infinitely long. In this new model, the presence of these completion-induced shocks means the system becomes unstable at a much lower arrival rate. For example, if the chance of a shock occurring is thirty percent, the system can only handle about two-thirds of the traffic it could manage if no shocks were happening. The line becomes unstable not because too many jobs are arriving, but because the jobs that do arrive are creating more work for each other, effectively clogging the system from the inside out.

To understand how this works, the researcher treated the queue as a series of states. When the line is long enough, the system can be described by looking at the status of the first two people in line: whether they are clean or invalidated. This creates a specific pattern of movement between different states, which the researcher analyzed using a method known as a quasi-birth-and-death process. This approach allowed for an exact calculation of the system's stability and its long-term behavior. The results showed that the system is stable only if the arrival rate of new jobs is low enough to be balanced by the rate at which the server can clear both the original work and the extra remediation work caused by the shocks.

One of the most striking findings concerns the relationship between the jobs in the line. In a standard queue, the time it takes to serve one person is usually independent of the time it takes to serve the next. In this shock model, the service times become linked. Because a single shock can invalidate two consecutive jobs, the need for remediation in one job is statistically connected to the need for remediation in the next. The researcher proved that this connection extends only to the immediate neighbor; the job two spots down the line is not directly affected by the same shock event. This creates a specific, predictable pattern of dependence where the history of the line influences its future, but only for a short distance.

The study also looked at what happens when the system is pushed to its absolute limit, a state known as heavy traffic. By expanding the mathematical description of the system near this breaking point, the researcher derived a precise coefficient that describes how the line grows as it approaches instability. When comparing this shock-driven system to a standard system where jobs are independent but have the same average service time, the shock system consistently performed worse. The extra work created by the shocks added a measurable penalty to the system's efficiency. This penalty was found to be strictly positive, meaning that the dependence between jobs always makes the queue longer and the wait times higher than if the jobs were independent, even if the average time to fix a job remains the same.

To ensure these theoretical results were correct, the researcher built a computer simulation that tracked every single job and its specific status, rather than relying on the simplified mathematical groups. The simulation confirmed the theoretical predictions with high precision, showing that the mathematical model accurately captures the behavior of the system. The study also explored what would happen if the shock could reach further down the line, affecting three jobs instead of two. While the math becomes more complex in that scenario, the fundamental principle remains the same: the range of the shock determines how far the dependence extends, creating a chain reaction of extra work that spreads through the queue.

This work provides a tractable way to understand systems where success in one area creates failure in another. It moves beyond the idea of a passive queue, where waiting jobs are just sitting there, and recognizes that the queue itself is an active participant in generating future workload. The findings suggest that in any system where upstream changes can invalidate downstream preparations, the capacity of the system is not just a matter of how fast the server works, but also a matter of how the completion of one task reshapes the requirements of the tasks waiting in the wings. The model offers a clear, exact framework for calculating these limits, showing that the cost of interdependence is a real, quantifiable reduction in performance.