Veranstaltungsnummer  
Thema Verteilte Algorithmen
Veranstalter Prof. Dr. Thomas Schwentick
Klassifikation Proseminar
Semester Sommersemester 2009
SWS 3
Kreditpunkte 4
Ort und Zeit  
Vorbesprechung Termin wird noch bekanntgegeben
Querverbindungen DAP 2, BSRvS
Voraussetzungen DAP 2

Es wird voraussichtlich Vorträge zu den folgenden Themen geben.Die Kapitelangaben beziehen sich ausnahmslos auf das Buch Distributed Algorithms von Nancy Lynch.

 

Nr Thema
Buch Vortragende(r) Kurzvortrag Langvortrag
1 Leader Election in synchronen Ringen 3.1-3.6 Abdulmalek AL-Nasheri - -
2 Algorithmen in synchronen Netzwerken 4.1-4.4 Hani Zabarah - -
3 Konsens in synchronen Netzwerken mit stoppenden Prozessoren 6.1-6.2 Dawid Kopetzki 5.5. 16.6.
4 Konsens in synchronen Netzwerken mit byzantinischen Fehlern 6.3 Nils Vortmeier 5.5. 16.6.
5 Wechselseitiger Ausschluss in asynchronen Netzwerken: Dijkstras Algorithmus 10.1-10.3 Markus Tervooren 5.5. 23.6.
6 Wechselseitiger Ausschluss in asynchronen Netzwerken: Petersons Algorithmus 10.4-10.5 Tobias Scheideler - -
7 Zugriff auf Ressourcen in asynchronen Netzwerken: Speisende Philosophen 11.1-11.3 Stefan Tschentscher 12.5. 30.6.
8 Konsens in asynchronen Netzwerken 12.1-12.2 Jann Schwenk - -
9 Leader Election in asynchronen Ringen 15.1 Dmitrij Scheftelowitsch 12.5. 13.7.
10 Leader Election in asynchronen Netzwerken 15.3,15.5 Dennis Bonnmann 12.5. 13.7.

Verteilte Algorithmen steuern Berechnungen, die auf mehrere Prozessoren verteilt sind. Im Gegensatz zu Parallelen Algorithmen wird dabei keine zentrale Steuerung der Berechnungen angenommen. Die Prozessoren können synchron oder asynchron arbeiten und über ein Netzwerk oder einen gemeinsamen Speicherbereich miteinander kommunizieren.

Typische algorithmische Probleme sind z.B.:

  • Erzielung eines Konsenses
  • Wechselseitiger Ausschluss beim Zugriff auf Ressourcen
  • Synchronisation

Algorithmen sollen möglichst robust gegen Ausfälle von Prozessoren, Speichern oder Verbindungen sein.

Das Proseminar basiert auf dem Buch von Nancy Lynch, Distributed Algorithms. Es ist immer noch die Referenz in diesem Gebiet, auch wenn es schon vor über zehn Jahren erschienen ist.

Neben dem rein fachlichen Inhalt umfasst das Proseminar eine Einführung in Präsentationstechniken im Umfang von 1 SWS und ist insofern für Bachelor-Studierende geeignet. Diplom-Studierende sind auch willkommen, ihre Bereitschaft zur aktiven Teilnahme am Präsentations-Anteil der Veranstaltung vorausgesetzt.

Der grobe Ablauf wird wie folgt sein:

  • Im Januar 2009 findet eine Vorbesprechung mit Themenvergabe statt
  • Zu Beginn des Sommersemesters erfolgt eine Einführung in Präsentationstechniken. Dieser Teil besteht aus Vorlesung und praktischer Übung.
  • Etwa vier Wochen später wird es zwei bis drei Kompaktseminare mit Kurzvorträgen der Teilnehmer und ausführlichem Feedback geben.
  • In der zweiten Semesterhälfte finden dann die Hauptvorträge statt, jeweils zwei zu 60 Minuten (plus ca. 15 Minuten Feedback) je Sitzung
  • Im Anschluss daran sind (bis Ende September) die Ausarbeitungen zu erstellen
  • Vor dem Kurzvortrag und vor dem Hauptvortrag findet jeweils eine ca. 1-stündige individuelle Besprechung statt