Title: Approximations and Bounds for (n, k) Fork-Join Queues: A Linear Transformation Approach,
Abstract: Compared to basic fork-join queues, a job in (n, k) fork-join queues only
needs its k out of all n sub-tasks to be finished. Since (n, k) fork-join
queues are prevalent in popular distributed systems, erasure coding based cloud
storages, and modern network protocols like multipath routing, estimating the
sojourn time of such queues is thus critical for the performance measurement
and resource plan of computer clusters. However, the estimating keeps to be a
well-known open challenge for years, and only rough bounds for a limited range
of load factors have been given. In this paper, we developed a closed-form
linear transformation technique for jointly-identical random variables: An
order statistic can be represented by a linear combination of maxima. This
brand-new technique is then used to transform the sojourn time of non-purging
(n, k) fork-join queues into a linear combination of the sojourn times of basic
(k, k), (k+1, k+1), ..., (n, n) fork-join queues. Consequently, existing
approximations for basic fork-join queues can be bridged to the approximations
for non-purging (n, k) fork-join queues. The uncovered approximations are then
used to improve the upper bounds for purging (n, k) fork-join queues.
Simulation experiments show that this linear transformation approach is
practiced well for moderate n and relatively large k.