Stationary states of generalized Jackson networks on countable graphs beyond the Rybko-Shlosman sufficient conditions

Rybko and Shlosman (Markov Processes and Related Fields 22 (2016); arXiv:1308.1524) proved existence, uniqueness, and relaxation of stationary states for mean-field limits of open generalized Jackson networks (arbitrary, non-exponential service times) on countable graphs, under three groups of sufficient hypotheses: regularity conditions 1-5 on the service-time densities, underload inequalities, and membership of the routing matrix in one of three transience classes (the Kel'bert-Kontsevich-Rybko double semi-stochastic class with vanishing maximal invariant measure, an $L^1$ column-decay class, and a single-column propagation class). Three linked questions remain open: (1) whether the existence, uniqueness, and relaxation conclusions survive under weaker service-law hypotheses such as heavy tails or irregular densities; (2) a necessary-and-sufficient characterization of the substochastic routing matrices for which zero is the only bounded invariant measure, i.e. the exact border between transient and non-transient routing operators; (3) the stationary behavior of the overloaded regime where the underload inequalities fail - existence, multiplicity, or nonexistence of stationary measures and possible phase transitions in the mean-field limit.

Background

A Jackson network (JN) is an open network of single-server queues: external customers arrive at the nodes as independent Poisson streams, after service completion at node $i$ a customer is routed to node $j$ with probability $p_{ij}$ or leaves the network with the complementary probability, and service times are independent exponentials. A generalized Jackson network (GJN) is the same model with arbitrary (non-exponential) service-time distributions. For finite networks of either kind, the classical theory characterizes existence and uniqueness of the stationary distribution through the underload condition: at every node the total input rate, external plus rerouted, is strictly below the service capacity. For networks on countable (infinite) graphs this does not settle the question, because the routing operator itself can transport mass to infinity: Kel'bert, Kontsevich and Rybko (1988) obtained existence and uniqueness criteria for infinite JNs under a double semi-stochastic routing condition (a nonnegative matrix whose row and column sums are both at most 1), but their network results are proved for exponential service times.

Rybko and Shlosman treat the GJN case in a mean-field setting. Servers are grouped into types; after service, a customer of type $i$ becomes type $j$ with probability $p_{ij}$, or leaves with probability $p_{i\infty}$, and within a type the customer chooses uniformly among the $N$ servers of that type. Taking $N\to\infty$ with finitely many, or countably many, types yields a Non-Linear Markov Process (NLMP): a Markov evolution of a measure-valued state whose transition rates depend on the current measure itself, in the spirit of McKean-Vlasov limits. The Poisson Hypothesis (PH) for such networks predicts that, in the combined long-time and large-size limit, the input flow to each node is close to a Poisson flow with a constant rate, distinct nodes are asymptotically independent, and, in its strong form, the limiting behavior does not depend on the initial state. Earlier work of the same authors proved the PH in simple cases and also produced counterexamples: closed or oscillatory networks whose nonlinear Markov evolutions never equilibrate, indicating that the PH can fail at high load, the load playing the role of temperature in statistical mechanics.

The 2016 paper proves the weak PH (convergence to the NLMP with Poisson input flows) and, under three groups of hypotheses, the strong PH: convergence of the flow rates to limits independent of the initial state, and uniqueness of the limiting stationary product state. Here $\lambda_i(t)$ denotes the rate of the total input flow to servers of type $i$ and $b_i(t)$ the rate of the exit (service-completion) flow from type $i$, the two being related by $\lambda_i(t) = v_i + \sum_j b_j(t)\,p_{ji}$. The hypotheses are: (A) the service-time densities $p_i(t)$ satisfy conditions 1-5, namely positivity with a uniform upper bound, the strong Lipschitz bound $|p_i(t+\Delta t)-p_i(t)|\le C\,p_i(t)|\Delta t|$, uniform $(2+\delta)$-moment bounds on the conditional residual service times, differentiability with uniform control of the residual density at zero $p_{i,\tau}(0)$ and of its $\tau$-derivative, and existence of the $\tau\to\infty$ limits, inherited from the earlier Poisson-Hypothesis machinery; (B) the underload inequalities $\mathbb{E}(\eta_i)\bar V_i<1$, where $\eta_i$ is the service time at a server of type $i$, $V=(v_i)$ is the vector of external arrival rates, and $\bar V = V + VP + VP^2 + \cdots$ is the vector of total input rates (external plus rerouted) at each type; and (C) the routing matrix $P$ belongs to one of three transience classes: the KKR double semi-stochastic class with vanishing maximal invariant measure (Theorem 5), an $L^1$ column-decay class (Theorem 7), or a single-column propagation class (Theorem 8). Here a bounded invariant measure of the substochastic matrix $P$ is a nonnegative bounded sequence $\lambda$ with $\lambda = \lambda P$; zero is always invariant, and the vanishing of all bounded invariant measures is the contraction property that forces the network to forget its initial state. Within the double semi-stochastic class there is a maximal invariant measure $\lambda^*$: $\lambda^*(i)$ is the probability that the dual Markov chain, with transition probabilities $p^*_{ij}=p_{ji}$ and an absorbing exit state $\infty$, started at $i$ never reaches $\infty$; the paper recovers the equivalence that zero is the only bounded invariant measure if and only if $\lambda^*=0$. Outside that class only sufficient conditions are known.

Problem Statement

Extend the stationary-state theory for mean-field limits of open generalized Jackson networks on countable graphs beyond the sufficient regime established by Rybko and Shlosman (2016). That theory asserts, under the hypotheses (A) service-time laws satisfying conditions 1-5, (B) the underload inequalities $\mathbb{E}(\eta_i)\bar V_i<1$ with $V=(v_i)$ the external arrival rates and $\bar V = V + VP + VP^2 + \cdots$ the total input rates, and (C) membership of the routing matrix $P$ in the transience classes of Theorem 5, 7, or 8, that the flow rates $\lambda_i(t)$, $b_i(t)$ converge to limits independent of the initial state and the stationary state is unique. Three linked facets, one common objective:

1. Service-law regularity. Determine to what extent conditions 1-5 can be weakened while preserving existence, uniqueness, and relaxation: prove the conclusions for service laws violating one or more of the conditions - heavier tails where the uniform $(2+\delta)$-moment bounds fail, or densities lacking the strong Lipschitz property or the uniform control of $p_{i,\tau}(0)$ and its $\tau$-derivative - or show by explicit counterexample that some of these conditions are necessary for the conclusions. This facet is resolved only by deciding, for each of conditions 1-5, whether it can be dropped; a proof or counterexample that settles one condition leaves the status of the conditions it does not address open.

2. Routing transience. For an irreducible substochastic routing matrix $P$ (one whose directed graph of positive entries is strongly connected) with killing probabilities $p_{i\infty}$, characterize by necessary and sufficient conditions when zero is the only bounded nonnegative invariant measure $\lambda = \lambda P$. Within the double semi-stochastic class this is settled by the KKR equivalence; the $L^1$ column-decay and single-column propagation classes are only sufficient. A resolution fixes the exact border between transient and non-transient routing operators, which governs uniqueness of stationary states and initial-state forgetting.

3. Overload. Describe the stationary and long-time behavior when the underload inequalities fail: existence, multiplicity, or nonexistence of stationary measures for the nonlinear Markov limit and the associated flow-rate dynamics $\lambda_i(t)$, $b_i(t)$, and whether phase transitions - multiple stationary solutions whose selection depends on the initial state - occur, in analogy with the proven failures of the Poisson Hypothesis in closed and mobile-server networks.

All three facets are posed for the general setting of countably many types and arbitrary service laws.

References

1. A. Rybko, S. Shlosman, Stationary states of the generalized Jackson networks. Markov Processes and Related Fields 22(4), 759-774 (2016); preprint arXiv:1308.1524, https://arxiv.org/abs/1308.1524; zbMATH Zbl 1361.60084, https://zbmath.org/?q=an%3A1361.60084
2. M. Ya. Kel'bert, M. L. Kontsevich, A. N. Rybko, On Jackson networks on denumerable graphs. Theory of Probability and its Applications 33(2), 358-361 (1988). DOI 10.1137/1133055, https://doi.org/10.1137/1133055
3. A. Rybko, S. Shlosman, Poisson Hypothesis for Information Networks. I. Moscow Mathematical Journal 5(3), 679-704 (2005). DOI 10.17323/1609-4514-2005-5-3-679-704, https://doi.org/10.17323/1609-4514-2005-5-3-679-704
4. A. Rybko, S. Shlosman, Poisson Hypothesis for Information Networks. II. Moscow Mathematical Journal 5(4), 927-959 (2005). DOI 10.17323/1609-4514-2005-5-4-927-959, https://doi.org/10.17323/1609-4514-2005-5-4-927-959
5. A. Rybko, S. Shlosman, Phase transitions in the queuing networks and the violation of the Poisson hypothesis. Moscow Mathematical Journal 8(1), 159-180 (2008). DOI 10.17323/1609-4514-2008-8-1-159-180, https://doi.org/10.17323/1609-4514-2008-8-1-159-180
6. A. Rybko, S. Shlosman, A. Vladimirov, Spontaneous resonances and the coherent states of the queuing networks. Journal of Statistical Physics 134, 67-104 (2009). DOI 10.1007/s10955-008-9658-0, https://doi.org/10.1007/s10955-008-9658-0
7. A. Rybko, S. Shlosman, A. Vladimirov, Absence of breakdown of the Poisson hypothesis. I. Closed networks at low load. Markov Processes and Related Fields 16(2), 267-285 (2010); preprint arXiv:0811.3577, https://arxiv.org/abs/0811.3577
8. A. Rybko, S. Shlosman, A. Vladimirov, Poisson hypothesis for open networks at low load. Moscow Mathematical Journal 17(1), 145-160 (2017). DOI 10.17323/1609-4514-2017-17-1-145-160, https://doi.org/10.17323/1609-4514-2017-17-1-145-160; preprint arXiv:1408.7034, https://arxiv.org/abs/1408.7034
9. F. Baccelli, A. N. Rybko, S. B. Shlosman, Queueing networks with mobile servers: the mean-field approach. Problems of Information Transmission 52(2), 178-199 (2016). DOI 10.1134/S0032946016020071, https://doi.org/10.1134/S0032946016020071; preprint arXiv:1311.3898, issued under the title 'Queuing Networks with Varying Topology -- A Mean-Field Approach', https://arxiv.org/abs/1311.3898
10. F. Baccelli, A. Rybko, S. Shlosman, A. Vladimirov, Metastability of queuing networks with mobile servers. Journal of Statistical Physics 173, 1227-1251 (2018). DOI 10.1007/s10955-018-2023-z, https://doi.org/10.1007/s10955-018-2023-z; preprint arXiv:1704.02521, https://arxiv.org/abs/1704.02521
11. A. A. Vladimirov, S. A. Pirogov, A. N. Rybko, S. B. Shlosman, Propagation of chaos and Poisson hypothesis. Problems of Information Transmission 54(3), 290-299 (2018). DOI 10.1134/S0032946018030080, https://doi.org/10.1134/S0032946018030080; preprint arXiv:1610.08492, https://arxiv.org/abs/1610.08492
12. R. Atar, Mean field limits of large Jackson networks in heavy traffic. Preprint arXiv:2606.01209 (2026), https://arxiv.org/abs/2606.01209
13. L. T. Clarke, G. Pang, R. Wu, Growing open Markovian Jackson networks: fluid limit and infinite-dimensional Skorokhod problem. Preprint arXiv:2605.16868 (2026), https://arxiv.org/abs/2605.16868
14. J. G. Dai, P. Glynn, Y. Xu, Asymptotic product-form steady-state for generalized Jackson networks in multi-scale heavy traffic. Preprint arXiv:2304.01499 (2023), https://arxiv.org/abs/2304.01499
15. A. Puhalskii, On large queue lengths in generalised Jackson networks. Markov Processes and Related Fields 31(3-4), 265-279 (2025). DOI 10.61102/1024-2953-mprf.2025.31.3-4.006, https://doi.org/10.61102/1024-2953-mprf.2025.31.3-4.006
16. A. Puhalskii, On tightness and exponential tightness in generalised Jackson networks. Preprint arXiv:2511.00873 (2025), https://arxiv.org/abs/2511.00873
17. A. Sankararaman, F. Baccelli, S. Foss, Interference queueing networks on grids. Annals of Applied Probability 29(5), 2929-2987 (2019). DOI 10.1214/19-AAP1470, https://doi.org/10.1214/19-AAP1470