Randomised Load Balancing Networks (12:10–12:55)

Thomas Sauerwald ( University of Cambridge )

We consider the problem of balancing load items on networks. Starting with an arbitrary initial load distribution, we allow in each iteration every node to exchange load with their neighbors. The goal is to obtain a distribution where all nodes have (approximately) the same load. For the continuous case where load is arbitrarily divisible, many load balancing protocols correspond to Markov chains whose convergence rate is well captured in terms of the spectral gap.

However, in many applications load cannot be divided arbitrarily often and we need to deal with the discrete case where load is composed of indivisible unit-size tokens. In this talk we will analyse protocols for the discrete case that employ deterministic or randomised rounding. Finally we will discuss new variants in which the rounding decisions are no longer independent and possibly even controlled by an adversary.