Stability of dynamic load balancing on a hyper-graph
James R. Cruise, Matthieu Jonckheere, Seva Shneer · arXiv (Cornell University) · 2020
We consider Poisson streams of exponentially distributed jobs arriving at each edge of an hypergraph of queues. Upon arrival, an incoming job chooses the shortest queue among the corresponding vertices. This generalizes many known models such as power-of-d load balancing and join the shorstest queue on generic graphs. We give a generic stability condition for this model and prove positive recurrence and transience of the underlying Markov process. We show that some graph topologies lead to a loss of capacity, implying more restrictive stability conditions than in, e.g., complete graphs.