Fork-Join queue stability

150 Views Asked by At

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?