Time-dependent properties of symmetric queues
type: Item
instance of: scholarly article
title: Time-dependent properties of symmetric queues
zbMATH Open document ID: 1213.60146
author: Bert Zwart
author: Brian Fralix
published in: Queueing Systems
publication date: 2011-02-03T00:00:00Z
review text: 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 ove…
Mathematics Subject Classification ID: 60K25
Mathematics Subject Classification ID: 90B22
zbMATH DE Number: 5844656
zbMATH Keywords: regenerative processes
zbMATH Keywords: symmetric queues
zbMATH Keywords: time reversal
reviewed by: Vyacheslav Abramov
MaRDI profile type: Publication
full work available at URL: s11134-010-9202-1
OpenAlex ID: W2119175166
cites work: Transient behavior of the M/M/1 queue via Laplace transforms
cites work: Applied Probability and Queues
cites work: On Kelly networks with shuffling
cites work: Q4255469
cites work: Q2730382
cites work: Benes's formula for M/G/1–FIFO ‘explained' by preemptive-resume LIFO
cites work: On the distribution of the number of customers in the symmetric M/G/1 queue
cites work: A Pollaczek–Khintchine formula for M/G/1 queues with disasters
cites work: Some Time-Dependent Properties of Symmetric M/G/1 Queues
cites work: Q3855869
cites work: The M/G/1 processor-sharing model: Transient behavior
cites work: Introductory lectures on fluctuations of Lévy processes with applications.
cites work: Calculation of the Laplace transform of the length of the busy period for the M/G/1 queue via martingales
cites work: Q4265492
cites work: The continuity of queues
cites work: Stochastic-Process Limits
DOI: 10.1007/S11134-010-9202-1
Recommended article: Note on the GI/GI/1 queue with LCFS-PR observed at arbitrary times
Recommended article: On the distribution of the number of customers in the symmetric M/G/1 queue
Recommended article: Some Time-Dependent Properties of Symmetric M/G/1 Queues
Recommended article: Q3795029
Recommended article: Stationary workload and service times for some nonwork-conserving M/G/1 preemptive LIFO queues
Recommended article: An invariant-discipline queueing system
Recommended article: Response times in M/M/1 time-sharing schemes with limited number of service positions
Recommended article: Server sharing with a limited number of service positions and symmetric queues
description: scientific article; zbMATH DE number 5844656