Join-the-shortest queue diffusion limit in Halfin-Whitt regime: sensitivity on the heavy-traffic parameter

DOI10.1214/19-AAP1496MaRDI QIDQ2180378zbMATH OpenOpenAlexFDO

Authors Sayan Banerjee, Debankur Mukherjee

Publication date 13 May 2020

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.01739, https://projecteuclid.org/euclid.aoap/1582621220

zbMATH Keywords

local timeHalfin-Whitt regimeregenerative processesdiffusion limitjoin the shortest queuesteady-state analysisnonelliptic diffusion

Mathematics Subject Classification ID

Diffusion processes (60J60) Queueing theory (aspects of probability theory) (60K25) Stochastic integral equations (60H20) Renewal theory (60K05)

Abstract: Consider a system of $N$ parallel single-server queues with unit-exponential service time distribution and a single dispatcher where tasks arrive as a Poisson process of rate $lambda(N)$. When a task arrives, the dispatcher assigns it to one of the servers according to the Join-the-Shortest Queue (JSQ) policy. Eschenfeldt and Gamarnik (Math. Oper. Res., 43(3):867-886, 2018) identified a novel limiting diffusion process that arises as the weak-limit of the appropriately scaled occupancy measure of the system under the JSQ policy in the Halfin-Whitt regime, where $$ as $Noinfty$. The analysis of this diffusion goes beyond the state of the art techniques, and even proving its ergodicity is non-trivial, and was left as an open question. Recently, exploiting a generator expansion framework via the Stein's method, Braverman (arXiv:1801.05121, 2018) established its exponential ergodicity, and adapting a regenerative approach, Banerjee and Mukherjee (Ann. Appl. Probab., 29(2):1262-1309, 2018) analyzed the tail properties of the stationary distribution and path fluctuations of the diffusion. However, the analysis of the bulk behavior of the stationary distribution, viz., the moments, remained intractable until this work. In this paper, we perform a thorough analysis of the bulk behavior of the stationary distribution of the diffusion process, and discover that it exhibits different qualitative behavior, depending on the value of the heavy-traffic parameter $$. Moreover, we obtain precise asymptotic laws of the centered and scaled steady state distribution, as $$ tends to 0 and $infty$. Of particular interest, we also establish a certain intermittency phenomena in the $$ regime and a surprising distributional convergence result in the $$ regime.

Recommendations

• Join-the-shortest queue diffusion limit in Halfin-Whitt regime: tail asymptotics and scaling of extrema
• Join the shortest queue with many servers. The heavy-traffic asymptotics
• Steady-state analysis of the join-the-shortest-queue model in the Halfin-Whitt regime
• Transient behavior of the Halfin-Whitt diffusion
• Universality of load balancing schemes on the diffusion scale

Cites work

• scientific article; zbMATH DE number 192908 (Why is no real title available?)
• scientific article; zbMATH DE number 1416816 (Why is no real title available?)
• Concentration inequalities and model selection. Ecole d'Eté de Probabilités de Saint-Flour XXXIII -- 2003.
• Economies-of-scale in many-server queueing systems: tutorial and partial review of the QED Halfin-Whitt heavy-traffic regime
• First passage times to congested states of many-server systems in the Halfin-Whitt regime
• Gravitation versus Brownian motion
• Heavy-Traffic Limits for Queues with Many Exponential Servers
• Join the shortest queue with many servers. The heavy-traffic asymptotics
• Join-the-shortest queue diffusion limit in Halfin-Whitt regime: tail asymptotics and scaling of extrema
• Long time asymptotics for constrained diffusions in polyhedral domains
• Lyapunov functions for semimartingale reflecting Brownian motions
• Markov chains and stochastic stability
• On positive recurrence of constrained diffusion processes
• On the rate of convergence to stationarity of the M/M/\(n\) queue in the Halfin-Whitt regime
• Scalable load balancing in networked systems: universality properties and stochastic coupling methods
• Slow energy dissipation in anharmonic oscillator chains
• Spectral gap of the Erlang A model in the Halfin-Whitt regime
• Steady-state GI/G/\(n\) queue in the Halfin-Whitt regime
• Steady-state analysis of the join-the-shortest-queue model in the Halfin-Whitt regime
• Transient behavior of the Halfin-Whitt diffusion
• Universality of load balancing schemes on the diffusion scale
• Universality of power-of-\(d\) load balancing in many-server systems

Cited in

(9)

• Join-the-shortest queue diffusion limit in Halfin-Whitt regime: tail asymptotics and scaling of extrema
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• Join the shortest queue with many servers. The heavy-traffic asymptotics
• Steady-state analysis of the join-the-shortest-queue model in the Halfin-Whitt regime
• The inert drift atlas model
• The Join-the-Shortest-Queue System in the Halfin-Whitt Regime: Rates of Convergence to the Diffusion Limit
• A load balancing system in the many-server heavy-traffic asymptotics
• Inert drift system in a viscous fluid: steady state asymptotics and exponential ergodicity
• Universality of load balancing schemes on the diffusion scale

This page was built for publication: Join-the-shortest queue diffusion limit in Halfin-Whitt regime: sensitivity on the heavy-traffic parameter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2180378)