zbMATH — the first resource for mathematics

Malyshev’s theory and JS-queues. Asymptotics of stationary probabilities. (English) Zbl 1039.60082
The paper considers a discrete-time nearest neighbor random walk (SHC random walk) in \(\mathbb{Z}^2_+\), whose jump probabilities are homogeneous in time and possess homogeneity relative to space shifts and symmetry relative to the reflection about the diagonal. These walks can describe the so-called join-the-shorter-queues (JS-queues). In JS-queues, tasks arrive within three independent Poisson processes \(\Xi_1\), \(\Xi_2\) and \(\Xi'\). Processes \(\Xi_1\) and \(\Xi_2\) are of rate \(\lambda\) and \(\Xi'\) of rate \(\lambda'\). Tasks from \(\Xi_1\) go to server 1, tasks from \(\Xi_2\) go to server 2 and tasks from \(\Xi'\) choose the shortest queue. The service rates at each server are equal 1, and tasks are served according to a conservative discipline (say, FCFS), without interruption. The paper gives a criterion for positive recurrence of SHC random walk and analyzes geometric asymptotics of the stationary probabilities \(\rho_{m+n, m}\) as \(m,n\to\infty\), \((m+ n)/n\sim \text{ctg\,}\gamma\).

60K25 Queueing theory (aspects of probability theory)
60G50 Sums of independent random variables; random walks
30D05 Functional equations in the complex plane, iteration and composition of analytic functions of one complex variable
30F10 Compact Riemann surfaces and uniformization
Full Text: DOI
[1] Boas, R. P. (1987). Invitation to Complex Analysis . Random House, New York.
[2] Fayolle, G. (1979). Méthodes analytiques pour les files d’attente couplées. Doctorat d’etat, sciences mathématiques, Université Paris VI.
[3] Fayolle, G. and Iasnogorodski, R. (1979). Two coupled processors: The reduction to a Riemann–Hilbert problem. Z. Wahrsch. Verw. Gebiete 47 325–351. · Zbl 0395.68032 · doi:10.1007/BF00535168
[4] Fayolle, G. and Iasnogorodski, R. (2002). Personal communications.
[5] Fayolle, G., Iasnogorodski, R. and Malyshev, V. (1999). Random Walks in the Quarter Plane , Algebraic Methods , Boundary Value Problems and Applications . Springer, Berlin. · Zbl 0932.60002
[6] Fayolle, G., Malyshev, V. and Menshikov, M. (1995). Topics in the Constructive Theory of Countable Markov Chains . Cambridge Univ. Press. · Zbl 0823.60053 · doi:10.1017/CBO9780511984020
[7] Fedoryuk, M. V. (1977). Saddle-Point Method. Nauka, Moscow. (In Russian.) · Zbl 0463.41020
[8] Flatto, L. and McKean, H. P. (1977). Two queues in parallel. Comm. Pure Appl. Math. 30 255–263. · Zbl 0336.60082 · doi:10.1002/cpa.3160300206
[9] Foley, R. D. and McDonald, D. R. (1998). Join the shortest queue: Stability and exact asymptotics. Preprint, Dept. Mathematics, Univ. Ottawa. · Zbl 1016.60078
[10] Iasnogorodski, R. (1979). Problèmes frontières dans les files d’attente. Doctorat d’etat, sciences math., Univ. Paris 6.
[11] Kurkova, I. A. (2001). A load-balanced network with two servers. Queueing Syst. 37 379–390. · Zbl 1017.90022 · doi:10.1023/A:1010841517511
[12] Kurkova, I. A. and Malyshev, V. A. (1998). Martin boundary and elliptic curves. Markov Process. Related Fields 4 203–272. · Zbl 0929.60055
[13] Malyshev, V. A. (1970). Random Walks. The Wiener–Hopf Equations in Quadrant of the Plane. Galois Automorophisms . Moscow Univ. Press. (In Russian.)
[14] Malyshev, V. A. (1972). Analytic method in the theory of two-dimensional random walks. Sib. Math. J. 13 1314–1327. · Zbl 0287.60072 · doi:10.1007/BF00971868
[15] Malyshev, V. A. (1973). Asymptotic behaviour of stationary probabilities for two-dimensional positive random walks. Sib. Math. J. 14 156–169. · Zbl 0307.60060 · doi:10.1007/BF00967270
[16] Suhov, Y. M. and Vvedenskaya, N. D. (1999). Fast Jackson-type networks with dynamic routing. Unpublished manuscript.
[17] Thomas, E. (2001). Unpublished manuscript.
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.