Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit
- 25 May 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 68 (3), 1-30
- https://doi.org/10.1145/3448213
Abstract
Parallel and distributed computing systems are foundational to the success of cloud computing and big data analytics. These systems process computational workflows in a way that can be mathematically modeled by a fork-and-join queueing network with blocking (FJQN/B). While engineering solutions have long been made to build and scale such systems, it is challenging to rigorously characterize their throughput performance at scale theoretically. What further complicates the study is the presence of heavy-tailed delays that have been widely documented therein. In this article, we utilize an infinite sequence of FJQN/Bs to study the throughput limit and focus on an important class of heavy-tailed service times that are regularly varying with index \(\). The throughput is said to be scalable if the throughput limit infimum of the sequence is strictly positive as the network size grows to infinity. We introduce two novel geometric concepts—scaling dimension and extended metric dimension—and show that an infinite sequence of FJQN/Bs is throughput scalable if the extended metric dimension \(\) and only if the scaling dimension \(\). We also show that for the cases where buffer sizes are scaling in an order of \(\), the scalability conditions are relaxed by a factor of \(\). The results provide new insights on the scalability of a rich class of FJQN/Bs with various structures, including tandem, lattice, hexagon, pyramid, tree, and fractals.
Keywords
Funding Information
- National Science Foundation (CNS-1717060, IIS-0916440, ECCS-1232118, and SES-1409214)
This publication has 37 references indexed in Scilit:
- Delay tails in MapReduce schedulingACM SIGMETRICS Performance Evaluation Review, 2012
- The Genome Analysis Toolkit: A MapReduce framework for analyzing next-generation DNA sequencing dataGenome Research, 2010
- Scalability of fork/join queueing networks with blockingACM SIGMETRICS Performance Evaluation Review, 2007
- Resolvability in graphs and the metric dimension of a graphDiscrete Applied Mathematics, 2000
- Properties of fork/join queueing networks with blocking under various operating mechanismsIEEE Transactions on Robotics and Automation, 1997
- Landmarks in graphsDiscrete Applied Mathematics, 1996
- Equivalence, reversibility, symmetry and concavity properties in fork-join queuing networks with blockingJournal of the ACM, 1994
- Greedy Lattice Animals I: Upper BoundsThe Annals of Applied Probability, 1993
- Comparison properties of stochastic decision free Petri netsIEEE Transactions on Automatic Control, 1992
- On the stability condition of a precedence-based queueing disciplineAdvances in Applied Probability, 1989