Fork–join queue

In queueing theory, a discipline within the mathematical theory of probability, a fork–join queue is a queue where incoming jobs are split on arrival for service by numerous servers and joined before departure.^[1] The model is often used for parallel computations^[2] or systems where products need to be obtained simultaneously from different suppliers (in a warehouse or manufacturing setting).^{[3]: 78–80} The key quantity of interest in this model is usually the time taken to service a complete job. The model has been described as a "key model for the performance analysis of parallel and distributed systems."^[4] Few analytical results exist for fork–join queues, but various approximations are known.

The situation where jobs arrive according to a

On arrival at the fork point, a job is split into N sub-jobs which are served by each of the N servers. After service, sub-job wait until all other sub-jobs have also been processed. The sub-jobs are then rejoined and leave the system.[3]

For the fork–join queue to be stable the input rate must be strictly less than sum of the service rates at the service nodes.^[8]

Fork–join queues have been used to model zoned RAID systems,^[9] parallel computations^[2] and for modelling order fulfilment in warehouses.^[3]

The response time (or sojourn time^[10]) is the total amount of time a job spends in the system.

Ko and Serfozo give an approximation for the response time distribution when service times are exponentially distributed and jobs arrive either according to a

An exact formula for the average response time is only known in the case of two servers (N=2) with exponentially distributed service times (where each server is an M/M/1 queue). In this situation, the response time (total time a job spends in the system) is^[14]

${\displaystyle {\frac {12-\rho }{8\mu (1-\rho )}}}$

where

• ${\displaystyle \rho =\lambda /\mu }$ is the utilization.
• ${\displaystyle \lambda }$ is the arrival rate of jobs to all the nodes.
• ${\displaystyle \mu }$ is the service rate across all the nodes.

In the situation where nodes are M/M/1 queues and N > 2, Varki's modification of mean value analysis can also be used to give an approximate value for the average response time.^[15]

For general service times (where each node is an M/G/1 queue) Baccelli and Makowski give bounds for the average response time and higher moments of this quantity both in the transient and steady state situations.^[16] Kemper and Mandjes show that for some parameters these bounds are not tight and show demonstrate an approximation technique.^[10] For heterogeneous fork-join queues (fork-join queues with different service times), Alomari and Menasce propose an approximation based on harmonic numbers that can be extended to cover more general cases such as probabilistic fork, open and closed fork-join queues.^[17]

The subtask dispersion, defined to be the range of service times, can be numerically computed and optimal deterministic delays introduced to minimize the range.^[18]

In general the

When the server is heavily loaded (service rate of the queue is only just larger than arrival rate) the queue length process can be approximated by a reflected Brownian motion which converges to the same stationary distribution as the original queueing process.^[19][20] Under limiting conditions the state space of the synchronisation queues collapses and all queues behave identically.^[21]

Once jobs are served, the parts are reassembled at the join queue. Nelson and Tantawi published the distribution of the join queue length in the situation where all servers have the same service rate.^[14] Heterogeneous service rates and distribution asymptotic analysis are considered by Li and Zhao.^[22]

An approximate formula can be used to calculate the response time distribution for a network of fork–join queues joined in series (one after the other).^[23]

A related model is the split–merge model, for which analytical results exist.^[2][24] Exact results for the split-merge queue are given by Fiorini and Lipsky.^[25] Here on arrival a job is split into N sub-tasks which are serviced in parallel. Only when all the tasks finish servicing and have rejoined can the next job start. This leads to a slower response time on average.

A generalization of the fork-join queueing system is the ${\displaystyle (n,k)}$ fork-join system where the job exits the system when any ${\displaystyle k}$ out of ${\displaystyle n}$ tasks are served. The traditional fork-join queueing system is a special case of the ${\displaystyle (n,k)}$ system when ${\displaystyle k=n}$. Bounds on the mean response time of this generalized system were found by Joshi, Liu and Soljanin.^[26][27]