Near equilibrium fluctuations for supermarket models with growing choices

DOI10.1214/21-AAP1729zbMATH Open1496.90022arXiv2006.03621OpenAlexW3033098623MaRDI QIDQ2170372FDOQ2170372

Authors: Shankar Bhamidi, Amarjit Budhiraja, Miheer Dewaskar 

Publication date: 5 September 2022

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

Abstract: We consider the supermarket model in the usual Markovian setting where jobs arrive at rate $nlambd{a}_n$ for some $lambd{a}_n>0$, with $n$ parallel servers each processing jobs in its queue at rate 1. An arriving job joins the shortest among $d_{n}len$ randomly selected service queues. We show that when $d_{n}oinfty$ and $lambd{a}_{n}olambdain(0,infty)$, under natural conditions on the initial queues, the state occupancy process converges in probability, in a suitable path space, to the unique solution of an infinite system of constrained ordinary differential equations parametrized by $lambda$. Our main interest is in the study of fluctuations of the state process about its near equilibrium state in the critical regime, namely when $lambd{a}_{n}o1$. Previous papers have considered the regime $frac{d}_{n}sqrtnlognoinfty$ while the objective of the current work is to develop diffusion approximations for the state occupancy process that allow for all possible rates of growth of $d_n$. In particular we consider the three canonical regimes (a) $d_n/sqrtno0$; (b) $d_n/sqrtnocin(0,infty)$ and, (c) $d_n/sqrtnoinfty$. In all three regimes we show, by establishing suitable functional limit theorems, that (under conditions on $lambd{a}_n$) fluctuations of the state process about its near equilibrium are of order $n^{-1/2}$ and are governed asymptotically by a one dimensional Brownian motion. The forms of the limit processes in the three regimes are quite different; in the first case we get a linear diffusion; in the second case we get a diffusion with an exponential drift; and in the third case we obtain a reflected diffusion in a half space. In the special case $d_n/(sqrtnlogn)oinfty$ our work gives alternative proofs for the universality results established by Mukherjee et al in 2018.

Full work available at URL: https://arxiv.org/abs/2006.03621

Recommendations

• Asymptotic distributions and chaos for the supermarket model
• The supermarket model with bounded queue lengths in equilibrium
• Strong approximation for the supermarket model
• Supermarket model on graphs
• Averaging over fast variables in the fluid limit for Markov chains: Application to the supermarket model with memory

zbMATH Keywords

load balancingdiffusion approximationsheavy trafficfunctional limit theoremsreflected diffusionsfluid limitsSkorohod problempower of choiceHalfin-Whittjoin-the-shortest-queue

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Functional limit theorems; invariance principles (60F17) Stochastic network models in operations research (90B15)

Cites Work

• Title not available (Why is that?)
• Queueing system with selection of the shortest of two queues: An asymptotic approach
• Strong approximation theorems for density dependent Markov chains
• Large loss networks
• Fast Jackson networks
• Asymptotic distributions and chaos for the supermarket model
• On the maximum queue length in the supermarket model
• Chaoticity on path space for a queueing network with selection of the shortest queue among several
• Title not available (Why is that?)
• Steady-state analysis of load-balancing algorithms in the sub-Halfin-Whitt regime
• Asymptotic independence of queues under randomized load balancing
• An explicit formula for the Skorokhod map on \([0,a]\)
• Strong approximation for the supermarket model
• 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
• Diffusion approximations for load balancing mechanisms in cloud storage systems
• The supermarket model with bounded queue lengths in equilibrium
• Universality of power-of-\(d\) load balancing in many-server systems
• Foundations of modern probability. In 2 volumes
• Analysis of Randomized Join-the-Shortest-Queue (JSQ) Schemes in Large Heterogeneous Processor-Sharing Systems
• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• Delay, memory, and messaging tradeoffs in distributed service systems

Cited In (4)

• Strong approximation for the supermarket model
• The supermarket model with bounded queue lengths in equilibrium
• Averaging over fast variables in the fluid limit for Markov chains: Application to the supermarket model with memory
• Asymptotic distributions and chaos for the supermarket model

This page was built for publication: Near equilibrium fluctuations for supermarket models with growing choices

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