Stability of JSQ in queues with general server-job class compatibilities

Richard James Randon Cruise, Matthieu Jonckheere, Vsevolod Shneer

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)
24 Downloads (Pure)


We consider Poisson streams of exponentially distributed jobs arriving at each edge of a hypergraph of queues. Upon arrival, an incoming job is routed to the shortest queue among the corresponding vertices. This generalizes many known models such as power-of-d load balancing and JSQ (join the shortest queue) on generic graphs. We prove that stability in this model is achieved if and only if there exists a stable static routing policy. This stability condition is equivalent to that of the JSW (join the shortest workload) policy. We show that some graph topologies lead to a loss of capacity, implying more restrictive stability conditions than in, for example, complete graphs.
Original languageEnglish
Pages (from-to)271-279
Number of pages9
JournalQueueing Systems
Issue number3-4
Early online date3 Jun 2020
Publication statusPublished - Aug 2020


  • Hypergraph
  • JSQ load balancing
  • Stability

ASJC Scopus subject areas

  • Statistics and Probability
  • Computer Science Applications
  • Management Science and Operations Research
  • Computational Theory and Mathematics


Dive into the research topics of 'Stability of JSQ in queues with general server-job class compatibilities'. Together they form a unique fingerprint.

Cite this