(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. This paper 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.
Parallel systems have received increasing attention with numerous recent applications such as fork-join systems, load-balancing, and l-out-of-fc redundancy. Common to these systems is a join or resequencing stage, where tasks that have finished service may have to wait for the completion of other tasks so that they leave the system in a predefined order. These synchronization constraints make the analysis of parallel systems challenging and few explicit results are known. In this work, we model parallel systems using a max-plus approach that enables us to derive statistical bounds of waiting and sojourn times. Taking advantage of max-plus system theory, we also show end-to-end delay bounds for multi-stage fork-join networks. We contribute solutions for basic G|G|1 fork-join systems, parallel systems with load-balancing, as well as general (k, l) fork-join systems with redundancy. Our results provide insights into the respective advantages of l-out-of-k redundancy vs. load-balancing. We propose a family of heuristic approximations for the expected response time of K-dimensional symmetric Fork-Join systems in statistical equilibrium with general inter-arrival and service time distributions. To do this, we rely on the light traffic interpolation technique popularized by Reiman and Simon. Our starting point is a formula for the heavy traffic limit of two-dimensional Fork-Join queues that was obtained by the authors in [17,20]. By observing a fortuitous agreement between the light traffic derivative and the heavy traffic limit for this system under Markovian assumptions, we are able to obtain an approximation to the heavy traffic limit for K-dimensional systems with general inter-arrival and service distributions. By combining this heavy traffic limit with light traffic limits, we generate interpolation approximations for the Fork-Join queue, which agree extremely well with simulation results. In a Fork-Join (FJ) queueing system an upstream fork station splits incoming jobs into N tasks to be further processed by N parallel servers, each with its own queue; the response time of one job is determined, at a downstream join station, by the maximum of the corresponding tasks' response times. This queueing system is useful to the modelling of multi-service systems subject to synchronization constraints, such as MapReduce clusters or multipath routing. Despite their apparent simplicity, FJ systems are hard to analyze. This paper provides the first computable stochastic bounds on the waiting and response time distributions in FJ systems. We consider four practical scenarios by combining 1a) renewal and 1b) non-renewal arrivals, and 2a) non-blocking and 2b) blocking servers. In the case of non blocking servers we prove that delays scale as O(logN), a law which is known for first moments under renewal input only. In the case of blocking servers, we prove that the same factor of log N dictates the stability region of the system. Simulation results indicate that our bounds are tight, especially at high utilizations, in all four scenarios. A remarkable insight gained from our results is that, at moderate to high utilizations, multipath routing 'makes sense' from a queueing perspective for two paths only, i.e., response times drop the most when N = 2; the technical explanation is that the resequencing (delay) price starts to quickly dominate the tempting gain due to multipath transmissions. Approximation techniques are developed to evaluate the performance of symmetric fork-join synchronization delays for K M G 1 queues. For a server utilization spl rho , the mean response time for fork-join requests is expressed as the sum of the mean response time at one of the queues and the mean synchronization delay as follows: R sub K sup F 1 ( spl rho )=R sub 1 ( spl rho )+F sub K spl alpha sub K ( spl rho ) spl sigma sub 1 ( spl rho ), where F sub K is obtained from the previous equation at spl rho =0, R sub 1 ( spl rho ) and spl sigma sub 1 ( spl rho ) are the mean and the standard deviation of response time at any one of the queues, respectively, and spl alpha sub K ( spl rho ) is a low-degree service-time distribution dependent polynomial in spl rho , whose coefficients are determined from simulation results. We also use simulation results to show that when fork-join requests share the servers with local requests, a good approximation (and an upper bound) to the fork-join response time is obtained by treating the components of fork-join response time as independent, i.e., the mean fork-join response time can be approximated by the expected value of the maximum of the response times at the K queues.