Fluid limits for interacting queues in sparse dynamic graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915544805933056 |
|---|---|
| author | Goldsztajn, Diego Borst, Sem C. van Leeuwaarden, Johan S. H. |
| author_facet | Goldsztajn, Diego Borst, Sem C. van Leeuwaarden, Johan S. H. |
| contents | Consider a network of $n$ single-server queues where tasks arrive independently at each server at rate $λ_n$. The servers are connected by a graph that is resampled at rate $μ_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 \to \infty$ when $λ_n / n \to λ$ and $μ_n \to \infty$, and prove that the limit of the occupancy process is given by a system of differential equations that depends solely on $λ$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_13054 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Fluid limits for interacting queues in sparse dynamic graphs Goldsztajn, Diego Borst, Sem C. van Leeuwaarden, Johan S. H. Probability 60F17, 60K25, 60K35 (Primary) 68M20 (Secondary) Consider a network of $n$ single-server queues where tasks arrive independently at each server at rate $λ_n$. The servers are connected by a graph that is resampled at rate $μ_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 \to \infty$ when $λ_n / n \to λ$ and $μ_n \to \infty$, and prove that the limit of the occupancy process is given by a system of differential equations that depends solely on $λ$ 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. |
| title | Fluid limits for interacting queues in sparse dynamic graphs |
| topic | Probability 60F17, 60K25, 60K35 (Primary) 68M20 (Secondary) |
| url | https://arxiv.org/abs/2305.13054 |