Tight Bounds for Parallel Randomized Load Balancing

Date: Thursday, July 07, 2011
Speaker: Christoph Lenzen
Venue: IST Austria
Notes:

Mondi 2

In the distributed balls-into-bins problem, one strives for distributing n balls into n bins as evenly as possible. In each communication round, balls may contact some bins, bins may respond, and balls may commit to a bin. Goals are to minimize the individual and overall message complexities, the maximum bin load, and the number of communication rounds.

Classical algorithms are non-adaptive, that is, each ball decides on the bins it will contact before communication commences. We will show how dropping this requirement drastically improves the trade-offs between the above optimization criterions. Concretely, we present a stunningly simple algorithm that guarantees a maximum bin load of two within log* n + O(1) rounds using O(n) total messages. This is provably optimal for a natural class of algorithms, while dropping any of the requirements of this class enables to achieve a constant running time. To round of the presentation, we discuss how our techniques can be applied to a basic communication task in a clique.

Bio:Christoph Lenzen received his diploma in Mathematics from the university of Bonn in 2007. He continued his studies at ETH Zurich in Roger Wattenhofer’s group and received his Ph.D. degree in 2011. Presently he is a postdoc at the Hebrew University of Jerusalem with Danny Dolev. His main area of interest are distributed algorithms, for instance for graph problems such as dominating or independent sets, randomized load balancing, and clock synchronization.

Posted in RiSE Seminar