Algorithmen für verteilte Systeme

Vortragender: Sebastian Forster
Semesterstunden: 2VO + 1PS
ECTS: 2 + 2
Curriculum: Bachelor Informatik/Angewandte Informatik
Master Data Science
Termin VO: Mittwoch, 09:15-10:45, T.01
Termin PS: Montag, 16:00-18:00, T.02, 14-tägig
Vorbesprechung: Mittwoch, 06.03., 09:15, T.01
Voraussetzungen: Algorithmen und Datenstrukturen
Anmeldung: PLUS online: VO PS

Prüfung

Der erste Termin für die schriftliche Prüfung findet am 26.06.2019 von 09:00 bis 10:55 Uhr in HS T.01 statt.

Der zweite Termin für die schriftliche Prüfung findet am 26.09.2019 von 14:00 bis 15:55 Uhr in Raum T.04 statt.

Der dritte Termin für die schriftliche Prüfung findet am 25.10.2019 von 14:00 bis 15:55 Uhr in Raum T.06 statt.


Zeitplan und Materialien

Datum Thema Slides Video Mitschrift Literatur
06.03. Vorbesprechung Slides Video
06.03. Routing in Prozessornetzwerken Slides Video
13.03. Leader Election I Slides Video Mitschrift [Lyn96, Kapitel 3]
20.03. Leader Election II Slides Video Mitschrift [Lyn96, Kapitel 3]
27.03. CONGEST Modell Slides Video Mitschrift [Pel00, Kapitel 3-4]
03.04. Maximal Independent Set Slides (*) Mitschrift [MRSZ11]
10.04. Graph Spanners Slides Video [BS07]
08.05. Kürzeste Wege I Slides Video [Nan14]
15.05. Kürzeste Wege II Slides Video(**) [FN18]
22.05. Synchronisierung Slides Video Mitschrift [Pel00, Kapitel 6]
29.05. Epidemische Informationsausbreitung I Slides Video Mitschrift [DK14]
12.06. Epidemische Informationsausbreitung II Slides Video Mitschrift [KSSV00]
19.06. Q&A Session
26.06. Schriftliche Prüfung

(*) Aufgrund technischer Probleme konnte am 03.04. keine Aufzeichnung durchgeführt werden.

(**) Aufgrund technischer Probleme konnte am 15.05. die Aufzeichnung nur teilweise durchgeführt werden.


Literatur

[BS07] Surender Baswana, Sandeep Sen. "A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs". Random Structures and Algorithms 30(4): 532-563 (2007)
[DK14] Benjamin Doerr, Marvin Künnemann. "Tight Analysis of Randomized Rumor Spreading in Complete Graphs". In Proc. of the Workshop on Analytic Algorithmics and Combinatorics (ANALCO) 82-91 (2014)
[FN18] Sebastian Forster, Danupon Nanongkai. "A Faster Distributed Single-Source Shortest Paths Algorithm". In Proc. of the Symposium on Foundations of Computer Science (FOCS) 686-697 (2018)
[KSSV00] Richard M. Karp, Christian Schindelhauer, Scott Shenker, Berthold Vöcking. "Randomized Rumor Spreading". In Proc. of the Symposium on Foundations of Computer Science (FOCS) 565-574 (2000)
[Nan14] Danupon Nanongkai. "Distributed Approximation Algorithms for Weighted Shortest Paths". In Proc. of the Symposium on Theory of Computing (STOC) 565-573 (2014)
[Lyn96] Nancy A. Lynch: Distributed Algorithms. Morgan Kaufmann, 1996.
[MRSZ11] Yves Métivier, John Michael Robson, Nasser Saheb-Djahromi und Akka Zemmari. "An optimal bit complexity randomized distributed MIS algorithm". Distributed Computing 23(5-6): 331-340 (2011)
[Pel00] D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM, Philadelphia, PA, 2000.


Übungsaufgaben


Rechercheauftrag

Der Rechercheauftrag ist hier zu finden.


Mitschriften

Die LaTeX-Vorlage für die Mitschriften gibt es hier.


Gitlab

Die Folien und die Mitschriften werden in einem git-Repository auf dem internen Gitlab-Server verwaltet. Um einen Gitlab-Account zu erhalten, loggen Sie sich zunächst einmalig mit ihrem cosy-Account ein. Sie werden dann nach manueller Prüfung von der Technik freigeschaltet. Um Zugriff auf das Repository zu erhalten, senden Sie mir eine Email und ich füge Sie dann dem Projekt AVS hinzu.

Aufgabenpräsentation

Bitte im Laufe des Semesters in der Datei presentation.txt im Git-Repository eintragen, um die Lösung einer Aufgabe im Proseminar zu präsentieren.