Short Bio:

Thomas Sauerwald received his PhD from the University of Paderborn, Germany in 2008. After that, he was a Postdoctoral Fellow at the International Computer Science in Berkeley, USA and a PIMS-Postdoctoral Fellow at the Simon Fraser University in Burnaby, Canada. Since 2010, he is holding a researcher position at the Max-Planck Institute for Informatics in Saarbruecken, Germany. His main research interests are the design and analysis of randomized algorithms. Topics he has worked on include Rumor Spreading, Load Balancing and Random Walks on Graphs.

Abstract:

Load Balancing is an important requisite for the efficient utilisation of shared resources. Here, we consider the problem of balancing discrete load items (tokens) on networks. In our model, in each time-step certain nodes are paired and they are allowed to average their load as close as possible. Most of the previous algorithms assumed that the excess token (if any) is kept by the node with the larger load. In this talk, we consider an algorithm that allocates the excess token to one of the two nodes randomly. We prove that this algorithm achieves an almost perfectly balanced load distribution.