The existence of fixed points for the \(\cdot\)/GI/1 queue. (English) Zbl 1084.60057

Summary: A celebrated theorem of Burke’s asserts that the Poisson process is a fixed point for a stable exponential single server queue; that is, when the arrival process is Poisson, the equilibrium departure process is Poisson of the same rate. This paper considers the following question: Do fixed points exist for queues which dispense i.i.d. services of finite mean, but otherwise of arbitrary distribution (i.e., the so-called \(\cdot/\text{GI}/1/\infty/\text{FCFS}\) queues)? We show that if the service time \(S\) is nonconstant and satisfies \(\int\! P\{S \geq u\}^{1/2}\,du <\infty\), then there is an unbounded set \({\mathcal S}\subset(E[S],\infty)\) such that for each \(\alpha\in{\mathcal S}\) there exists a unique ergodic fixed point with mean inter-arrival time equal to \(\alpha\). We conjecture that in fact \({\mathcal S}=(E[S],\infty)\).


60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
Full Text: DOI Euclid


[1] Anantharam, V. (1993). Uniqueness of stationary ergodic fixed point for a \(\cdot/M/K\) node. Ann. Appl. Probab. 3 154–172. [Correction (1994) Ann. Appl. Probab. 4 607.] JSTOR: · Zbl 0786.60112
[2] Baccelli, F., Borovkov, A. and Mairesse, J. (2000). Asymptotic results on infinite tandem queueing networks. Probab. Theory Related Fields 118 365–405. · Zbl 0976.60088
[3] Billingsley, P. (1968). Convergence of Probability Measures . Wiley, New York. · Zbl 0172.21201
[4] Borovkov, A. (1976). Stochastic Processes in Queueing Theory . Springer, Berlin. [Russian edition (1972), Nauka, Moscow.] · Zbl 0319.60057
[5] Borovkov, A. (1984). Asymptotic Methods in Queueing Theory . Wiley, New York. [Russian edition (1980), Nauka, Moscow.] · Zbl 0479.60006
[6] Brandt, A., Franken, P. and Lisek, B. (1990). Stationary Stochastic Models . Wiley, New York. · Zbl 0723.60112
[7] Burke, P. (1956). The output of a queueing system. Oper. Res. 4 699–704.
[8] Chang, C. S. (1994). On the input-output map of a \(G/G/1\) queue. J. Appl. Probab. 31 1128–1133. · Zbl 0811.60077
[9] Daley, D. and Rolski, T. (1992). Finiteness of waiting-time moments in general stationary single-server queues. Ann. Appl. Probab. 2 987–1008. JSTOR: · Zbl 0772.60073
[10] Dudley, R. (1989). Real Analysis and Probability . Wadsworth & Brooks/Cole, Belmont, CA. · Zbl 0686.60001
[11] Ethier, S. and Kurtz, T. (1986). Markov Processes : Characterization and Convergence . Wiley, New York. · Zbl 0592.60049
[12] Glynn, P. and Whitt, W. (1991). Departures from many queues in series. Ann. Appl. Probab. 1 546–572. JSTOR: · Zbl 0749.60090
[13] Gray, R. (1988). Probability , Random Processes , and Ergodic Properties . Springer, Berlin. · Zbl 0644.60001
[14] Kamae, T., Krengel, U. and O’Brien, G. L. (1977). Stochastic inequalities on partially ordered spaces. Ann. Probab. 5 899–912. · Zbl 0371.60013
[15] Loynes, R. (1962). The stability of a queue with non-independent interarrival and service times. Proc. Cambridge Philos. Soc. 58 497–520. · Zbl 0203.22303
[16] Mairesse, J. and Prabhakar, B. (1999). On the existence of fixed points for the \(\cdot/GI/1\) queue. LIAFA Research Report 99/25, Universit√© Paris 7. · Zbl 1084.60057
[17] Martin, J. (2002). Large tandem queueing networks with blocking. Queueing Systems Theory Appl. 41 45–72. · Zbl 1053.60098
[18] Mountford, T. and Prabhakar, B. (1995). On the weak convergence of departures from an infinite sequence of \(\cdot/M/1\) queues. Ann. Appl. Probab. 5 121–127. JSTOR: · Zbl 0826.60083
[19] Prabhakar, B. (2003). The attractiveness of the fixed points of a \(\cdot/GI/1\) queue. Ann. Probab. 31 2237–2269. · Zbl 1057.60090
[20] Rudin, W. (1991). Functional Analysis , 2nd ed. McGraw-Hill, New York. · Zbl 0867.46001
[21] Stoyan, D. (1984). Comparison Methods for Queues and Other Stochastic Models . Wiley, New York. · Zbl 0536.60085
[22] Whitt, W. (1992). Uniform conditional stochastic order. J. Appl. Probab. 17 112–123.
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.