1
$\begingroup$

I was going through Distributed Systems by Maarten van Steen & Andrew S. Tanenbaum. While going through size scalability of systems, I came across this in a note.



enter image description here



I want to know the derivation of this formula. Also, for $\left ( 1 -\frac{\lambda }{\mu} \right )$ to be greater than zero, $\lambda$ should be less than $\mu$. That means system rate of processing requests is faster than request arrival rate, then how come requests would accumulate at any moment? Even if the system starts processing after the first request arrives and meanwhile second request is already being buffered, the system would finish processing the first request before the second request completes arrival. So no request would remain in buffer then.

$\endgroup$
1

2 Answers 2

1
$\begingroup$

I have to admit that this is pretty unintuitive. I calculated many equations today, not reaching any formula close to what it says in the book. However, I managed to get my hands on the book and a few other resources, and with a little digging, I found something that might help you.

Let's look at the equation from a statistics point of view. Let's say that the mean rate of request arrival is $\lambda$ and the mean process calculation rate is $\mu$. Now you can argue that the probability that you find a certain process in the system itself is $\frac{\lambda}{\mu}$.
Hence, the probability of finding $k$ processes in the system is equal to $$ \Bigl(\frac{\lambda}{\mu}\Bigr)^k $$ But at any given time, there are packages arriving in the system and packages going out of the system. So at the interval that we are interested in viewing the system, no new packages should be found in the system. The probability of that equals $(1-\frac{\lambda}{\mu})$. Putting everything together we get the formula: $$ p_k = \Bigl(1-\frac{\lambda}{\mu}\Bigr)\Bigl(\frac{\lambda}{\mu}\Bigr)^k $$ This is actually equal to the probability of finding exactly $k$ packages in the system.

I'll keep digging and update the answer if anything new comes up.

$\endgroup$
1
  • $\begingroup$ What do you mean by probability of finding a certain process in the system ?. Either it's probability of finding exactly one process or probability of finding atleast one process. If it's the first then subtracting it from one isn't enough to find probability of no process in the system. If it's the second then we can't seem to calculate the probability of k processes in the system with it. $\endgroup$
    – Dhruv
    Sep 1, 2022 at 1:43
1
$\begingroup$

It took some time but I finally found how to derive the above equation. This thing requires the knowledge of continuous Markov chains. I learned about them from these two videos which was enough to understand the concept.

Now the derivation is here on Wikipedia. Basically, our system is an M/M/1 queue and can be modeled as in the following pic.

state diagram with a numbered chain of nodes, transition on lambda moves forward and mu moves back

Each number represents the number of processes in the system. The rate matrix is written as follows.

$$ Q = \begin{pmatrix} -\lambda & \lambda & & & & \\ \mu & -(\mu+\lambda) & \lambda & & & \\ & \mu & -(\mu+\lambda) & \lambda & & \\ & & \mu & -(\mu+\lambda) & \lambda & \\ & & & & \ddots & \end{pmatrix} $$ In steady state ($Q \pi = 0$, where $\pi$ is just the probability distribution $P_{0}, P_{1}, P_{2}, \ldots$), the equations are $$ \begin{eqnarray*} \mu P_{1} &=& \lambda P_{0} \\ \lambda P_{0} + \mu P_{2} &=& (\lambda + \mu) P_{1} \\ \lambda P_{n-1} + \mu P_{n+1} &=& (\lambda + \mu) P_{n} \end{eqnarray*} $$ which gives $$ P_{n} = \frac{\lambda}{\mu} P_{n-1},\quad\text{$n=1,2,...$} $$ and the fact that system is going to be in any one of the following states at any moment of time leads to $$ P_{0} + P_{1} + P_{2} + \ldots = 1 $$ So, finally we have $$ P_{n} = \rho^{n}(1-\rho) $$ where $\rho = \cfrac{\lambda}{\mu}$ in steady state.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.