Extreme values for the waiting time in large fork-join queues
Authors:
Open Access
- 22 February 2025
- journal article
- research article
- Published by Springer Nature in Queueing Systems
- Vol. 109 (1) , 1-26
Abstract
We prove that the scaled maximum steady-state waiting time and the scaled maximum steady-state queue length among N GI/GI/1-queues in the N-server fork-join queue converge to a normally distributed random variable as $$N\rightarrow \infty $$ . The maximum steady-state waiting time in this queueing system scales around $$\frac{1}{\gamma }\log N$$ , where $$\gamma $$ is determined by the cumulant generating function $$\Lambda $$ of the service times distribution and solves the Cramér–Lundberg equation with stochastic service times and deterministic interarrival times. This value $$\frac{1}{\gamma }\log N$$ is reached at a certain hitting time. The number of arrivals until that hitting time satisfies the central limit theorem, with standard deviation $$\frac{\sigma _A}{\sqrt{\Lambda '(\gamma )\gamma }}$$ . By using the distributional form of Little’s law, we can extend this result to the maximum queue length. Finally, we extend these results to a fork-join queue with different classes of servers.
Keywords
All Related Versions
Funding Information
- Stichting voor de Technische Wetenschappen (439.16.121)
This publication has 42 references indexed in Scilit:
- Fork–join and redundancy systems with heavy-tailed job sizesQueueing Systems, 2022
- Delay asymptotics and bounds for multitask parallel jobsQueueing Systems, 2019
- Biased Processor Sharing in Fork-Join Queues2018
- Dynamic Control of the Join-Queue Lengths in Saturated Fork-Join Stations2016
- Sojourn times in G/M/1 fork‐join networksNaval Research Logistics (NRL), 2008
- Extreme Value Theory2006
- A fork-join queueing model: Diffusion approximation, integral representations and asymptoticsQueueing Systems, 1996
- Interpolation approximations for symmetric Fork-Join queuesPerformance Evaluation, 1994
- Performance evaluation of fork and join synchronization primitivesActa Informatica, 1987
- On the constant in the nonuniform version of the Berry-Ess en theoremProbability Theory and Related Fields, 1981