max planck institut
informatik
informatik
Max-Planck-Institut für
Informatik
Department 1: Algorithms and Complexity
Campus E1 4,
Room 319
66123 Saarbrücken
Germany
Email: sauerwal@mpi-inf.mpg.de
Phone: +49 681 9325 1130Fax: +49 681 9325 1099
Load Balancing The problem of load balancing on large networks is to find distributed algorithms that balance the load across the units of the network efficiently. Our work focuses on two popular communication models, the diffusion and the matching model. For both models, we analyze several iterative protocols that employ the idea of randomized rounding. We show that these protocols almost achieve the same discrepancy within the same number of rounds as their counterparts for the case of divisible load.
- Tight Bounds For Randomized Load Balancing on Arbitrary Network Topologies (with He Sun)
Available on Arxiv, 2012.- Quasirandom Load Balancing (with Tobias Friedrich and Martin Gairing)
SIAM Journal on Computing, to appear, 2012. Preliminary version appeared in SODA 2010, pages 1620-1629.- Distributed Selfish Load Balancing on Networks (with Petra Berenbrink and Martin Hoefer)
In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011, pages 1487-1497.- Smoothed Analysis of Balancing Networks (with Tobias Friedrich and Dan Vilenchik)
Random Structures & Algorithms, 39(1):115-138, 2011. Preliminary version appeared in ICALP 2009, pages 472-483.- The Impact of Randomization in Smoothing Networks (with Marios Mavronicolas)
Distributed Computing, 22(5-6), pages 381-411, 2010. Preliminary version appeared in PODC 2008, pages 345-354.- Near-Perfect Load Balancing by Randomized Rounding (with Tobias Friedrich)
In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), 2009, pages 121-130.
Random Walks The cover time of random walks is an ubiquitous parameter of graphs, which has many interesting relations to electrical networks, spectral graph theory, probability theory, complexity theory etc. We study different ways to speed up random walks with the aim of decreasing their cover time. For instance, we examine random walks that are able to explore their neighborhood in each step or analyze the cover time of parallel random walks.
- Expansion and the Cover Time of Parallel Random Walks
In Proceedings of the 29th ACM Symposium on Principles of Distributed Computing (PODC), 2010, pages 315-324.- Speeding Up Random Walks with Neighborhood Exploration (with Petra Berenbrink, Colin Cooper, Robert Elsässer, Tomasz Radzik)
In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010, pages 1422-1435.- Tight Bounds for the Cover Time of Multiple Random Walks (with Robert Elsässer)
Theoretical Computer Science, 412(24): 2623--2641, 2011. Preliminary version appeared in ICALP 2009, pages 415-426.- Cover Time and Broadcast Time (with Robert Elsässer)
In Proceedings of the 22nd International Symposium on Theoretical Aspects of Computer Science (STACS), 2009, pages 373-384.
Rumor Spreading Randomized rumor spreading are simple epidemic protocols that spread one message (rumor) from one node to all other nodes. This is done by allowing nodes to exchange any rumor with a randomly chosen neighbor in each round. The main question is to determine the number of required rounds to spread the rumor to all nodes on different networks. Our research includes: (1) analyzing the rumor spreading time on different network models, e.g., social networks; (2) studying the relation to graph parameters such as vertex- or edge expansion; (3) understanding the randomness requirement of rumor spreading.
- Rumor Spreading and Vertex Expansion (with George Giakkoupis)
In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012, pages 1623-1641.- Ultra-Fast Rumor Spreading in Social Networks (with Nikolas Fountoulakis and Konstantinos Panagiotou)
In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012, pages 1642-1661.- Low Randomness Rumor Spreading via Hashing (with George Giakkoupis, He Sun and Philipp Woelfel)
To appear in Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS), 2012.- On Mixing and Edge Expansion Properties in Randomized Broadcasting
Algorithmica, 56(1):51-88, 2010. Preliminary version appeared in ISAAC 2007, pages 196-207.- Quasirandom Rumor Spreading (with Benjamin Doerr and Tobias Friedrich)
In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008, pages 773-781.