×
Luczak, Malwina J.; Norris, James

Strong approximation for the supermarket model. (English) Zbl 1080.60086

Ann. Appl. Probab. 15, No. 3, 2038-2061 (2005).
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.
Reviewer: Oleg K. Zakusilo (Kyïv)

Cited in 10 Documents

MSC:

60K25 Queueing theory (aspects of probability theory)
60F15 Strong limit theorems

Keywords:

join the shortest queue; law of large numbers
PDF BibTeX XML Cite
\textit{M. J. Luczak} and \textit{J. Norris}, Ann. Appl. Probab. 15, No. 3, 2038--2061 (2005; Zbl 1080.60086)
Full Text: DOI arXiv
  • logo of hbz
  • logo of WorldCat

References:

[1] Darling, R. W. R. and Norris, J. R. (2005). Structure of large random hypergraphs. Ann. Appl. Probab. 15 125–152. · Zbl 1062.05132
[2] Deimling, K. (1977). Ordinary Differential Equations in Banach Spaces. Lecture Notes in Math. 596 . Springer, Berlin. · Zbl 0361.34050
[3] Eager, D. L., Lazokwska, E. D. and Zahorjan, J. (1986). Adaptive load sharing in homogeneous distributed systems. IEEE Trans. Soft. Eng. 12 662–675.
[4] Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes : Characterization and Convergence. Wiley, New York. · Zbl 0592.60049
[5] Graham, C. (2000). Kinetic limits for large communication networks. In Modelling in Applied Sciences (N. Bellomo and M. Pulvirenti, eds.) 317–370. Birkhäuser, Basel. · Zbl 0984.94040
[6] Graham, C. (2000). Chaoticity on path space for a queueing network with selection of the shortest queue among several. J. Appl. Probab. 37 198–201. · Zbl 0961.60091
[7] Graham, C. (2004). Functional central limit theorems for a large network in which customers join the shortest of several queues. · Zbl 1058.60077
[8] Komlós, J., Major, P. and Tusnády, G. (1975). An approximation of partial sums of independent RV’s and the sample DF I. Z. Wahrsch. Verw. Gebiete 32 111–131. · Zbl 0308.60029
[9] Luczak, M. J. (2003). A quantitative law of large numbers via exponential martingales. In Stochastic Inequalities and Applications (E. Giné, C. Houdré and D. Nualart, eds.) 56 93–111. Birkhäuser, Basel. · Zbl 1038.60068
[10] Luczak, M. J. and McDiarmid, C. (2004). On the maximum queue length in the supermarket model. · Zbl 1102.60083
[11] Luczak, M. J. and McDiarmid, C. (2005). On the power of two choices: Balls and bins in continuous time. Ann. Appl. Probab. 15 1733–1764. · Zbl 1079.60016
[12] Martin, J. B. and Suhov, Y. M. (1998). Fast Jackson networks. Ann. Appl. Probab. 9 854–870. · Zbl 0972.90008
[13] Massart, P. (2002). Tusnády’s lemma, 24 years later. Ann. Inst. H. Poincaré Probab. Statist. 38 991–1007. · Zbl 1016.60037
[14] Mitzenmacher, M. (1996). The power of two choices in randomized load balancing. Ph.D. thesis, Berkeley.
[15] Revuz, D. and Yor, M. (1991). Continuous Martingales and Brownian Motion. Springer, Berlin. · Zbl 0731.60002
[16] Vvedenskaya, N. D., Dobrushin, R. L. and Karpelevich, F. I. (1996). Queueing system with selection of the shortest of two queues: An asymptotic approach. Probl. Inf. Transm. 32 15–27. · Zbl 0898.60095
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.