Title : Load Balancing by Randomized Rounding
Speaker :  Thomas Sauerwald (University of Cambridge)


Abstract : 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
obtain a distribution where all nodes have 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
fairly well-understood in terms of their spectral gap.

However, in many applications load items cannot be divided arbitrarily
often and we need to deal with the discrete case where load is composed
of indivisible tokens. In this talk we investigate a natural protocol
based on randomized rounding and demonstrate that there is almost no
difference between the discrete and continuous case. Specifically, we
show that for any regular network, all nodes have the same number of
tokens up to an additive constant in the same number of rounds as in the
continuous case.