Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-24T12:31:44.487Z Has data issue: false hasContentIssue false
  • English
  • Français

The fork-join queue and related systems with synchronization constraints: stochastic ordering and computable bounds

Published online by Cambridge University Press:  01 July 2016

François Baccelli ,
Armand M. Makowski  and
Adam Shwartz
François Baccelli*
Affiliation:
INRIA
Armand M. Makowski*
Affiliation:
University of Maryland
Adam Shwartz*
Affiliation:
Technion–Israel Institute of Technology
*
∗Postal address: INRIA—Centre de Sophia Antipolis, Avenue E. Hughes, 06565, Valbonne Cedex, France.
∗∗Postal address: Electrical Engineering Department and Systems Research Center, University of Maryland, College Park, Maryland 20742, USA.
∗∗∗Postal address: Electrical Engineering Department, Technion–Israel Institute of Technology, Haifa 32000, Israel.
Get access Rights & Permissions [Opens in a new window]

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 system 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, and are of independent interest to study various other queueing systems with synchronization constraints. The paper is an abridged version of a more complete report on the matter [6].

Keywords

STOCHASTIC BOUNDSINCREASING CONVEX ORDERINGASSOCIATED RANDOM VARIABLES
Type
Research Article
Information
Advances in Applied Probability , Volume 21 , Issue 3 , September 1989 , pp. 629 - 660
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.)

Footnotes

The work of this author was supported partially through a grant from AT & T Bell Laboratories and partially through a grant from the Minta Martin Aeronautical Research Fund, College of Engineering, University of Maryland, College Park, MD 20742, USA.

The work of this author was supported partially through ONR Grant N00014-84-K-0614, partially through NSF Grant ECS-83–51836 and partially through a grant from AT & T Bell Laboratories.

The work of this author was supported through a grant from AT & T Bell Laboratories.

References

[1] Baccelli, F. (1985) Two parallel queues created by arrivals with two demands. Rapport de Recherche 426, INRIA—Rocquencourt France.Google Scholar
[2] Baccelli, F. and Makowski, A. M. (1985) Simple computable bounds for the fork-join queue. Proc. 19th Annual Conf. Information Sciences and Systems, The Johns Hopkins University, Baltimore, MD, March 1985, 436–441.Google Scholar
[3] Baccelli, F. and Makowski, A. M. (1986) Stability and bounds for single server queue in random environment. Stoch. Models 2, 281–292.CrossRefGoogle Scholar
[4] Baccelli, F. and Makowski, A. M. (1989) Multidimensional stochastic ordering and associated random variables. Operat. Res. 37.CrossRefGoogle Scholar
[5] Baccelli, F., Makowski, A. M. and Shwartz, A. (1986) Simple computable bounds and approximations for the fork-join queue. Intern. Workshop on Computer Performance Evaluation, Tokyo, September 1985, pp. 437–450.Google Scholar
[6] Baccelli, F., Makowski, A. M. and Shwartz, A. (1987) The fork-join queue and related systems with synchronization constraints: stochastic ordering, approximations and computable bounds. Technical Research Report TR-87–01, System Research Center, University of Maryland, College Park, MD, January 1987 and Rapport de Recherche 687, INRIA–Rocquencourt (France), June 1987.Google Scholar
[7] Baccelli, F., Makowski, A. M. and Shwartz, A. (1988) Computations for synchronized queueing networks. In preparation.Google Scholar
[8] Baccelli, F., Massey, W. A. and Towsley, A. (1989) Acyclic fork-join queueing network. J. Assoc. Comput. Mach. 36.Google Scholar
[9] Barlow, R. E. and Proschan, F. (1975) Statistical Theory of Reliability and Life Testing. Holt, Rinehart and Winston, Reading, MA.Google Scholar
[10] Borovkov, A. A. (1976) Stochastic Processes in Queueing Theory (English translation). Springer-Verlag, New York.CrossRefGoogle Scholar
[11] Flatto, L. and Hahn, S. (1984) Two parallel queues created by arrivals with two demands I. SIAM J. Appl. Math. 44, 1041–1053.CrossRefGoogle Scholar
[12] Hajek, B. (1983) The proof of a folk theorem on queueing delay with applications to routing in networks. J. Assoc. Comput. Mach. 30, 834–851.CrossRefGoogle Scholar
[13] Humblet, P. (1982) Determinism minimizes waiting times in queues. Technical Report LIDS—Department of Electrical Engineering and Computer Science, MIT, Cambridge, MA.Google Scholar
[14] Lai, T. L. and Robbins, H. (1978) A class of dependent random variables and their maxima. Z. Wahrscheinlichkeitsch. 42, 89–111.CrossRefGoogle Scholar
[15] Loynes, R. M. (1962) The stability of a queue with non-independent interarrival and service times. Proc. Camb. Phil. Soc. 5, 497–520.CrossRefGoogle Scholar
[16] Nelson, R. and Tantawi, A. N. (1988) Approximate analysis of fork/join synchronization in parallel queues. IEEE Trans Comput. 37, 739–743.CrossRefGoogle Scholar
[17] Rogozin, B. A. (1966) Some extremal problems in queueing theory. Theory Prob. Appl. 11, 144–151.CrossRefGoogle Scholar
[18] Ross, S. (1986) Stochastic Processes. Wiley, New York.Google Scholar
[19] Rolski, T. (1981) Queues with non-stationary input streams: Ross' conjecture. J. Appl. Prob. 13, 603–68.Google Scholar
[20] Rolski, T. (1984) Comparison theorems for queues with dependent inter-arrival times. In Modelling and Performance Evaluation Methodology, Paris (France), January 1983. Lecture Notes in Control and Information Sciences 60, Springer-Verlag, New York.Google Scholar
[21] Stoyan, D. (1984) Comparison Methods for Queues and Other Stochastic Models (English translation, ed. Daley, D. J.). Wiley, New York.Google Scholar
[22] Whitt, W. (1984) Minimizing delays in the GI/GI/1 queue. Operat. Res. 32, 41–51.CrossRefGoogle Scholar