Strong approximation for the supermarket model
From MaRDI portal
Abstract: We prove three strong approximation theorems for the `supermarket' or `join the shortest queue' model -- a law of large numbers, a jump process approximation and a central limit theorem. The estimates are carried through rather explicitly. This allows us to estimate each of the infinitely many components of the process in its own scale and to exhibit a cut-off in the set of active components which grows slowly with the number of servers.
The supermarket model is a system of \(N\) single-server queues. Customers arrive as a Poisson process of rate \(N\lambda \), where \(\lambda \in (0,1)\). Each customer examines \(d\) queues, chosen randomly from all queues, and joins the shortest of these \(d\) queues, choosing randomly if the shortest queue is not unique. The paper establishes a law of large numbers, a jump process approximation and a central limit theorem for this supermarket model.
Recommendations
- The supermarket model with bounded queue lengths in equilibrium
- Asymptotic distributions and chaos for the supermarket model
- Dynamics of the non-homogeneous supermarket model
- Near equilibrium fluctuations for supermarket models with growing choices
- Supermarket model on graphs
- On the maximum queue length in the supermarket model
- Block-structured supermarket models
- The mean-field computation in a supermarket model with server multiple vacations
- Supermarket Choice and Supermarket Competition in Market Equilibrium
- On a doubly dynamically controlled supermarket model with impatient customers
Cites work
- An approximation of partial sums of independent RV'-s, and the sample DF. I
- Chaoticity on path space for a queueing network with selection of the shortest queue among several
- Fast Jackson networks
- Functional central limit theorems for a large network in which customers join the shortest of several queues
- scientific article; zbMATH DE number 3951715 (Why is no real title available?)
- scientific article; zbMATH DE number 48952 (Why is no real title available?)
- scientific article; zbMATH DE number 2034511 (Why is no real title available?)
- scientific article; zbMATH DE number 1488838 (Why is no real title available?)
- On the maximum queue length in the supermarket model
- On the power of two choices: balls and bins in continuous time
- Ordinary differential equations in Banach spaces
- Queueing system with selection of the shortest of two queues: An asymptotic approach
- Structure of large random hypergraphs
- Tusnady's lemma, 24 years later
Cited in
(15)- 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
- Near equilibrium fluctuations for supermarket models with growing choices
- The hydrodynamic limit of a randomized load balancing network
- Supermarket model on graphs
- Asymptotic distributions and chaos for the supermarket model
- On the maximum queue length in the supermarket model
- The mean-field computation in a supermarket model with server multiple vacations
- Block-structured supermarket models
- Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
- Universality of power-of-d load balancing in many-server systems
- Economies-of-scale in many-server queueing systems: tutorial and partial review of the QED Halfin-Whitt heavy-traffic regime
- Staffing and control of instant messaging contact centers
- Real-time dynamic control in the supermarket models and some numerical analyses
- Invariance principle and McKean-Vlasov limit for randomized load balancing in heavy traffic
This page was built for publication: Strong approximation for the supermarket model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2572400)
