Algorithmen für verteilte Systeme
Diese Lehrveranstaltungen VO und PS „Algorithmen für verteilte Systeme“ wird im Sommersemester 2021 nicht angeboten. Studierende, die auf diese Lehrveranstaltungen für den Abschluss ihres Studiums im Sommersemester 2021 angewiesen sind, haben die Möglichkeit vorgegebene Ersatzlehrveranstaltungen im gleichen ECTS-Umfang zu absolvieren. Die Liste der Ersatzlehrveranstaltungen wird von Helge Hagenauer zusammengestellt.
LV-Leitung: | Sebastian Forster |
Semesterstunden: | 2VO + 1PS |
ECTS: | 2 + 2 |
Curriculum: | Bachelor Informatik/Angewandte Informatik |
Master Data Science | |
Voraussetzungen: | Algorithmen und Datenstrukturen |
Diskrete Mathematik für Informatik | |
Statistik für Informatik (empfohlen) |
Zeitplan und Materialien
-
Vorbesprechung
Slides Basiswissen Mathematik -
Leader Election I
Slides Video mkv Video mp4 Mitschrift (neu)
Literatur: [Lyn96, Kapitel 3] [AW04, Kapitel 3] -
Leader Election II
Slides Video mkv Video mp4 Video Mitschrift (neu)
Literatur: [Lyn96, Kapitel 3] [AW04, Kapitel 14] -
CONGEST Modell
Slides Video mkv Video mp4 Mitschrift (neu)
Literatur: [Pel00, Kapitel 3-4] -
Synchronisierung
Slides Video mkv Video mp4 Mitschrift
Literatur: [Pel00, Kapitel 6] -
Maximal Independent Set
Slides Video mkv Video mp4 Mitschrift (neu)
Literatur: [MRSZ11] -
Graph Spanners
Slides Video mkv Video mp4
Literatur: [BS07] -
Kürzeste Wege I
Slides Video mkv Video mp4 Mitschrift (neu)
Literatur: [Nan14] -
Kürzeste Wege II
Slides Video mkv Video mp4
Literatur: [FN18] -
Epidemische Informationsausbreitung I
Slides Video mkv Video mp4 Mitschrift
Literatur: [DK14] -
Epidemische Informationsausbreitung II
Slides Video mkv Video mp4 Mitschrift
Literatur: [KSSV00]
Achtung: Die verlinkten Mitschriften und Videos entsprechen teilweise Umständen dem Stoffumfang der Vorjahre. Die aktualisierten Mitschriften sind als „neu“ gekennzeichnet.
Alle Slides stehen unter einer Creative Commons Namensnennung 4.0 International Lizenz und dürfen von interessierten Lehrenden verwendet und verändert werden. Die gesammelten Slides stehen auch in folgenden Paketen zur Verfügung:
Mitschriften
Die LaTeX-Vorlage für die Mitschriften gibt es hier.
Prüfung
Der erste Termin für die schriftliche Vorlesungsprüfung findet online am 25.06.2020 von 16:00 bis 18:00 Uhr statt. Der zweite Termin für die schriftliche Vorlesungsprüfung findet online am 15.07.2020 von 14:00 bis 16:00 Uhr statt. Der dritte Termin für die schriftliche Vorlesungsprüfung findet am 23.09.2020 von 14:00 bis 16:00 Uhr statt statt. Achtung: Es ist kein weiterer Prüfungstermin für den Stoffumfang des Sommersemesters 2020 geplant.
Literatur
[AW04] Hagit Attiya, Jennifer Welch (2004) Distributed Computing: Fundamentals, Simulations, and Advanced Topics, Wiley.
[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 (1996) Distributed Algorithms, Morgan Kaufmann.
[MRSZ11] Yves Métivier, John Michael Robson, Nasser Saheb-Djahromi, Akka Zemmari. „An optimal bit complexity randomized distributed MIS algorithm“. Distributed Computing 23(5–6): 331–340 (2011)
[Pel00] David Peleg (2000) Distributed Computing: A Locality-Sensitive Approach, SIAM.