Load balancing with sparse dynamic random graphs

arXiv2305.13054MaRDI QIDQ6437495FDOQ6437495

Authors: Diego Goldsztajn, Sem Borst, Johan S. H. van Leeuwaarden 

Publication date: 22 May 2023

Abstract: Consider a system of $n$ single-server queues where tasks arrive at each server in a distributed fashion. A graph is used to locally balance the load by dispatching every incoming task to one of the shortest queues in the neighborhood where the task appears. In order to globally balance the load, the neighborship relations are constantly renewed by resampling the graph at rate $m{u}_n$ from some fixed random graph law. We derive the fluid limit of the occupancy process as $noinfty$ and $m{u}_{n}oinfty$ when the resampling procedure is symmetric with respect to the servers. The maximum degree of the graph may remain bounded as $n$ grows and the total number of arrivals between consecutive resampling times may approach infinity. The fluid limit only depends on the random graph laws through their limiting degree distribution and can be interpreted as a generalized power-of-$(d+1)$ scheme where $d$ is random and has the limiting degree distribution. We use the fluid limit to obtain valuable insights into the performance impact and optimal design of sparse dynamic graphs with a bounded average degree. In particular, we establish a phase transition in performance when the probability that a server is isolated switches from zero to positive, and we show that performance improves as the degree distribution becomes more concentrated.

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Functional limit theorems; invariance principles (60F17)

This page was built for publication: Load balancing with sparse dynamic random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6437495)