The join-the-shortest-queue (JSQ) networks of Dai–Hasenbein–Kim generalize Jackson queueing networks by letting each arriving or rerouted customer join the shortest queue among an allowed set of stations, with arbitrary tie-breaking and general independent, identically distributed (i.i.d.) interarrival and service times. For two stations, and for any number of stations under a homogeneity assumption on the feedback probabilities, positive Harris recurrence — stability in the sense that the network state process possesses a stationary probability distribution and returns to it from every initial state — is completely characterized by first-order mean parameters. Without that assumption, the paper's counterexamples show that stability can hinge on tie-breaking probabilities and on the full service-time distribution, so no criterion in terms of means alone exists. The open problem is to characterize positive Harris recurrence of general JSQ networks with J≥3J\ge 3 stations and arbitrary heterogeneous routing: to give necessary and sufficient conditions, and to identify which data beyond first-order means the stability boundary actually depends on.

Background

A queueing network is a system of service stations, each with a queue, through which customers arrive, receive service, and move between stations or leave the system. In a classical Jackson network, routing is probabilistic but fixed — every customer leaving station ii goes to station jj with a probability that does not depend on the state — and interarrival and service times are exponential. A generalized Jackson network keeps the fixed routing but allows i.i.d. interarrival and service times with general distributions. The standard notion of stability is positive Harris recurrence: the Markov process describing the network state (queue lengths and, for non-exponential primitives, residual interarrival and service times) possesses a stationary probability distribution and returns to it from every initial state; this is the natural extension of positive recurrence from countable-state to general-state Markov processes. A classical fact is that stability of a generalized Jackson network is decided by first-order data alone: the network is stable if and only if the traffic intensity — the long-run rate of arriving work divided by service capacity — is strictly below one at every station, regardless of any other feature of the distributions.

Join-the-shortest-queue (JSQ) routing adds customer choice. Dai, Hasenbein and Kim (2007) formalized the JSQ network as follows. There are JJ single-server stations. For each nonempty subset CC of the station set J={1,…,J}\mathcal{J}=\{1,\dots,J\} there is a type-CC exogenous arrival stream of rate λC\lambda_C; a type-CC customer joins the shortest queue among the stations in CC, and when the queues of a set BB are tied for shortest, the customer joins queue j∈Bj\in B with probability γB,j\gamma_{B,j} (the tie-breaking rule). After completing service at station ii, a customer either leaves the network with probability 1−pi∗1-p_i^*, or becomes a type-CC customer with probability piCp_{iC} and is routed again by the shortest-queue rule; the piCp_{iC} are called feedback probabilities. Stations are non-idling (a server works whenever a customer is waiting) and serve first-in-first-out; interarrival and service times are i.i.d. with rates λC\lambda_C and μi\mu_i (that is, mean interarrival times 1/λC1/\lambda_C and mean service times 1/μi1/\mu_i). JSQ is the canonical greedy load-balancing discipline, and the feedback mechanism models multi-tier systems in which jobs return to a dispatcher between processing stages.

Dai–Hasenbein–Kim established three things. First, for J=2J=2 stations the network is positive Harris recurrent if and only if three explicit linear inequalities in the first-order parameters (λC,μi,piC)(\lambda_C,\mu_i,p_{iC}) hold; mean data suffice, and in the symmetric Poisson-exponential case with fair tie-breaking the conditions agree with Kurkova's (2001) earlier Lyapunov-function characterization of a two-server load-balanced network. Second, for J≥3J\ge 3 the mean-parameter paradigm fails: they constructed two three-station examples, with Poisson arrivals and exponential or hyperexponential services, in which all first-order parameters are fixed yet stability depends on the tie-breaking probabilities, or on the service-time distributions. In these examples the routing is heterogeneous — station 1's output is routed to station 3 while station 2's customers leave — which is precisely why the homogeneity assumption below does not apply: the effective load of station 3 is λ3+d1\lambda_3+d_1, where d1d_1 is the stationary departure rate of station 1, a quantity sensitive to tie-breaking and to distributional detail. Third, under Assumption 1 — the feedback probabilities are homogeneous, piC=pCp_{iC}=p_C independent of the station ii being left — mean parameters again characterize stability: writing ΛC=∑∅≠B⊆CλB\Lambda_C=\sum_{\emptyset\ne B\subseteq C}\lambda_B for the total exogenous rate of types whose choice set lies inside CC, PC=∑∅≠B⊆CpBP_C=\sum_{\emptyset\ne B\subseteq C}p_B, μC=∑i∈Cμi\mu_C=\sum_{i\in C}\mu_i, λ∗\lambda^* for the total exogenous arrival rate and p∗<1p^*<1 for the total feedback probability, the network is positive Harris recurrent if and only if

ΛC+λ∗1−p∗PC<μC\Lambda_C+\frac{\lambda^*}{1-p^*}P_C<\mu_C

for every nonempty C⊆JC\subseteq\mathcal{J}; and when the reversed strict inequality holds for some CC, the total queue length diverges to infinity almost surely. Their method extends fluid-model technology (the deterministic limiting dynamics obtained by space-time scaling of the stochastic network, whose stability implies stability of the network by Dai's 1995 theorem) with an augmented fluid model that can also certify non-positive recurrence, beyond the classical use of fluid models to prove only stability or transience.

The case without feedback — every customer leaves after one service — is well understood: Foss and Chernova (1998) analyzed a partially accessible multi-station queue with state-dependent routing under the FIFO discipline via fluid limits, and Bramson (2011) proved that subcritical JSQ networks without feedback are stable under every non-idling service discipline and general primitive distributions, with uniform bounds on stationary queue-length tails. Cruise–Jonckheere–Shneer (2020) studied JSQ on general server–class compatibility structures (a hypergraph of queues) with exponential primitives, giving a generic sufficient condition and exhibiting topologies whose stability region is strictly smaller than the naive load bound; Goldsztajn–Borst–van Leeuwaarden (2024) uncovered a related steady-state pathology (server saturation) in skewed compatibility networks. Adjacent results reinforce, in other models, the phenomenon discovered by Dai–Hasenbein–Kim: Moyal–Perry (2022) showed that for parallel server systems with routing errors the traffic-intensity condition no longer guarantees stability, and Gamarnik–Tsitsiklis–Zubeldia (2022) quantified the message and memory resources a dispatcher needs for guaranteed stability in heterogeneous systems. None of these lines addresses JSQ networks with feedback and heterogeneous routing, which is the unresolved general case.

Problem Statement

Within the JSQ network model of Dai–Hasenbein–Kim (J≥3J\ge 3 single-server stations indexed by J={1,…,J}\mathcal{J}=\{1,\dots,J\}; for each nonempty C⊆JC\subseteq\mathcal{J}, a type-CC exogenous arrival stream of rate λC\lambda_C whose customers join the shortest queue among the stations of CC, a tie among the stations of a set BB being broken by choosing queue j∈Bj\in B with probability γB,j\gamma_{B,j}; after completing service at station ii, a customer becomes a type-CC customer with probability piCp_{iC} and is routed again by the shortest-queue rule, or leaves the network with the remaining probability; independent, identically distributed (i.i.d.) interarrival and service times with rates λC\lambda_C and μi\mu_i; first-in-first-out (FIFO), non-idling service, so a server works whenever a customer is waiting; stability meaning positive Harris recurrence of the network Markov process, i.e. the existence of a stationary probability distribution to which the process returns from every initial state), settle the stability characterization that the source paper's counterexamples leave open. The common objective is an exact, usable description of the stability region when the routing is arbitrary — no homogeneity imposed on the feedback probabilities:

  1. (Criterion) Give necessary and sufficient conditions for positive Harris recurrence of JSQ networks with arbitrary heterogeneous feedback, stated in terms of explicitly specified network data, together with a matching instability assertion — conditions under which the process is not positive recurrent (ideally, the total queue length diverges almost surely).
  2. (Minimal data) Determine which data beyond the first-order means (λC,μi,piC)(\lambda_C,\mu_i,p_{iC}) the stability boundary genuinely depends on: identify a set of parameters that suffices to decide stability for a given routing structure, and prove insufficiency results — pairs of networks agreeing on any proposed smaller data set yet differing in stability — of which the source paper's two three-station counterexamples are the prototypes: one in which positive Harris recurrence depends on the tie-breaking probabilities, and one in which it depends on the service-time distributions, at fixed first-order means.

The original generality must be retained: arbitrary J≥3J\ge 3, arbitrary routing and tie-breaking, general primitive distributions. In particular, answers restricted to homogeneous feedback, or to networks without feedback, restate what is already known.

References

  1. J. G. Dai, John J. Hasenbein, Bara Kim, 'Stability of join-the-shortest-queue networks', Queueing Systems 57(4):129-145, 2007. DOI: 10.1007/s11134-007-9046-5, https://doi.org/10.1007/s11134-007-9046-5
  2. J. G. Dai, John J. Hasenbein, Bara Kim, 'Stability of Join-the-Shortest-Queue networks: Analysis by Fluid Limits', in R. J. Boucherie and N. M. van Dijk (eds.), Queueing Networks: A Fundamental Approach, International Series in Operations Research & Management Science 154, Springer, New York, pp. 461-487, 2011. DOI: 10.1007/978-1-4419-6472-4_10, https://doi.org/10.1007/978-1-4419-6472-4_10
  3. J. G. Dai, 'On Positive Harris Recurrence of Multiclass Queueing Networks: A Unified Approach Via Fluid Limit Models', Annals of Applied Probability 5(1):49-77, 1995. DOI: 10.1214/aoap/1177004828, https://doi.org/10.1214/aoap/1177004828
  4. Maury Bramson, 'Stability of Join the Shortest Queue Networks', Annals of Applied Probability 21(4):1568-1625, 2011. DOI: 10.1214/10-AAP726, arXiv:1010.1749, https://arxiv.org/abs/1010.1749
  5. Serguei Foss, Natalia Chernova, 'On the stability of a partially accessible multi-station queue with state-dependent routing', Queueing Systems 29(1):55-73, 1998. DOI: 10.1023/A:1019175812444, https://doi.org/10.1023/A:1019175812444
  6. I. A. Kurkova, 'A Load-Balanced Network with Two Servers', Queueing Systems 37(4):379-389, 2001. DOI: 10.1023/A:1010841517511, https://doi.org/10.1023/A:1010841517511
  7. James Cruise, Matthieu Jonckheere, Seva Shneer, 'Stability of JSQ in queues with general server-job class compatibilities', Queueing Systems 95(3-4):271-279, 2020. DOI: 10.1007/s11134-020-09656-w, arXiv:2001.09921, https://arxiv.org/abs/2001.09921
  8. David Gamarnik, John N. Tsitsiklis, Martin Zubeldia, 'Stability, Memory, and Messaging Trade-Offs in Heterogeneous Service Systems', Mathematics of Operations Research 47(3):1862-1874, 2022. DOI: 10.1287/moor.2021.1191, https://doi.org/10.1287/moor.2021.1191
  9. Diego Goldsztajn, Sem C. Borst, Johan S. H. van Leeuwaarden, 'Server Saturation in Skewed Networks', Proceedings of the ACM on Measurement and Analysis of Computing Systems 8(2):1-37, 2024. DOI: 10.1145/3656018, arXiv:2404.06485, https://arxiv.org/abs/2404.06485
  10. Pascal Moyal, Ohad Perry, 'Stability of Parallel Server Systems', Operations Research 70(4):2456-2476, 2022. DOI: 10.1287/opre.2021.2125, https://doi.org/10.1287/opre.2021.2125