According to the wikipedia article:

There are $N$ queues, the index of a single queue is $i \in N$.

For the fork–join queue to be stable the input rate $\lambda$ must be strictly less than sum of the service rates $\mu_i$ at the service nodes.

Let's forget about fork-join queues for a moment and consider a single queue. When is it stable? Well, the arrival rate $\lambda$ (number of incoming jobs per unit time) needs to be smaller than service rate $\mu$ (number of completed jobs per unit time). If the condition $\lambda < \mu$ is not satisfied, then the queue will grow infinitely. That's obvious.

I'm not convinced if the rule regarding fork-join quoted above is correct. If there are $N$ queues in the Fork-join setup, and we assume the service rate on every server to be equal $\mu_1=\mu_2=...=\mu_N$, then it's essentially the same thing as having a single queue. The job will not be completed until all sub-jobs have completed. If you visualised the work of every server and their queues, they would all look identical (because of identical service rates). So all queues grow at equal rate on every server. And all sub-jobs are completed at the same time. The service rate of completion of all sub-jobs is equal to the service rate of jobs.

That's why I think the rule $\lambda < \mu_1+\mu_2+...+\mu_N$ doesn't guarantee the system will be stable. In the fork join system case described above, it's necessary that $\lambda < \mu_i$, otherwise the queue will grow forever.

EDIT: Apparently I forgot there's another queue for the sub-jobs that have been processed already.

So, could anyone provide an easy to understand proof the fact that $\lambda < \mu_1+\mu_2+...+\mu_N$ guarantees the system is stable?

  • $\begingroup$ @stochasticboy321 yes, I have $n$ servers. When a job arrives to the system at rate $\lambda$ it is split into $n$ subjobs, and each sub-job is then passed to one of $n$ servers. Is it what you assumed? $\endgroup$ – user299869 Dec 19 '15 at 22:01
  • $\begingroup$ No, a sub-job has to visit only one server. Servers process sub-jobs and then merge the results, once this is done the whole job is completed. $\endgroup$ – user299869 Dec 19 '15 at 22:12
  • $\begingroup$ Yeah, I see where I've missed the point. Sorry for the inconvenience, I'll delete the stuff above. Let me think, maybe I can still answer this. $\endgroup$ – stochasticboy321 Dec 19 '15 at 22:13
  • $\begingroup$ Actually I'm not inventing anything new in my question, I'd only like to figure out the proof for the quoted theorem (from the wikipedia article about fork-join queues). $\endgroup$ – user299869 Dec 19 '15 at 22:15
  • $\begingroup$ "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" - the key thing to remember is that a sub-job is processed by only one server, the Wiki definition is not exactly precise at this. $\endgroup$ – user299869 Dec 19 '15 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.