Duality and Other Results for M/G/1 and GI/M/1 Queues, Via a New Ballot Theorem

Abstract

We generalize the classical ballot theorem and use it to obtain direct probabilistic derivations of some well-known and some new results relating to busy and idle periods and waiting times in M/G/1 and GI/M/1 queues. In particular, we uncover a duality relation between the joint distribution of several variables associated with the busy cycle in M/G/1 and the corresponding joint distribution in GI/M/1. In contrast with the classical derivations of queueing theory, our arguments avoid the use of transforms, and thereby provide insight and term-by-term “explanations” for the remarkable forms of some of these results.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 17 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.