View source for Fork–join queue

{{Short description|Type of queue}}
{{Use dmy dates|date=December 2020}}
[[File:Fork-join-queue.svg|thumb|250px|A fork–join queueing node]]
In [[queueing theory]], a discipline within the mathematical [[probability theory|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.<ref>{{Cite journal | last1 = Kim | first1 = C. | last2 = Agrawala | first2 = A. K. | doi = 10.1109/12.16501 | title = Analysis of the fork-join queue | journal = IEEE Transactions on Computers | volume = 38 | issue = 2 | pages = 250 | year = 1989 }}</ref> The model is often used for parallel computations<ref name="rtapprox" /> or systems where products need to be obtained simultaneously from different suppliers (in a warehouse or manufacturing setting).<ref name="serfozo">{{Cite book | last1 = Serfozo | first1 = R. | chapter = Markov Chains | doi = 10.1007/978-3-540-89332-5_1 | title = Basics of Applied Stochastic Processes | pages = 1–98 | series = Probability and Its Applications | year = 2009 | isbn = 978-3-540-89331-8 }}</ref>{{rp|78&ndash;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 computing|parallel]] and [[distributed computing|distributed systems]]."<ref>{{cite tech report | first=Onno | last=Boxma |author-link=Onno J. Boxma |author2=Koole, Ger |author3=Liu, Zhen | title=Queueing-theoretic Solution Methods for Models of Parallel and Distributed Systems | number=BS-R9425 | institution=[[Centrum Wiskunde & Informatica|CWI]] | year=1996 | url=http://oai.cwi.nl/oai/asset/5133/05133D.pdf}}</ref> Few analytical results exist for fork–join queues, but various approximations are known.
The situation where jobs arrive according to a [[Poisson process]] and service times are exponentially distributed is sometimes referred to as a '''Flatto–Hahn–Wright model''' or '''FHW model'''.<ref name="flatto" /><ref>{{citation|first=Paul E.|last=Wright|title=Two parallel processors with coupled inputs|journal=Advances in Applied Probability|volume=24|issue=4|year=1992|pages=986–1007|jstor=1427722|doi=10.2307/1427722|s2cid=124774848 }}</ref><ref name="pinotsi">{{Cite journal | last1 = Pinotsi | first1 = D. | last2 = Zazanis | first2 = M. A. | doi = 10.1016/j.orl.2004.12.005 | title = Synchronized queues with deterministic arrivals | journal = Operations Research Letters | volume = 33 | issue = 6 | pages = 560 | year = 2005 }}</ref>
==Definition==
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.<ref name="serfozo" />
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.<ref>{{cite journal|title=Stationary and Stability of Fork-Join Networks|first1=Panagiotis|last1=Konstantopoulos|first2=Jean|last2=Walrand|author-link2=Jean Walrand|pages=604–614|journal=Journal of Applied Probability|volume=26|date=September 1989|url=http://www2.math.uu.se/~takis/public_html/PAPERS/forkjoin.pdf|issue=3|doi=10.2307/3214417|jstor=3214417|s2cid=120222029 |archive-url=https://web.archive.org/web/20120318232130/http://www2.math.uu.se/~takis/public_html/PAPERS/forkjoin.pdf|archive-date=18 March 2012|url-status=dead}}</ref>
==Applications==
Fork–join queues have been used to model zoned [[RAID]] systems,<ref>{{Cite book | last1 = Lebrecht | first1 = A. S. | last2 = Dingle | first2 = N. J. | last3 = Knottenbelt | first3 = W. J. | doi = 10.1007/978-3-642-02924-0_2 | chapter = Modelling Zoned RAID Systems Using Fork-Join Queueing Simulation | title = Computer Performance Engineering | series = Lecture Notes in Computer Science | volume = 5652 | pages = 16–29 | year = 2009 | isbn = 978-3-642-02923-3 | citeseerx = 10.1.1.158.7363 }}</ref> parallel computations<ref name="rtapprox" /> and for modelling order fulfilment in warehouses.<ref name="serfozo" />
==Response time==
The response time (or sojourn time<ref name="kemper" />) is the total amount of time a job spends in the system.
===Distribution===
Ko and Serfozo give an approximation for the response time distribution when service times are exponentially distributed and jobs arrive either according to a [[Poisson process]]<ref name="ko" /> or a general distribution.<ref>{{Cite journal | last1 = Ko | first1 = S. S. | last2 = Serfozo | first2 = R. F. | doi = 10.1002/nav.20294 | title = Sojourn times in G/M/1 fork-join networks | journal = Naval Research Logistics | volume = 55 | issue = 5 | pages = 432 | year = 2008 | s2cid = 119551482 }}</ref> QIu, Pérez and Harrison give an approximation method when service times have a [[phase-type distribution]].<ref>{{Cite journal | last1 = Qiu | first1 = Zhan | last2 = Pérez | first2 = Juan F. | last3 = Harrison | first3 = Peter G. | year = 2015 | title = Beyond the mean in fork-join queues: Efficient approximation for response-time tails | journal = [[Performance Evaluation]] | volume = 91 | pages =  99–116| doi = 10.1016/j.peva.2015.06.007 | doi-access = free }}</ref>
===Average response time===
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<ref name="nelson">{{Cite journal | last1 = Nelson | first1 = R. | last2 = Tantawi | first2 = A. N. | doi = 10.1109/12.2213 | title = Approximate analysis of fork/join synchronization in parallel queues | journal = IEEE Transactions on Computers | volume = 37 | issue = 6 | pages = 739 | year = 1988 }}</ref>
:<math>\frac{12-\rho}{8\mu(1-\rho)}</math>
where
*<math>\rho=\lambda/\mu</math> is the utilization.
*<math>\lambda</math> is the arrival rate of jobs to all the nodes.
*<math>\mu</math> is the service rate across all the nodes.
In the situation where nodes are [[M/M/1 queue]]s and ''N''&nbsp;>&nbsp;2, Varki's modification of [[mean value analysis]] can also be used to give an approximate value for the average response time.<ref>{{Cite web |url=http://www.cs.unh.edu/~varki/publication/open.pdf |last1=Varki |first1=Elizabeth |last2=Merchant |first2=Arif |last3=Chen |first3=H. |title=M/M/1 Fork-join queue with variable sub-tasks |access-date=29 March 2009 |archive-url=https://web.archive.org/web/20100805150850/http://www.cs.unh.edu/~varki/publication/open.pdf |archive-date=5 August 2010 |url-status=dead }}</ref>
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 [[moment (mathematics)|moments]] of this quantity both in the transient and steady state situations.<ref>{{citation|title=Simple computable bounds for the fork-join queue|url=http://hal.inria.fr/docs/00/07/61/62/PDF/RR-0394.pdf|year=1985|first1=François|last1=Baccelli|first2=A.|last2=Makowski|publisher=National Institute for Research in Computer Science and Control Technical Report|access-date=2011-07-08}}</ref> Kemper and Mandjes show that for some parameters these bounds are not tight and show demonstrate an approximation technique.<ref name="kemper">{{Cite journal | last1 = Kemper | first1 = B. | last2 = Mandjes | first2 = M. | doi = 10.1007/s00291-010-0235-y | title = Mean sojourn times in two-queue fork-join systems: Bounds and approximations | journal = OR Spectrum | volume = 34 | issue = 3 | pages = 723 | year = 2011 | doi-access = free }}</ref> 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.<ref>{{Cite journal | last1 = Alomari | first1 = F. | last2 = Menasce | first2 = D. A. | doi = 10.1109/TPDS.2013.70 | title = Efficient Response Time Approximations for Multiclass Fork and Join Queues in Open and Closed Queuing Networks | journal = IEEE Transactions on Parallel and Distributed Systems | volume = 25 | issue = 6 | pages = 1437–1446 | year = 2013 | s2cid = 422296 }}</ref>
===Subtask dispersion===
The subtask dispersion, defined to be the [[range (statistics)|range]] of service times, can be numerically computed and optimal deterministic delays introduced to minimize the range.<ref>{{Cite book | last1 = Tsimashenka | first1 = I. | last2 = Knottenbelt | first2 = W. J. | chapter = Reduction of Subtask Dispersion in Fork-Join Systems | doi = 10.1007/978-3-642-40725-3_25 | title = Computer Performance Engineering | series = Lecture Notes in Computer Science | volume = 8168 | pages = 325–336 | year = 2013 | isbn = 978-3-642-40724-6 | chapter-url = http://www.doc.ic.ac.uk/~wjk/publications/tsimashenka-knottenbelt-epew-2013.pdf| citeseerx = 10.1.1.421.9780 }}</ref>
==Stationary distribution==
In general the [[Markov chain#Steady-state analysis and limiting distributions|stationary distribution]]{{Broken anchor|date=2024-06-13|bot=User:Cewbot/log/20201008/configuration|target_link=Markov chain#Steady-state analysis and limiting distributions|reason= The anchor (Steady-state analysis and limiting distributions) [[Special:Diff/970694186|has been deleted]].}} of the number of jobs at each queue is intractable.<ref name="ko">{{Cite journal | last1 = Ko | first1 = S. S. | last2 = Serfozo | first2 = R. F. | doi = 10.1239/aap/1093962238 | title = Response times in M/M/s fork-join networks | journal = Advances in Applied Probability | volume = 36 | issue = 3 | pages = 854 | year = 2004 | s2cid = 122581916 }}</ref> Flatto considered the case of two servers (''N=2'') and derived the stationary distribution for the number of jobs at each queue via [[uniformization (probability theory)|uniformization]] techniques.<ref name="flatto">{{Cite journal | last1 = Flatto | first1 = L. | last2 = Hahn | first2 = S. | doi = 10.1137/0144074 | title = Two Parallel Queues Created by Arrivals with Two Demands I | journal = SIAM Journal on Applied Mathematics | volume = 44 | issue = 5 | pages = 1041 | year = 1984 }}</ref> Pinotsi and Zazanis show that a [[product form solution]] exists when arrivals are [[deterministic system|deterministic]] as the queue lengths are then independent [[D/M/1 queue]]s.<ref name="pinotsi" />
===Heavy traffic/diffusion approximation===
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.<ref>{{Cite journal | last1 = Tan | first1 = X. | last2 = Knessl | first2 = C. | doi = 10.1007/BF01149176 | title = A fork-join queueing model: Diffusion approximation, integral representations and asymptotics | journal = Queueing Systems | volume = 22 | issue = 3–4 | pages = 287 | year = 1996 | s2cid = 206789463 }}</ref><ref>{{cite web | url = http://drum.lib.umd.edu/bitstream/1903/5028/1/PhD_90-2.pdf | title = Heavy and Light Traffic Approximations for Queues with Synchronization Constraints (PhD thesis) | first = Subir | last = Varma | publisher = University of Maryland | year = 1990 | access-date = 10 February 2013}}</ref> Under limiting conditions the state space of the synchronisation queues collapses and all queues behave identically.<ref>{{Cite book | last1 = Atar | first1 = R. | last2 = Mandelbaum | first2 = A. | last3 = Zviran | first3 = A. | doi = 10.1109/Allerton.2012.6483303 | chapter = Control of Fork-Join Networks in heavy traffic | title = 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton) | pages = 823 | year = 2012 | isbn = 978-1-4673-4539-2 | s2cid = 18115820 | chapter-url = http://webee.technion.ac.il/people/atar/FJN.pdf}}</ref>
==Join queue distribution==
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.<ref name="nelson" /> Heterogeneous service rates and distribution [[asymptotic analysis]] are considered by Li and Zhao.<ref>{{Cite journal | last1 = Li | first1 = J. | last2 = Zhao | first2 = Y. Q. | doi = 10.1017/S0269964810000112 | title = On the Probability Distribution of Join Queue Length in a Fork-Join Model | journal = Probability in the Engineering and Informational Sciences | volume = 24 | issue = 4 | pages = 473 | year = 2010 | s2cid = 124693767 }}</ref>
==Networks of fork–join queues==
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).<ref>{{Cite book | last1 = Ko | first1 = S. S. | chapter = Cycle Times in a Serial Fork-Join Network | doi = 10.1007/978-3-540-74472-6_62 | title = Computational Science and Its Applications – ICCSA 2007 | series = Lecture Notes in Computer Science | volume = 4705 | pages = 758–766 | year = 2007 | isbn = 978-3-540-74468-9 }}</ref>
==Split–merge model==
A related model is the split–merge model, for which analytical results exist.<ref name="rtapprox">{{cite conference |last1=Lebrecht |first1=Abigail |last2=Knottenbelt |first2=William J. |date=June 2007 |title=Response Time Approximations in Fork-Join Queues |conference=23rd Annual UK Performance Engineering Workshop (UKPEW) |url=http://pubs.doc.ic.ac.uk/forkjoin/forkjoin.pdf |access-date=2 July 2009 |archive-url=https://web.archive.org/web/20131029195204/http://pubs.doc.ic.ac.uk/forkjoin/forkjoin.pdf |archive-date=29 October 2013 |url-status=dead }}</ref><ref>{{Cite book | last1 = Harrison | first1 = P. | author-link1 = Peter G. Harrison| last2 = Zertal | first2 = S. | chapter = Queueing Models with Maxima of Service Times | doi = 10.1007/978-3-540-45232-4_10 | title = Computer Performance Evaluation. Modelling Techniques and Tools | series = Lecture Notes in Computer Science | volume = 2794 | pages = 152–168 | year = 2003 | isbn = 978-3-540-40814-7 }}</ref> Exact results for the split-merge queue are given by Fiorini and Lipsky.<ref>{{Cite journal | last1 = Fiorini | first1 = Pierre M. | title = Exact Analysis of Some Split Merge Queues | journal = SIGMETRICS Performance Evaluation Review | volume = 43| issue = 2| pages = 51–53| year = 2015| doi = 10.1145/2825236.2825257 | s2cid = 26219594 }}</ref>
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.
==Generalized (n,k) fork-join system ==
A generalization of the fork-join queueing system is the <math>(n,k)</math> fork-join system where the job exits the system when any <math> k </math> out of <math>n</math> tasks are served. The traditional fork-join queueing system is a special case of the <math> (n,k) </math> system when <math> k = n </math>. Bounds on the mean response time of this generalized system were found by Joshi, Liu and Soljanin.<ref name="jls_allerton">{{cite conference |last1=Joshi |first1=Gauri |last2=Liu |first2=Yanpei |last3=Soljanin |first3=Emina |date=Oct 2012 |title=Coding for Fast Content Download |conference= Allerton Conference on Communication, Control and Computing | arxiv = 1210.3012|bibcode=2012arXiv1210.3012J }}</ref><ref name="jls_jsac">{{cite conference |last1=Joshi |first1=Gauri |last2=Liu |first2=Yanpei |last3=Soljanin |first3=Emina |date= May 2014 |title=On the Delay-Storage trade-off in Content Download from Coded Distributed Storage |conference= Journal on Selected Areas of Communications | arxiv = 1305.3945|bibcode=2013arXiv1305.3945J }}</ref>
==References==
{{reflist|colwidth=30em}}
{{Queueing theory}}
{{DEFAULTSORT:Fork-Join Queue}}
[[Category:Single queueing nodes]]