Asymptotic Zero Queueing in Many-Server Heavy Traffic

17 concepts10 papers1 proposal

In classical queueing theory, operating a system near its maximum capacity comes with a severe penalty: as utilization approaches 100%, queue lengths and waiting times explode toward infinity. This "heavy-traffic curse" has long been accepted as an unavoidable trade-off in system design.

However, modern cloud infrastructure operates at a scale where thousands of servers are managed collectively. In this many-server regime ($N \to \infty$), a remarkable phenomenon emerges: if the arrival rate of jobs approaches the system's total capacity at a carefully controlled rate, clever routing and scheduling policies can achieve asymptotic zero queueing. This means that even under heavy traffic, the probability of an incoming task experiencing any delay vanishes to zero as the system scales.

The Geometry of the Sub-Halfin-Whitt Regime

To understand why asymptotic zero queueing is possible, we must look at how spare capacity scales relative to the number of servers, $N$.

In the well-studied Halfin-Whitt regime, the system's spare capacity scales as $O(\sqrt{N})$. While this scale keeps queueing delays bounded, it does not eliminate them entirely. To drive the waiting probability to zero, the system must operate in the slightly less congested sub-Halfin-Whitt regime. Here, the system retains just enough extra breathing room so that routing algorithms can successfully hunt for idle servers.

The core mechanism behind this behavior was formalized by Xin Liu et al.. They demonstrated that achieving near-zero waiting times depends on a simple condition: the load balancing policy must keep the probability of routing a task to a busy server below a specific threshold relative to $N$. As long as this condition is met, the system maintains a state where almost every incoming job finds an idle resource immediately.

Halfin-Whitt Regime:      Spare Capacity ~ O(√N)   --> Bounded Delays
Sub-Halfin-Whitt Regime:  Slightly More Spare Capacity --> Asymptotic Zero Queueing

In a follow-up steady-state analysis, Xin Liu et al. proved that widespread algorithms like Join-the-Shortest-Queue (JSQ) and Join-the-Idle-Queue (JIQ) naturally satisfy this condition. Even randomized policies can exploit this regime. The "Power-of-$d$" strategy—which samples $d$ random servers and routes the job to the least loaded one—is highly popular because it avoids the overhead of querying every server. As analyzed by Sushil Mahavir Varma et al., the choice of the sample size $d$ in the sub-Halfin-Whitt regime acts as a sharp threshold, dictating whether jobs experience finite or infinite delays as traffic approaches capacity.

Proving Insensitivity to Job Distributions

Early proofs of zero-waiting behaviors relied on the mathematically convenient assumption that job service times are exponentially distributed (memoryless). Real-world cloud workloads, however, are highly variable and non-exponential.

To bridge this gap, Kang Gong analyzed load balancing under Coxian-2 distributed service times. By combining Stein's method with a novel iterative state-space collapse technique, the author proved that the mean queue length still scales down as $O(1/\sqrt{N})$, forcing waiting times to asymptotically approach zero.

To generalize this further, Kang Gong introduced a framework called Iterative State-Space Peeling (ISSP). This technique established the "large-system insensitivity" of zero-waiting algorithms, proving that for a broad class of policies, the waiting probability scales as $O(1/N^{0.5-\alpha})$ in the sub-Halfin-Whitt regime regardless of the underlying Coxian service distribution.

Taming Heterogeneity with Graphon Theory

In practical cloud environments, the assumption of uniformity breaks down completely: some servers process tasks faster than others, and certain tasks can only run on specific server types. This multi-dimensional heterogeneity typically causes localized bottlenecks, destroying the pool of idle servers needed for zero queueing.

To solve this, Zhisheng Zhao et al. introduced a mathematical framework based on graphon theory to model infinite-dimensional heterogeneity. They designed two low-complexity routing policies:

  1. Intelligent Capacity Reservation and Dispatching (ICRD)
  2. Speed-Priority Dispatching (SPD)

These policies work by systematically pruning the rate-matrix of allowed connections between task types and server types. By isolating and reserving capacity for specific workloads, Zhisheng Zhao et al. proved that these policies maintain the asymptotic zero-queueing property, ensuring that diverse tasks find idle, compatible servers even at massive scales.

The Multi-Server Job Challenge: Packing Instabilities

The rise of large-scale AI and machine learning workloads introduces a more severe structural challenge: a single job may require multiple servers simultaneously (e.g., a distributed training job spanning 8 GPUs). This creates a geometric packing problem. Even if 10% of the cluster's servers are idle, a job requiring 16 servers cannot start if those idle servers are scattered across the cluster. This fragmentation causes queue lengths to grow exponentially under heavy traffic.

To find the boundaries of stability, Weina Wang et al. established a joint scaling regime. By parameterizing how the system load, the maximum job size, and the total server capacity evolve relative to one another, the authors derived the exact mathematical boundaries where the probability of queueing delays vanishes to zero. They showed that massive clusters can achieve near-instantaneous service for multi-server jobs, provided that the growth of individual job resource requirements is sufficiently constrained relative to the total server count.

Traditional Jobs:   [Job] ──> Fits on any single idle server.
Multi-Server Jobs:  [  Job  ] ──> Requires concurrent, coordinated idle servers (Packing Problem).

When operating deep within heavy traffic, heuristics that focus solely on job duration fail because they ignore this packing fragmentation. To address this, Isaac Grosof et al. developed ServerFilling-SRPT. This policy pairs the latency-minimizing properties of Shortest Remaining Processing Time (SRPT) with an explicit server-packing heuristic. By prioritizing jobs that cleanly fill the remaining server slots, it prevents fragmentation and keeps utilization high enough to minimize mean response times.

Finally, when dispatching jobs based on size and queue states, traditional symmetric heuristics often degrade under heavy traffic. To counter this, Runhan Xie et al. proposed a design principle called CARD (Controlled Asymmetry Reduces Delay). Instead of trying to balance the load perfectly across all queues, CARD deliberately creates asymmetric queue states. This controlled imbalance ensures that a subset of servers remains highly fluid and clear of long-running jobs, providing an architectural guarantee that incoming tasks can always find an immediate opening.

Key Foundational Work

Steady-state analysis of load-balancing algorithms in the sub-Halfin-Whitt regime (2020) — contributed 5 concept elements to this direction.
Zero Queueing for Multi-Server Jobs (2020) — contributed 3 concept elements to this direction.
A Simple Steady-State Analysis of Load Balancing Algorithms in the Sub-Halfin-Whitt Regime (2018) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_heavy_traffic_instability_2137256c,
  title = {heavy-traffic instability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/heavy-traffic-instability/rdr_2137256cf73341119d1a2b84e7e10b7c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_heavy_traffic_instability_2137256c_v1,
  title = {heavy-traffic instability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/heavy-traffic-instability/rdr_2137256cf73341119d1a2b84e7e10b7c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake