Algorithmen für verteilte Systeme

LV-Leitung: Sebastian Forster
Semesterstunden: 2VO + 1PS
ECTS: 2 + 2
Curriculum: Bachelor Informatik
Voraussetzungen: Algorithmen und Datenstrukturen
Diskrete Mathematik für Informatik
Statistik für Informatik (empfohlen)

Materialien

Achtung: Die verlinkten Videos entsprechen teilweise dem Stoffumfang der Vorjahre.

Slides: Die gesammelten Slides stehen auch in folgenden Paketen zur Verfügung:

Mitschriften: Die gesammelten Mitschriften stehen in folgenden Paketen zur Verfügung

Die Slides und die Mitschriften stehen unter einer Creative Commons Namensnennung 4.0 International Lizenz und dürfen von interessierten Lehrenden verwendet und verändert werden.

Ablauf Proseminar

Im Proseminar werden Übungsaufgaben zum Stoff der Vorlesung besprochen. Grundlage der Bewertung für das Proseminar sind drei Aufgabenblätter (mit jeweils drei Aufgaben), die zu festgesetzten Terminen schriftlich auszuarbeiten sind und mit LaTeX gesetzt als PDF-Dateien in Blackboard abzugeben sind. Diese Aufgabenblätter sind hier abrufbar:

Darüberhinaus werden weitere Übungsaufgaben besprochen, die zum Teil im Voraus vorzubereiten sind und zum Teil ad hoc während der Präsenzzeit im Proseminar gelöst werden. Diese Übungsblätter sind hier abrufbar: Das Proseminar ist eine prüfungsimmanente Lehrveranstaltung, in der eine Anwesenheit von 75% gefordert wird.

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.