Time-dependent properties of symmetric queues (Q622618)

A symmetric \(M/G/1\) queue is such an \(M/G/1\) queueing system in which all positions in the queue are labeled 1, 2, 3, \(\dots\), and when there are \(n\) customers in the system, the server processes the customer that is currently in the position \(i\) at rate \(\gamma(n,i)\), \(1\leq i\leq n\), and \(\sum_{i=1}^n\gamma(n,i)=1\). At a moment of Poisson arrival of a new customer, the position \(i\) for that customer is chosen with probability \(\gamma(n+1,i)\), and each customer having the position \(k\geq i\) previously is moved to the position \(k+1\). If a service of a specific customer \(j\) is completed, it leaves the system and each customer having the position \(l\geq j\) changes it to \(l-1\). Preemptive-resume last-come-first-serve (PR-LCFS) discipline and processor-sharing discipline are two examples where the queues are symmetric. \textit{O. Kella, B. Zwart} and \textit{O. Boxma}, J. Appl. Probab. 42, No. 1, 223--234 (2005; Zbl 1077.60069)], have studied the time-dependent behavior of PR-LCFS queues. They showed that the number of jobs sampled at an exponential time has a geometric distribution. It follows from the result of these authors that the distribution of the number of jobs at a fixed time is independent of the service discipline. Whether or not this fact is correct for all symmetric queues remained an open problem. \textit{D. Denisov} and \textit{A. Sapozhnikov} [Queueing Syst. 54, No. 4, 237--241 (2006; Zbl 1104.60054)], proved this fact for the queues with Erlang service times. The present paper solves the aforementioned conjecture for arbitrary distributed service times and arbitrary symmetric service disciplines. The approach is based on a simple time-reversal argument, which is an extension of the earlier analysis of \textit{J. Abate} and \textit{W. Whitt} [Adv. Appl. Probab. 20, No. 1, 145--178 (1988; Zbl 0638.60097)], and helps to solve the problem in the case of the queueing process that admits a stationary solution. In the case of overloaded queueing systems the authors use other arguments that reduce the problems to the analysis of clearing models.