Stability of Fork-Join Systems with Redundancy and Heterogeneous Servers
Abstract
We consider the stability problem of fork-join systems with redundancy (FJR) and heterogeneous servers under both static and dynamic capacity-allocation policies. In an (n,k) FJR system, each arriving job is split into n independent tasks, with one task assigned to each of n parallel servers. Once k ≤ n tasks have been processed, they are joined and the corresponding job departs the system; the remaining n−k unprocessed tasks are then removed and are therefore termed redundant. We first identify the nominal traffic intensity and characterize the maximal stability region, defined as the set of traffic intensities for which there exists an admissible policy that stabilizes the system. We then establish conditions under which this maximal stability region is attained for two classes of policies: static and dynamic. Specifically, we show that for static allocation policies, in which service capacities remain fixed over time, maximality is achieved whenever the fastest server is allocated no more than 1/k of the total service capacity. For dynamic allocation policies, in which a fixed total service capacity may be repeatedly reallocated among the servers, we show that maximality is achieved whenever the cumulative capacity allocated to the j shortest queues does not exceed j/k of the total capacity for every j=1,…,k−1. Our analysis is based on a projection of the (n,k) FJR system onto a simpler (k,k) system that has no redundancy, together with a novel sample-path comparison argument for multidimensional processes based on the generalized Schur-convex order.
Related
- Redundancy and Renewal of Servers in Opened Queuing Networks
- The Capacity of Private Information Retrieval from Coded Storage Systems with Colluding, Robust and Byzantine Servers
- Some applications of binary numeration systems with nonzero redundancy to the theory of locally complex functions
- Comparing the reliability of coherent systems with heterogeneous, dependent and distribution-free components
- Speed and stability of segregated waves in a pressure-based model of heterogeneous cell populations
BibTeX
@misc{gao2026stability,
title = {{Stability of Fork-Join Systems with Redundancy and Heterogeneous Servers}},
author = {Chutong Gao and Seyed Iravani and Ohad Perry},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.09237},
eprint = {2609.09237},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.09237},
}
RIS
TY - UNPB
TI - Stability of Fork-Join Systems with Redundancy and Heterogeneous Servers
AU - Chutong Gao
AU - Seyed Iravani
AU - Ohad Perry
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.09237
UR - https://arxiv.org/abs/2609.09237
AB - We consider the stability problem of fork-join systems with redundancy (FJR) and heterogeneous servers under both static and dynamic capacity-allocation policies. In an (n,k) FJR system, each arriving job is split into n independent tasks, with one task assigned to each of n parallel servers. Once k ≤ n tasks have been processed, they are joined and the corresponding job departs the system; the remaining n−k unprocessed tasks are then removed and are therefore termed redundant. We first identify the nominal traffic intensity and characterize the maximal stability region, defined as the set of traffic intensities for which there exists an admissible policy that stabilizes the system. We then establish conditions under which this maximal stability region is attained for two classes of policies: static and dynamic. Specifically, we show that for static allocation policies, in which service capacities remain fixed over time, maximality is achieved whenever the fastest server is allocated no more than 1/k of the total service capacity. For dynamic allocation policies, in which a fixed total service capacity may be repeatedly reallocated among the servers, we show that maximality is achieved whenever the cumulative capacity allocated to the j shortest queues does not exceed j/k of the total capacity for every j=1,…,k−1. Our analysis is based on a projection of the (n,k) FJR system onto a simpler (k,k) system that has no redundancy, together with a novel sample-path comparison argument for multidimensional processes based on the generalized Schur-convex order.
ER -