Queues wait for other queues- A communication problem

Question

I am working on a problem which involves a single server that requires multiple inputs to do a computation. Each of these inputs arrive as a Poisson process with rate $\lambda$. Hence, a situation arises where a particular input from one queue has to wait for all other corresponding inputs from other queues to arrive.

I need to calculate the channel capacity of such a system. Assume $N$ inputs to the server ($N$ parallel queues) and the service time of the server is $\operatorname{Exp}(\mu)$.

If it were only one input (trivial case with no waiting for other queues), I could use the Pollaczek-Khinchin formula for queue and the fact that the capacity is $\lambda$ times the Laplace transform of waiting time distribution to find the capacity (as described in arXiv:1804.00906v3)

However, in this case the service time becomes layer dependent since there is an additional wait of $\max_N (\Gamma(j,\lambda)) - \Gamma(j,\lambda)$ for a bit in the $j^{th}$ "layer" or the queue due to the waiting policy described above. Hence the total service time distribution becomes $\max_N (\Gamma(j,\lambda)) - \Gamma(j,\lambda) + \operatorname{Exp}(\mu) $ which is dependent on the position in the queue. I am not sure how to proceed in this case and any help would be much appreciated.

Answer 1

If I understand the setup correctly, this is a null recurrent or transient Markov chain. There is therefore no stationary system state distribution, so there is very likely no stationary waiting time distribution.

Imagine first the case where $N = 2$ and $\mu = \infty$ (i.e. service is instant). Then if the queue lengths at time $t$ are $Q_1(t)$ and $Q_2(t)$, the state of the system can be boiled down to $X(t) = Q_1(t) - Q_2(t)$. But $X(t)$ is clearly an unbiased $\pm 1$ random walk on the integers where all transitions have rate $\lambda$, which is a classic null recurrent Markov chain. Because $X(t)$ doesn't converge to a stationary distribution, neither does $(Q_1(t), Q_2(t))$.

In the general case, if $Q_i(t)$ is the length of queue $i$ at time $t$, then I think for any two queues, $Q_i(t) - Q_j(t)$ is again a Markov chain, and it's again a null recurrent random walk. The key observation is that each departure and each non-$\{i, j\}$ arrival leaves $Q_i(t) - Q_j(t)$ unchanged, so the dynamics of this difference are identical to the dynamics of $X(t)$ in the special case above. Because $X(t)$ doesn't converge to a stationary distribution, neither does $(Q_1(t), \dots, Q_N(t))$.