Fluid limits for interacting queues in sparse dynamic graphs

doi:10.1016/j.spa.2025.104794

Fluid limits for interacting queues in sparse dynamic graphs

2025-10-01

0

PRE

AI

Johan S. H. van Leeuwaarden

DOI：10.1016/j.spa.2025.104794

Original

Original request for help

Save

Abstract

En 中文

Consider a network of n single-server queues where tasks arrive independently at each server at rate lambda n. The servers are connected by a graph that is resampled at rate mu n in a way that is symmetric with respect to the servers, and each task is dispatched to the shortest queue in the graph neighborhood where it appears. We aim to gain insight in the impact of the dynamic network structure on the load balancing dynamics in terms of the occupancy process which describes the empirical distribution of the number of tasks across the servers. This process evolves on the underlying dynamic graph, and its dynamics depend on the number of tasks at each individual server and the neighborhood structure of the graph. We establish that this dependency disappears in the limit as n - infinity when lambda n/n - lambda and mu n - infinity, and prove that the limit of the occupancy process is given by a system of differential equations that depends solely on lambda and the limiting degree distribution of the graph. We further show that the stationary distribution of the occupancy process converges to an equilibrium of the differential equations, and derive properties of this equilibrium that reflect the impact of the degree distribution. Our focus is on truly sparse graphs where the maximum degree is uniformly bounded across n, which is natural in load balancing systems.

Keywords:

Interacting queues

Load balancing

Dynamic random graphs

Fluid limits

Fluid limits for interacting queues in sparse dynamic graphs

Abstract

Journal

Organization