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

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.