Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 12 (2007) > Paper 3 open journal systems 


Asymptotic distributions and chaos for the supermarket model

Malwina J Luczak, London School of Economics
Colin McDiarmid, University of Oxford


Abstract
In the supermarket model there are n queues, each with a unit rate server. Customers arrive in a Poisson process at rate λn, where 0<λ<1. Each customer chooses d > 2 queues uniformly at random, and joins a shortest one. It is known that the equilibrium distribution of a typical queue length converges to a certain explicit limiting distribution as n -> oo. We quantify the rate of convergence by showing that the total variation distance between the equilibrium distribution and the limiting distribution is essentially of order n-1; and we give a corresponding result for systems starting from quite general initial conditions (not in equilibrium). Further, we quantify the result that the systems exhibit chaotic behaviour: we show that the total variation distance between the joint law of a fixed set of queue lengths and the corresponding product law is essentially of order at most n-1.


Full text: PDF

Pages: 75-99

Published on: January 24, 2007
Bibliography
  1. Ethier, Stewart N.; Kurtz, Thomas G. Markov processes. and Mathematical Statistics. John Wiley & Sons, Inc., New York, 1986. x+534 pp. ISBN: 0-471-08186-8 MR0838085 (88a:60130)
  2. Graham, Carl. Kinetic limits for large communication networks. 317--370, Model. Simul. Sci. Eng. Technol., Birkhäuser Boston, Boston, MA, 2000. MR1763158 (2001f:60109)
  3. Graham, Carl. Chaoticity on path space for a queueing network with selection of the J. Appl. Probab. 37 (2000), no. 1, 198--211. MR1761670 (2001f:60101)
  4. Graham, Carl. Functional central limit theorems for a large network in which Probab. Theory Related Fields 131 (2005), no. 1, 97--120. MR2105045 (2005k:60301)
  5. Graham, Carl; Méléard, Sylvie. Chaos hypothesis for a system interacting through shared Probab. Theory Related Fields 100 (1994), no. 2, 157--173. MR1296426 (95j:60165)
  6. Guionnet, A.; Zegarlinski, B. Lectures on logarithmic Sobolev inequalities. 1--134, Lecture Notes in Math., 1801, Springer, Berlin, 2003. MR1971582 (2004b:60226)
  7. Kac, M. Foundations of kinetic theory. pp. 171--197. University of California Press, Berkeley and Los Angeles, 1956. MR0084985 (18,960i)
  8. Ledoux, Michel. The concentration of measure phenomenon. Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, RI, 2001. x+181 pp. ISBN: 0-8218-2864-9 MR1849347 (2003k:28019)
  9. Luczak, Malwina J. A quantitative law of large numbers via exponential martingales. 93--111, Progr. Probab., 56, Birkhäuser, Basel, 2003. MR2073429 (2005h:60250)
  10. Luczak, Malwina J.; McDiarmid, Colin. On the power of two choices: balls and bins in continuous time. Ann. Appl. Probab. 15 (2005), no. 3, 1733--1764. MR2152243 (2006j:60014)
  11. Luczak, Malwina J.; McDiarmid, Colin. On the maximum queue length in the supermarket model. Ann. Probab. 34 (2006), no. 2, 493--527. MR2223949
  12. Luczak, Malwina J.; Norris, James. Strong approximation for the supermarket model. Ann. Appl. Probab. 15 (2005), no. 3, 2038--2061. MR2152252 (2006c:60123)
  13. McDiarmid, Colin. On the method of bounded differences. 148--188, London Math. Soc. Lecture Note Ser., 141, Cambridge Univ. Press, Cambridge, 1989. MR1036755 (91e:05077)
  14. McDiarmid, Colin. Concentration. 195--248, Algorithms Combin., 16, Springer, Berlin, 1998. MR1678578 (2000d:60032)
  15. Mitzenmacher, Michael. Load balancing and density dependent jump Markov processes (extended 213--222, IEEE Comput. Soc. Press, Los Alamitos, CA, 1996. MR1450619
  16. M. Mitzenmacher. The power of two choices in randomized load-balancing. Ph.D. thesis. Berkeley, 1996, http://www.eecs.harvard.edu/~michaelm/
  17. Mitzenmacher, Michael; Richa, Andréa W.; Sitaraman, Ramesh. The power of two random choices: a survey of techniques and 255--312, Comb. Optim., 9, Kluwer Acad. Publ., Dordrecht, 2001. MR1966907 (2004c:68171)
  18. Sznitman, Alain-Sol. Topics in propagation of chaos. 165--251, Lecture Notes in Math., 1464, Springer, Berlin, 1991. MR1108185 (93b:60179)
  19. C. Villani. Optimal transportation, dissipative PDE's and functional inequalities. Lect. Notes Math. 1813, Springer-Verlag, Berlin, to appear.
  20. Vvedenskaya, N. D.; Dobrushin, R. L.; Karpelevich, F. I. A queueing system with a choice of the shorter of two queues---an (Russian) Problemy Peredachi Informatsii 32 (1996), no. 1, 20--34; translation in Problems Inform. Transmission 32 (1996), no. 1, 15--27 MR1384927 (97d:60154)
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489