Stationary Analysis of Finite-Capacity M/M/1 Fork-Join Queues
Pierre Fiorini
Fork–join queues are a core abstraction for synchronized parallel services, yet exact stationary analysis remains limited. For the infinite-buffer $M/M/1$ fork–join queue, closed-form results exist only in the two-server case. For finite-capacity $M/M/1/K_i$ systems, no broadly usable closed-form stationary characterization is known; direct CTMC solution is numerically exact but quickly becomes computationally infeasible. For $N\ge 3$, in both the infinite and finite cases, the stationary distribution and job-level delay metrics are otherwise approached through approximations, bounds, asymptotics, or simulation. For finite-capacity $M/M/1/K_i$ fork–join systems with all-or-nothing admission, this paper develops a regenerative busy-period framework coupled with a deterministic staged-particle solver. The empty state is a regeneration point, each busy period decomposes into admitted-arrival stages, and exact stage-occupation identities recover the stationary distribution, blocking probability, effective throughput, queue-length moments, and admitted-arrival Erlang-mixture latency CDFs once the stage distributions are known. The algorithm propagates those stage distributions by systematic deterministic quantization with particle resolution~$P$ and, in the fully homogeneous case, exploits exact histogram compression from $(K+1)^N$ to $\binom{N+K}{K}$. On every finite-capacity model the exact stage kernel is uniformly absorbing, one-stage transport and occupation errors are $O(P^{-1})$, and we prove a particle-limit consistency theorem: if $P\to\infty$ and the stage cutoff grows so the geometric tail vanishes, the staged solver converges in $\ell_1$ to the true stationary distribution. Numerical experiments benchmark the method against exact CTMC baselines on small models and against independent discrete-event simulation on homogeneous and heterogeneous benchmarks up to $N=1000$ synchronized servers, where the exact reduced chain already has $\binom{1010}{10}\approx 2.91\times 10^{23}$ states.