Randomisierte Algorithmen

Themen

Book Chapters

1. 22.5.2019: N. Nisan, T. Roughgarden: Algorithmic Game Theory. Chapter 18: T. Roughgarden: Routing Games. 2007.
2. 8.5.2019: N. Nisan, T. Roughgarden: Algorithmic Game Theory. Chapter 20: B. Vöcking: Selfish Load Balancing. 2007.
3. 15.5.2019: F. Meyer auf der Heide: Kommunikation in Parallelen Rechenmodellen. Kapitel 6: Oblivious Routing. link
4. 29.5.2019: M. Mitzenmacher, E. Upfal: Probability and Computing, 2nd Edition. Chapter 5: Balls, Bins, and Random Graphs. 2017.
5. 5.6.2019: M. Mitzenmacher, E. Upfal: Probability and Computing, 2nd Edition. Chapter 17: Balanced Allocations and Cuckoo Hashing. 2017.

Papers

1. R. Karp, C. Schindelhauer, S. Shenker, B. Vocking: Randomized Rumor Spreading. FOCS 2000.
2. B. Doerr, L. A. Goldberg, L. Minder, T. Sauerwald, C. Scheideler: Stabilizing consensus with the power of two choices. SPAA 2011.
3. M. Raab, A. Steger: "Balls into Bins" - A Simple and Tight Analysis. RANDOM 1998.
4. J. Augustine, W. K. Moses Jr., A. Redlich, E. Upfal: Balanced Allocation: Patience is not a Virtue. SODA 2016.
5. D. Angluin, J. Aspnes, D. Eisenstat: A simple population protocol for fast robust approximate majority. Distributed Computing 21(2), 2008.

Übungsaufgaben

Sheet 1

Sheet 2

Lehrende

Petra Berenbrink

Dominik Kaaser

Inhalte

Randomisierte Algorithmen und verteilte Kommunikationsprotokolle im Kontext paralleler und verteilter Systeme, z.B.

• Informationsverteilung und epidemische Prozesse,
• Abstimmung und Mehrheitsentscheidungen
• Lastbalancierung
• Synchronisation Autonomer Agenten
   

Lernziel

Die Studierenden lernen fortschrittliche Techniken aus dem Bereich der randomisierten Algorithmen und stochastischen Prozessen sowie deren Anwendung im Kontext von parallelen und verteilten Systemen. Zusätzlich wird auf aktuelle internationale Forschungsergebnisse eingegangen. 

Literatur

• Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan
• Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal
• Concentration of Measure for the Analysis of Randomized Algorithms by Devdatt P. Dubhashi and Alessandro Panconesi