×

The fork-join queue and related systems with synchronization constraints: Stochastic ordering and computable bounds. (English) Zbl 0681.60096

From the authors’ abstract: A simple queueing system, known as the fork- join queue, is considered with basic performance measure defined as the delay between the fork and join dates. Simple lower and upper bounds are derived for some of the statistics of this quantity. They are obtained, in both transient and steady-state regimes, by stochastically comparing the original system to other queueing systems with a structure simpler than the original system, yet with identical stability characteristics. In steady-state, under renewal assumptions, the computation reduces to standard GI/GI/1 calculations and the bounds constitute a first sizing-up of system performance.
These bounds can also be used to show that for homogeneous fork-join queue systems under assumptions, the moments of the system response time grow logarithmically in the number of parallel processors provided the service time distribution has rational Laplace-Stieltjes transform. The bounding arguments combine ideas from the theory of stochastic ordering with the notion of associated random variables.
Reviewer: E.A.van Doorn

MSC:

60K25 Queueing theory (aspects of probability theory)
PDFBibTeX XMLCite
Full Text: DOI