Derandomized Load Balancing using Random Walks on Expander Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2019
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913619553288192 |
|---|---|
| author | Tang, Dengwang Subramanian, Vijay G. |
| author_facet | Tang, Dengwang Subramanian, Vijay G. |
| contents | In a computing center with a huge amount of machines, when a job arrives, a dispatcher need to decide which machine to route this job to based on limited information. A classical method, called the power-of-$d$ choices algorithm is to pick $d$ servers independently at random and dispatch the job to the least loaded server among the $d$ servers. In this paper, we analyze a low-randomness variant of this dispatching scheme, where $d$ queues are sampled through $d$ independent non-backtracking random walks on a $k$-regular graph $G$. Under certain assumptions of the graph $G$ we show that under this scheme, the dynamics of the queuing system converges to the same deterministic ordinary differential equation (ODE) for the power-of-$d$ choices scheme. We also show that the system is stable under the proposed scheme, and the stationary distribution of the system converges to the fixed point of the ODE. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1901_09094 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Derandomized Load Balancing using Random Walks on Expander Graphs Tang, Dengwang Subramanian, Vijay G. Probability Networking and Internet Architecture Performance Systems and Control In a computing center with a huge amount of machines, when a job arrives, a dispatcher need to decide which machine to route this job to based on limited information. A classical method, called the power-of-$d$ choices algorithm is to pick $d$ servers independently at random and dispatch the job to the least loaded server among the $d$ servers. In this paper, we analyze a low-randomness variant of this dispatching scheme, where $d$ queues are sampled through $d$ independent non-backtracking random walks on a $k$-regular graph $G$. Under certain assumptions of the graph $G$ we show that under this scheme, the dynamics of the queuing system converges to the same deterministic ordinary differential equation (ODE) for the power-of-$d$ choices scheme. We also show that the system is stable under the proposed scheme, and the stationary distribution of the system converges to the fixed point of the ODE. |
| title | Derandomized Load Balancing using Random Walks on Expander Graphs |
| topic | Probability Networking and Internet Architecture Performance Systems and Control |
| url | https://arxiv.org/abs/1901.09094 |