Arrival theorem

In queueing theory, a discipline within the mathematical theory of probability, the arrival theorem[1] (also referred to as the random observer property, ROP or job observer property[2]) states that "upon arrival at a station, a job observes the system as if in steady state at an arbitrary instant for the system without that job."[3]

The arrival theorem always holds in open product-form networks with unbounded queues at each node, but it also holds in more general networks. A necessary and sufficient condition for the arrival theorem to be satisfied in product-form networks is given in terms of Palm probabilities in Boucherie & Dijk, 1997.[4] A similar result also holds in some closed networks. Examples of product-form networks where the arrival theorem does not hold include reversible Kingman networks[4][5] and networks with a delay protocol.[3]

Mitrani offers the intuition that "The state of node i as seen by an incoming job has a different distribution from the state seen by a random observer. For instance, an incoming job can never see all 'k jobs present at node i, because it itself cannot be among the jobs already present."[6]

  1. ^ Asmussen, Søren (2003). "Queueing Networks and Insensitivity". Applied Probability and Queues. Stochastic Modelling and Applied Probability. Vol. 51. pp. 114–136. doi:10.1007/0-387-21525-5_4. ISBN 978-0-387-00211-8.
  2. ^ El-Taha, Muhammad (1999). Sample-path Analysis of Queueing Systems. Springer. p. 94. ISBN 0-7923-8210-2.
  3. ^ a b Van Dijk, N. M. (1993). "On the arrival theorem for communication networks". Computer Networks and ISDN Systems. 25 (10): 1135–2013. doi:10.1016/0169-7552(93)90073-D.
  4. ^ a b Boucherie, R. J.; Van Dijk, N. M. (1997). "On the arrivai theorem for product form queueing networks with blocking". Performance Evaluation. 29 (3): 155. doi:10.1016/S0166-5316(96)00045-4.
  5. ^ Kingman, J. F. C. (1969). "Markov Population Processes". Journal of Applied Probability. 6 (1). Applied Probability Trust: 1–18. doi:10.2307/3212273. JSTOR 3212273.
  6. ^ Mitrani, Isi (1987). Modelling of Computer and Communication Systems. CUP. p. 114. ISBN 0521314224.