Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies

We consider the problem of balancing load items (tokens) on networks. Starting with an arbitrary load distribution, we allow in each round nodes to exchange tokens with their neighbors. The goal is to achieve a distribution where all nodes have nearly the same number of tokens.

For the continuous case where tokens are arbitrarily divisible, most load balancing schemes correspond to Markov chains whose convergence is rather well-understood in terms of their spectral gap. However, since for many applications load items cannot be divided arbitrarily, we focus on the discrete case where the load is composed of indivisible tokens. Unfortunately, this discretization entails a non-linear behavior due to its rounding errors, which makes the analysis much harder than in the continuous case. Therefore, it has been a major open problem to understand the limitations of discrete load balancing and its relation to the continuous case.

We investigate several randomized protocols for different communication models in the discrete case. Our results demonstrate that there is almost no deviation between the discrete and continuous case. For instance, for any regular network in the matching-based model, all nodes have the same load up to a constant additive error in (asymptotically) the same number of rounds required in the continuous case. This generalizes and tightens the previous best result, which only holds for expander graphs and whose number of rounds is sub-optimal (STOC'09).

This is joint work with He Sun.