Averaging over fast variables in the fluid limit for Markov chains: Application to the supermarket model with memory

DOI10.1214/12-AAP861zbMATH Open1274.60244arXiv1001.0895OpenAlexW3104995436MaRDI QIDQ1950259FDOQ1950259

Authors: Malwina Luczak, James R. Norris 

Publication date: 10 May 2013

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

Abstract: We set out a general procedure which allows the approximation of certain Markov chains by the solutions of differential equations. The chains considered have some components which oscillate rapidly and randomly, while others are close to deterministic. The limiting dynamics are obtained by averaging the drift of the latter with respect to a local equilibrium distribution of the former. Some general estimates are proved under a uniform mixing condition on the fast variable which give explicit error probabilities for the fluid approximation. Mitzenmacher, Prabhakar and Shah [In Proc. 43rd Ann. Symp. Found. Comp. Sci. (2002) 799-808, IEEE] introduced a variant with memory of the "join the shortest queue" or "supermarket" model, and obtained a limit picture for the case of a stable system in which the number of queues and the total arrival rate are large. In this limit, the empirical distribution of queue sizes satisfies a differential equation, while the memory of the system oscillates rapidly and randomly. We illustrate our general fluid limit estimate by giving a proof of this limit picture.

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

Recommendations

• Strong approximation for the supermarket model
• Near equilibrium fluctuations for supermarket models with growing choices
• Dynamics of the non-homogeneous supermarket model
• Asymptotic distributions and chaos for the supermarket model
• Averaging in Markov models with fast Markov switches and applications to queueing models

zbMATH Keywords

law of large numberscorrectorsfast variablessupermarket modeljoin the shortest queueexponential martingale inequalitiesfluid limits for Markov chainssupermarket model with memory

Mathematics Subject Classification ID

Applications of continuous-time Markov processes on discrete state spaces (60J28) Queueing theory (aspects of probability theory) (60K25)

Cites Work

• Queueing system with selection of the shortest of two queues: An asymptotic approach
• Differential equation approximations for Markov chains
• Asymptotic analysis of multiscale approximations to reaction networks
• Functional central limit theorems for a large network in which customers join the shortest of several queues
• 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
• Strong approximation for the supermarket model

Cited In (8)

• Scalable Load Balancing in Networked Systems: A Survey of Recent Advances
• Fluid limits for QB-CSMA with polynomial rates, homogenization and reflection
• Variations on undirected graphical models and their relationships
• The supermarket model with bounded queue lengths in equilibrium
• The Power of Filling in Balanced Allocations
• Near equilibrium fluctuations for supermarket models with growing choices
• Induced idleness leads to deterministic heavy traffic limits for queue-based random-access algorithms
• Power-of-d-Choices with Memory: Fluid Limit and Optimality

This page was built for publication: Averaging over fast variables in the fluid limit for Markov chains: Application to the supermarket model with memory

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