Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-12T19:42:52.472Z Has data issue: false hasContentIssue false
  • English
  • Français

On the stability condition of a precedence-based queueing discipline

Published online by Cambridge University Press:  01 July 2016

François Baccelli  and
Zhen Liu
François Baccelli*
Affiliation:
INRIA
Zhen Liu*
Affiliation:
CNET PAA-ATR
*
∗Postal address: INRIA, Centre Sophia Antipolis, 06565 Valbonne Cedex, France.
∗∗Now at INRIA, Centre Sophia Antipolis.
Get access Rights & Permissions [Opens in a new window]

Abstract

The queueing model known as precedence-based queueing discipline, proposed in [8] by Tsitsiklis et al. is addressed. In this queueing model, there are infinitely many servers and for any pair of customers i and j such that i arrived later than j, there is a fixed probability p that i will have to wait for the end of the execution of j before starting its execution. In the case where the customer service times are deterministic and the arrival process is Poisson, these authors have derived the stability condition which determines the maximum arrival rate that keeps the system stable. For more general statistics, they conjectured that the stability condition would possibly depend on the complete service time distribution functions but only on the first moment of the inter-arrival times.

In this paper, we consider this queueing model and relax the restrictive statistical assumptions mentioned above by only assuming that the service times and the inter-arrival times are stationary and ergodic sequences, so that these variables can receive general distribution functions and be correlated.

We derive a general expression for the stability condition which in turn proves the above conjectures. The results are obtained by establishing pathwise evolution equations for these queueing systems, and then a schema which, in certain sense, generalizes the schema of Loynes for the G/G/1 queues.

Keywords

QUEUEING THEORYERGODIC THEORYDATABASE CONCURRENCY CONTROLPARALLEL PROCESSING
Type
Research Article
Information
Advances in Applied Probability , Volume 21 , Issue 4 , December 1989 , pp. 883 - 898
Copyright
Copyright © Applied Probability Trust 1989 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Baccelli, F. and Bremaud, P. (1987) Palm Probabilities and Stationary Queues. Lecture Notes in Statistics 41, Springer-Verlag, Berlin.Google Scholar
[2] Baccelli, F. and Liu, Z. (1988) On the stability of a precedence based queueing discipline. Rapport INRIA No. 880.Google Scholar
[3] Baccelli, F. and Makowski, A. (1989) Queueing models for systems with synchronization constraints. Proc. IEEE 77, 138–161. (Special Issue on Dynamics of Discrete Event Systems, ed. Ho, L.)Google Scholar
[4] Bambos, N. and Walrand, J. (1989) On stability and performance of parallel processing systems. In preparation.Google Scholar
[5] Kingman, J. F. C. (1968) The ergodic theory of subadditive stochastic processes. J. R. Statist. Soc. B 30, 499–510.Google Scholar
[6] Kingman, J. F. C. (1976) Subadditive processes. Ecole d'Eté de Probabilités de Saint-Flour, ed. Hennequin, P. L. Lecture Notes in Mathematics 539, Springer-Verlag, Berlin, 165–223.Google Scholar
[7] Loynes, R. M. (1962) The stability of queues with non-independent interarrival and service times. Proc. Camb. Phil. Soc. 58, 497–520.Google Scholar
[8] Tsitsiklis, J. N., Papadimitriou, C. H. and Humblet, P. (1986) The performance of a precedence-based queueing discipline. J. Assoc. Comput. Mach. 33, 593–602.Google Scholar
[9] Vincent, J. M. (1989) In preparation.Google Scholar