Universal Scaling of Distributed Queues Under Load Balancing in the Super-Halfin-Whitt Regime

Abstract

This paper considers the steady-state performance of load balancing algorithms in a many-server system with distributed queues. The system has$N$servers, and each server maintains a local queue with buffer size$b-1$, i.e. a server can hold at most one job in service and$b-1$jobs in the queue. Jobs in the same queue are served according to the first-in-first-out (FIFO) order. The system is operated in a heavy-traffic regime such that the workload per server is$\lambda = 1 - N^{-\alpha }$for$0.5\leq \alpha < 1$. We identify a set of algorithms such that the steady-state queues have the following universal scaling, whereuniversalmeans that it holds for any$\alpha \in [0.5,1$): (i) the number of busy servers is$\lambda N-o(1)$; and (ii) the number of servers with two jobs (one in service and one in queue) is$O(N^{\alpha }\log N)$; and (iii) the number of servers with more than two jobs is$O({1}/{N^{r(1-\alpha)-1}})$, where$r$can be any positive integer independent of$N$. The set of load balancing algorithms that satisfy the sufficient condition includes join-the-shortest-queue (JSQ), idle-one-first (I1F), and power-of-$d$-choices (Po$d$) with$d\geq 2N^\alpha \log N$. We further argue that the waiting time of such an algorithm is near optimal order-wise.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 16 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.