Comparing with basic fork-join queues, a job in (n,k) fork-join queues only needs its first k out of all n sub-tasks to be finished. Since (n,k) fork-join queues are prevalent in modern popular distributed systems such as Cassandra, MapReduce and Spark, estimating the sojourn time of such queues is critical for these systems' performance measurement and resource plan  . However, the estimating keeps to be a well-known open challenge for years, and only rough bounds for a narrow range of load factor have been given. In this paper, we developed a close-form linear transformation technique for identical random variables: The distribution of the k^{th} order statistic can be represented by a linear combination of the distributions of maxima. This brand-new technique is then used to transform the sojourn time distribution of non-purging (n,k) fork-join queues to a linear combination of the sojourn time distributions of basic (k,k)\sim (n,n) fork-join queues. Consequently, the expected sojourn time of non-purging (n,k) fork-join queues can be approximated with the help of existing approximations for basic fork-join queues. Then, approximations for non-purging queues are 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.
Comparing with 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 modern popular distributed systems such as Cassandra, MapReduce and Spark, estimating the sojourn time of such queues is critical for the performance measurement and resource plan of these systems . However, the estimating keeps to be a well-known open challenge for years, and only rough bounds for a narrow range of load factors have been given. In this paper, we developed a close-form linear transformation technique for identical random variables: The k^{th} 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)\sim (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.
D
first
R
these systems'
the
A
of these systems
R
factor
factors
D
distribution of the
D
the distributions of
D
distribution
R
to
into
R
time distributions
times
R
the expected sojourn time of
existing approximations for basic fork-join queues can be bridged to the approximations for
R
can be approximated with the help of existing approximations for basic fork-join queues. Then, approximations for non-purging queues are
. The uncovered approximations are then