Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit

DOI10.1145/3448213zbMATH Open1499.68040arXiv1805.05197OpenAlexW3165146583MaRDI QIDQ5056406

Author name not available (Why is that?)

Publication date: 8 December 2022

Published in: (Search for Journal in Brave)

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. To this end, we introduce two fundamental concepts for networks of arbitrary topology (scaling dimension and extended metric dimension) and utilize an infinite sequence of growing FJQN/Bs to study the throughput limit. 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 investigate throughput scalability by focusing on heavy-tailed service times that are regularly varying (with index $alpha>1$) and featuring the network topology described by the two aforementioned dimensions. In particular, we show that an infinite sequence of FJQN/Bs is throughput scalable if the extended metric dimension $<alpha-1$ and only if the scaling dimension $lealpha-1$. These theoretical 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.

Full work available at URL: https://arxiv.org/abs/1805.05197

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Fork and Join Queueing Networks with Heavy Tails: Scaling Dimension and Throughput Limit

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5056406)