Home | Articles | Past volumes | About | Login | Notify | Contact | Search
 Stochastic Systems > Vol. 6 (2016) open journal systems 

Heavy-traffic limits for a fork-join networkin the Halfin-Whitt regime

Hongyuan Lu, Penn State University
Guodong Pang, Penn State University

We study a fork-join network with a single class of jobs, which are forked into a fixed number of parallel tasks upon arrival to be processed at the corresponding multi-server stations. After service completion, each task will join a buffer associated with the service station waiting for synchronization, called “unsynchronized queue”. The synchronization rule requires that all tasks from the same job must be completed, referred to as “non-exchangeable synchronization”. Once synchronized, jobs will leave the system immediately. Service times of the parallel tasks of each job can be correlated and form a sequence of i.i.d. random vectors with a general continuous joint distribution function. We study the joint dynamics of the queueing and service processes at all stations and the associated unsynchronized queueing processes.
The main mathematical challenge lies in the “resequencing” of arrival orders after service completion at each station. As in Lu and Pang (2015) for the infinite-server fork-join network model, the dynamics of all the aforementioned processes can be represented via a multiparameter sequential empirical process driven by the service vectors for the parallel tasks of each job. We consider the system in the Halfin-Whitt regime, and prove a functional law of large number and a functional central limit theorem for queueing and synchronization processes. In this regime, although the delay for service at each station is asymptotically negligible, the delay for synchronization is of the same order as the service times.

AMS 2000 subject classifications: 60F17, 60H20, 60K25, 60K30, 90B15, 90B22.

Keywords: Fork-join networks, non-exchangeable synchronization, resequencing, Halfin-Whitt (QED) regime, functional law of large numbers (FLLN), functional central limit theorem (FCLT), multiparameter sequential empirical process, generalized multiparameter Kiefer

Creative Common LOGO

Full Text: PDF

Lu, Hongyuan, Pang, Guodong, Heavy-traffic limits for a fork-join networkin the Halfin-Whitt regime, Stochastic Systems, 6, (2016), 519-600 (electronic). DOI: 10.1214/15-SSY206.


[1]    R. J. Adler and J. E. Taylor. (2007) Random Fields and Geometry. Springer. MR2319516

[2]    M. Armony, S. Israelit, A. Mandelbaum, Y. N. Marmor, Y. Tseytlin and G. B. Yom-Tov. (2015) Patient flow in hospitals: a data-based queueing-science perspective. Stochastic Systems. Vol. 5, No. 1, 146–194. MR3442392

[3]    R. Atar, A. Mandelbaum and A. Zviran. (2012) Control of fork-join networks in heavy traffic. Communication, Control, and Computing (Allerton), 50th Annual Allerton Conference on. IEEE.

[4]    F. Baccelli, M. Lelarge and S. Foss. (2004) Asymptotics of subexponential max plus networks: the stochastic event graph case. Queueing Systems. Vol. 46, No. 1-2, 75–96. MR2072276

[5]    F. Baccelli, A. M. Makowski and A. Shwartz. (1989) The fork-join queue and related systems with synchronization constraints: stochastic ordering and computable bounds. Advances in Applied Probability. Vol. 21, No. 3, 629–660. MR1013655

[6]    F. Baccelli, W. A. Massey and D. Towsley. (1989) Acyclic fork-join queueing networks. Journal of the ACM (JACM). Vol. 36, No. 3, 615–642. MR1072240

[7]    P. Billingsley. (2009) Convergence of Probability Measures. John Wiley & Sons.

[8]    J. Blanchet, Y. Pei and K. Sigman. (2015) Exact sampling of some multi-dimensional queueing models with renewal input. Working paper. https://arxiv.org/abs/1512.07284

[9]    P. Brémaud. (1981) Point Processes and Queues. Springer, New York.

[10]    H. Dai. (2011) Exact Monte Carlo simulation for fork-join networks. Advances in Applied Probability. Vol. 43, No. 2, 484–503.

[11]    J. Dean and S. Ghemawat. (2008) MapReduce: simplified data processing on large clusters. Communications of the ACM. Vol. 51, No. 1, 107–113.

[12]    A. B. Dieker and M. Lelarge. (2006) Tails for (max, plus) recursions under subexponentiality. Queueing Systems. Vol. 53, No. 4, 213–230.

[13]    R. Durrett. (2010) Probability: Theory and Examples. Cambridge University Press. MR2722836

[14]    S. N. Ethier and T. G. Kurtz. (2009) Markov Processes: Characterization and Convergence. John Wiley & Sons.

[15]    L. Flatto and S. Hahn. (1984) Two Parallel Queues Created by Arrivals with Two Demands I. SIAM Journal on Applied Mathematics. Vol. 44, No. 5, 1041–1053. MR0759714

[16]    L. Flatto. (1985) Two Parallel Queues Created by Arrivals with Two Demands II. SIAM Journal on Applied Mathematics. Vol. 45, No. 5, 861–878.

[17]    J. Gallien and L. M. Wein. (2001) A simple and effective component procurement policy for stochastic assembly systems. Queueing Systems. Vol. 38, No. 2, 221–248.

[18]    S. Halfin and W. Whitt. (1981) Heavy-traffic limits for queues with many exponential servers. Operations Research. Vol. 29, No. 3, 567–588. MR0629195

[19]    B. G. Ivanoff. (1980) The function space D([0,)q, E). Canadian Journal of Statistics. Vol. 8, No. 2, 179–191.

[20]    J. Jacod and A. N. Shiryaev. (1987) Limit Theorems for Stochastic Processes. Springer-Verlag, Berlin.

[21]    A. Jean-Marie and L. Gün. (1993) Parallel queues with resequencing. Journal of the ACM (JACM). Vol. 40, No. 5, 1188–1208.

[22]    L. Jiang and R. E. Giachetti. (2008) A queueing network model to analyze the impact of parallelization of care on patient cycle time. Health Care Management Science. Vol. 11, 248–261.

[23]    I. Karatzas and S. E. Shreve. (1991) Brownian Motion and Stochastic Calculus. Springer. MR1121940

[24]    H. Kaspi and K. Ramanan. (2011) Law of large numbers limits for many-server queues. Annals of Applied Probability. Vol. 21, No. 1, 33–114.

[25]    H. Kaspi and K. Ramanan. (2013) SPDE limits of many-server queues. Annals of Applied Probability. Vol. 23, No. 1, 145–229.

[26]    L. J. Klementowski. (1978) PERT/CPM and supplementary analytical techniques: an analysis of aerospace usage. Ph.D. Thesis. Faculty of the School of Engineering of the Air Force Institute of Technology, Air University.

[27]    S. S. Ko and R. F. Serfozo. (2004) Response times in M/M/s fork-join networks. Advances in Applied Probability. Vol. 36, No. 3, 854–871.

[28]    S. S. Ko and R. F. Serfozo. (2008) Sojourn times in G/M/1 fork-join networks. Naval Research Logistics. Vol. 55, No. 5, 432–443.

[29]    E. V. Krichagina and A. A. Puhalskii. (1997) A heavy-traffic analysis of a closed queueing system with a GI∕service center. Queueing Systems. Vol. 25, No. 1-4, 235–280.

[30]    R. C. Larson, M. F. Cahn and M. C. Shell. (1993) Improving the New York City arrest-to-arraignment system. Interfaces. Vol. 23, No. 1, 76–96.

[31]    M. Lin, L. Zhang, A. Wierman and J. Tan. (2013) Joint optimization of overlapping phases in MapReduce. Proceedings of IFIP Performance. Vol. 70, No. 10, 720–735.

[32]    R. S. Liptser and A. N. Shiryaev. (1989) Theory of Martingales. Kluwer, Dordrecht.

[33]    H. Lu and G. Pang. (2015) Gaussian limits of a fork-join network with non-exchangeable synchronization in heavy-traffic. Mathematics of Operations Research. Vol. 41, No. 2, 560–595.

[34]    H. Lu, G. Pang and M. Mandjes. (2016) A functional central limit theorem for Markov additive arrival processes and its applications to queueing systems. Queueing Systems. Vol. 84, No. 3, 381–406.

[35]    H. Lu and G. Pang. (2017) Heavy-traffic limits for an infinite-server fork-join queueing system with dependent and disruptive services. Queueing Systems. Vol. 85, No. 1–2, 67–115.

[36]    M. Mandelker. (1982) Continuity of monotone functions. Pacific Journal of Mathematics. Vol. 99, No. 2, 413–418.

[37]    A. W. Marshall and I. Olkin. (1967) A multivariate exponential distribution. Journal of the American Statistical Association. Vol. 62, No. 317, 30–44.

[38]    A. Mandelbaum and P. Momčilović. (2012) Queues with many servers and impatient customers. Mathematics of Operations Research. Vol. 37, No. 1, 41–65. MR2891146

[39]    G. Neuhaus. (1971) On weak convergence of stochastic processes with multidimensional time parameter. Annals of Mathematical Statistics. Vol. 42, No. 4, 1285–1295.

[40]    V. Nguyen. (1993) Processing networks with parallel and sequential tasks: heavy traffic analysis and Brownian Limits. Annals of Applied Probability. Vol. 3, No. 1, 28–55.

[41]    V. Nguyen. (1994) The trouble with diversity: fork-join networks with heterogeneous customer population. Annals of Applied Probability. Vol. 4, No. 1, 1–25.

[42]    G. Pang, R. Talreja and W. Whitt. (2007) Martingale proofs of many-server heavy-traffic limits for Markovian queues. Probability Surveys. 4, 193–267.

[43]    G. Pang and W. Whitt. (2010) Two-parameter heavy-traffic limits for infinite-server queues. Queueing Systems. Vol. 65, No. 4, 325–364.

[44]    G. Pang and W. Whitt. (2012) Infinite-server queues with batch arrivals and dependent service times. Probability in Engineering and Informational Sciences. Vol. 26, No. 2, 197–220.

[45]    G. Pang and W. Whitt. (2013) Two-parameter heavy-traffic limits for infinite-server queues with dependent service times. Queueing Systems. Vol. 73, No. 2, 119–146.

[46]    G. Pang and Y. Zhou. (2016) Two-parameter process limits for an infinite-server queue with arrival dependent service times. Forthcoming in Stochastic Processes and their Applications. http://dx.doi.org/10.1016/j.spa.2016.08.003

[47]    G. Pang and Y. Zhou. (2017) Two-parameter process limits for infinite-server queues with dependent service times via chaining bounds. Under review.

[48]    D. Pinotsi and M. A. Zazanis. (2005) Synchronized queues with deterministic arrivals. Operations Research Letters. Vol. 33, No. 6, 560–566.

[49]    B. Prabhakar, N. Bambos and T. S. Mountford. (2000) The synchronization of Poisson processes and queueing networks with service and synchronization nodes. Advances in Applied Probability. Vol. 32, No. 3, 824–843.

[50]    A. A. Puhalskii and J. E. Reed. (2010) On many-server queues in heavy traffic. Annals of Applied probability. Vol. 20, No. 1, 129–195.

[51]    J. E. Reed. (2009) The G/GI/N queue in the Halfin-Whitt regime. Annals of Applied Probability. Vol. 19, No. 6, 2211–2269.

[52]    M. Sklar. (1959) Fonctions de répartition à n dimensions et leurs marges. Publ. Inst. Statist. Univ. Paris 8.

[53]    M. Takahashi, H. Osawa and T. Fujisawa. (2000) On a synchronization queue with two finite buffers. Queueing Systems. Vol. 36, No. 1-3, 107–123.

[54]    J. Tan, X. Meng and L. Zhang. (2012) Delay tails in MapReduce scheduling. ACM SIGMETRICS Performance Evaluation Review. Vol. 40, No. 1, 5–16.

[55]    A. W. van der Vaart and J. A. Wellner. (1996) Weak Convergence and Empirical Processes. Springer.

[56]    S. Varma. (1990) Heavy and light traffic approximations for queues with synchronization constraints. Ph.D. Thesis.

[57]    W. Wang, K. Zhu, L. Ying, J. Tan and L. Zhang. (2013) Map task scheduling in MapReduce with data locality: throughput and heavy-traffic optimality. Proceedings of IEEE INFOCOM. 1609–1617.

[58]    W. Whitt. (2002) Stochastic-Process Limits: An Introduction to Stochastic-Process Limits and Their Application to Queues. Springer.

[59]    C. J. Willits and D. C. Dietz. (2001) Nested fork-join queueing network model for analysis of airfield operations. Journal of Aircraft. Vol. 38, No. 5, 848–855.

[60]    I. Zaied. (2012) The offered load in fork-join networks: calculations and applications to service engineering of emergency department. M.Sc. Research Thesis. Technion.

[61]    A. Zviran. (2011) Fork-join networks in heavy traffic: diffusion approximations and control. M.Sc. Research Thesis. Technion.

Home | Articles | Past volumes | About | Login | Notify | Contact | Search

Stochastic Systems. ISSN: 1946-5238