**Queueing Model:**


Consider $n$ independent, parallel $M/M/1$ queues with identical arrival rate $\lambda$ and service rate $\mu$. For each $M/M/1$ queue, we use the FCFS (First Come First Served) discipline and *if there is some customer in service, no more customers can enter it*. 


For each customer $c$, its start time, finish time, service interval are denoted by $c\_{.st}$, $c\_{.ft}$, and $[c\_{.st}, c\_{.ft}]$, respectively.


**Problem:**


I want to study some concurrency-related problems in such queueing system in the long run. 



> 
> (1). Given two different $M/M/1$ queues $Q\_i$ and $Q\_j$ and a 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}]$)?
> 
> 
> 


Notice that $c'$ will be unique if $c\_{.st} \in [c'\_{.st}, c'\_{.ft}]$ holds (see the figure below).



> 
> (2). Given a customer $c'$ served by $Q\_j$, what is the probability that there are exactly $m$ customers each of which (denoted $c''$) *finishes* during the service interval of $c'$ (i.e., $c''\_{.ft} \in [c'\_{.st}, c'\_{.ft}]$)?
> 
> 
> 


Notice that there may be more than one customer in $Q\_k$ ($Q\_k \neq Q\_j$) satisfying the condition $c''\_{.ft} \in [c'\_{.st}, c'\_{.ft}]$ (see the figure below).



> 
> (3) *Combine problems (1) and (2):*  
> 
>  Given two different $M/M/1$ queues $Q\_i$ and $Q\_j$ and a customer $c$ served by $Q\_i$, let $c'$ be the customer served by $Q\_j$ satisfying $c\_{.st} \in [c'\_{.st}, c'\_{.ft}]$ (i.e., $c$ *starts* during the service interval of $c'$).  
> 
>  The set of customers that finishes before $c$ starts is denoted by $c^{\prec} = \{c'': c''\_{.ft} \le c\_{.st} \}$.  
> 
>  What is the probability that there are **exactly $k$ customers in $c^{\prec}$** each of which (denoted by $c''$) *finishes* during the service interval of $c'$ (i.e., $c''\_{.ft} \in [c'\_{.st}, c'\_{.ft}]$)?
> 
> 
> 


[parallelmm1\_threeproblems http://i1.tietuku.com/5eeddcb2557fb93c.png](http://i1.tietuku.com/5eeddcb2557fb93c.png)



> 
> In addition, are such *concurrency-related problems* are the typical ones studied in the literature on queueing theory? Any references related to similar problems are also well appreciated.
> 
> 
> 



Concurrency related problems in $n$ independent, parallel $M/M/1$ queues
Let $Y(t)=(X^{(1)}(t), X^{(2)}(t))$ be the vector of the number of customers in queues $1$ and $2$ at time $t$. Then, $Y(t)$ is a Continuous Time Markov chain with four states $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$. The stationary distribution of this chain is:
\begin{align\*}
 \mathbb{P}(Y(\infty) = (0,1)) = \frac{\lambda}{\mu+\lambda}\frac{\mu}{\mu+\lambda} =: \pi\_{0,1} \\
 \mathbb{P}(Y(\infty) = (1,0)) = \frac{\lambda}{\mu+\lambda}\frac{\mu}{\mu+\lambda} =: \pi\_{1,0} \\
 \mathbb{P}(Y(\infty) = (1,1)) = \frac{\lambda}{\mu+\lambda}\frac{\lambda}{\mu+\lambda} =: \pi\_{1,1}
\end{align\*}


For your first question, using the Poisson Arrivals See Time Averages (PASTA) property of arrivals, 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 which is 
$$
\frac{1}{2}(\pi\_{1,0} + \pi\_{0,1})
$$.


For the second question, first condition on whether the customer which starts at $c\_{st}$ (called the tagged customer) sees the other queue as empty or not. If it sees the other queue empty, then the number of departures, $D$, during its service interval, will have the distribution:
$$
\mathbb{P}(D = m) = P\left(\sum\_{i=1}^m (A\_i + S\_i) < Z < \sum\_{i=1}^{m+1} (A\_i + S\_i) \right),
$$
where $A\_i$ are i.i.d. $exponential(\lambda)$ random variables corresponding to the inter-arrival times of customers in the other queue, $S\_i$ are i.i.d. $exponential(\mu)$ corresponding to the service times of these customers, and $Z$ is $exponential(\mu)$ is the service time of the tagged customer. The probability of the case when tagged customer sees the other queue busy can also be written in a similar way.


