Consider two parallel, independent $M/M/1/1$ queues (denoted $Q_i, Q_j$) with identical arrival rate $\lambda$ and service rate $\mu$, using FCFS (First Come First Served) discipline. Note that the last $1$ in the notation $M/M/1/1$ means that the system is of finite capacity $N = 1$. In other words, for each queue system, if there is some customer in service, no more customers can enter it.

For each customer $c$, its service-starting time, service-finishing time, and service interval are denoted by $c_{st}$, $c_{ft}$, and $[c_{st}, c_{ft}]$, respectively.

My Problems: Consider the following two concurrency related problems in such queueing system in the long run.

(1) Given customer $c$ served by $Q_i$, what is the probability that it starts during the service interval of some customer $c'$ served by $Q_j$ (i.e., $c_{st} \in [c'_{st}, c'_{ft}]$)?

Note that $c'$ will be unique if it exists, as shown in the figure.

(2) Conditioning on (1), what is the distribution of the service-starting time lag $c_{st} - c'_{st}$, as shown in the figure.

lag time

P.S. A solution to the first problem has been given by @user137846 at MathOverflow. However, I am not sure whether it is true or not. I am seeking more comments and detailed explanations.

Edit: Although I have accepted this answer, I am not absolutely certain of its correctness. Comments and other answers are still highly appreciated.


The answer on MathOverflow looks reasonable. For the second part as the two queues are independent the time delay is an exponential distribution with parameter according to the arrival rate in the second queue because the exponential distribution has the memoryless property.

  • $\begingroup$ Thanks. However, before accepting it as the answer or giving any useful comments, I have to take some time to understand it. $\endgroup$ – hengxin May 15 '14 at 14:35
  • $\begingroup$ In the answer to the first problem provided by @user137846 in MathOverflow, it says that the probability that a customer starts during the service period of another customer is the probability that one queue is empty and the other is full. Why is this? After all, in these two states (i.e., $(0,1)$ and $(1,0)$), no new customer arrives. Do we need to consider the transitions of $(0,1) \to (1,1)$ and $(1,0) \to (1,1)$ which capture the arrival of a new customer? Do I misunderstand the PASTA property completely? $\endgroup$ – hengxin May 18 '14 at 13:28
  • $\begingroup$ My further attempt: The probability that a customer $c$ in queue $Q_i$ starts during the service period of another customer $c'$ of $Q_j$ (denoted by event $E$) equals the probability that when $c$ arrives at $Q_i$, it finds $Q_i$ empty (denoted $E_i$) and as a bystander $Q_j$ full (denoted $E_j$). The two events $E_i$ and $E_j$ are independent (formal verification needed?). Therefore, $P(E) = P(E_i \land E_j) = P(E_i) \cdot P(E_j) = P_0 \cdot P_1 = \frac{\mu \lambda}{(\mu + \lambda)^{2}}$. The last but one equality is due to the PASTA property. Is this argument reasonable? Thanks. $\endgroup$ – hengxin May 18 '14 at 14:19
  • $\begingroup$ For the second problem, is the service-starting time lag $c_{st} - c'_{st}$ exactly the inter-arrival time of the second queue, which is exponential with rate $\lambda$? Do you also mean this? How does the memoryless property come in? $\endgroup$ – hengxin May 20 '14 at 8:30

Your Answer

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

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