Title: Derandomized Load Balancing using Random Walks
Abstract: Load balancing resources with algorithms that have low communication complexity, low computation complexity and low memory utilization is the holy grail for many large-scale and distributed systems, such as distributed hash-tables and large-scale cloud computing systems. A well-known scheme in the area is the power-of-d choices scheme, wherein $d$ resource elements from a total of $n$ are sampled independently and uniformly at random, and an assignment is made to the least loaded resource. In the standard ball-in-bins experiment, that models the distributed hash-tables problem, it was shown by Azar et al. that this scheme yields a maximum load of $\log\log n/\log d+O(1)$ with high probability. Similar performance is obtained for the dynamic version of the problem by Vvedenskaya et al. and Mitzenmacher, which models assignment in large-scale multi-server systems.
Subsequent work analyzed the model when at each time, the $d$ resources are sampled through some correlated or non-uniform way. However, the case when the sampling for different resources are correlated has rarely been investigated. In this work we present analysis of a new scheme for both the allocation problems. We assume that there is an underlying $k$-regular graph $G$ connecting the resources. Then the new scheme is a variant of \emph{power-of-$d$ choices}, where the sampling of the $d$ resources at each time is based on the locations of $d$ independently moving non-backtracking random walkers on the graph $G$.
For the balls-in-bins problem, we show that under some conditions for the underlying graph that can be summarized as the graph being a high girth expander, the scheme can perform as well as \emph{power-of-$d$}, so that the maximum load is bounded by $\frac{\log\log n}{\log d}+O(1)$ with high probability. We further characterize the conditions of the graph in which the maximum load is bounded by $\Theta(\log \log n)$. Our results resolve Alon et al.'s open question in the balls-in-bins setting, and thus the random walk based assignment can be seen as a \emph{derandomization} of \emph{power-of-$d$ choices}.
For the multi-server systems setting, with similar assumptions on the graph as above, we show that under the random-walk based sampling scheme, as $n$ increases without bound, the dynamics of the queuing system converges to the same deterministic ordinary differential equation (ODE) system that is the mean-field limit for the power-of-$d$ choices scheme. We also show that the system is stable under the proposed scheme for each $n$, and the stationary distribution of the system converges to the fixed point of the ODE system. The proof of each step involves several methodological challenges as the processes being studied are non-Markovian.
