[Christian-Albrechts-Universität] [Institut fuer Informatik]

Verteilte Algorithmen
Vorlesung im Wintersemester 2007/08


 
Termin: Mo. und Mi. 8:15 - 9:45
Beginn: Mo., 22.10.2007
Ort: LMS2 - R.Ü1
Dozent: Willem-Paul de Roever
Übung: Di. 12:15 - 13:45 (Wilhelm-Seelig-Platz 3, Raum 1), erster Termin: 30.10.2007
  Do. 12:15 - 13:45 (Wilhelm-Seelig-Platz 3, Raum 3), erster Termin: 1.11.2007

Für die offiziellen studientechnischen Daten sei auf das Univis-System der Universität verwiesen.

Bei Fragen zur Übung, E-Mail an Heiko Schmidt (oder Tim Fenten oder Christian Motika).

Abstract:

Verteilte Algorithmen sind eines der am häufigsten vorkommenden Bestandteile der modernen Informatik. Jeder Informatiker soll sich damit auskennen und mit der spezifischen Problematik dieser Algorithmen vertraut sein. Ihrer Komplexität wegen sind die fehlerfreie Entwicklung und Analyse solcher Algorithmen zeitaufwendig und in relativ kurzer Zeit nur möglich, wenn die Entstehung, d.h. ihre Entwicklungsgeschichte, bekannt ist.

Die Vorlesung hat zum Ziel, die Entwicklungsgeschichte zu erläutern und die Funktionsweise der wichtigsten verteilten Algorithmen zu erklären.

Stichworte: Algorithmen für Leader Election, Distributed Search, Spanning Tree, and Distributed Consensus sowie für Resource Allocation, Atomic Objects, Asynchronous Networks und Synchronizers.

1  Organisatorisches

Die Vorlesung wird durch (i.d.R) wöchentliche Übungen begleitet, die in 2er-Gruppen bearbeitet werden. Zwei etwas aufwendigere Übungen (Mitt- und Endsemestertest), die auch bei den Endbewertungen stärker gewichtet werden, müssen alleine gelöst werden.

Ausgabe der Zettel ist in der Regel Mittwoch in der Vorlesung, Abgabe in der Regel in der darauffolgenden Woche, Freitag 12:00 Uhr im Schrein. Besprechung und Rückgabe dann in der folgenden Übung.

Abgaben per E-Mail sollten an hsc (Heiko), tif (Tim) UND cmot (Christian) geschickt werden, "VA" und "Abgabe" im Betreff haben, im PDF- oder Nur-Text-Format vorliegen und zur Deadline (meist Fr. 12:00) bei uns im Postfach sein.

Mittsemestertest: Ausgabe voraussichtlich am 3.12.2007

Endsemestertest: Ausgabe voraussichtlich am 28.1.2008



2  Übungsserien + Unterlagen

Präsentationsfolien vom 24.10.2007 zu Kapitel 3, Leader Election in a Synchronous Ring

Übung 1 (Ausgabetermin: 24.10.2007, Abgabe: 02.11.2007)

Übung 2 (Ausgabetermin: 31.10.2007, Abgabe: 09.11.2007)

Übung 3 (Ausgabetermin: 07.11.2007, Abgabe: 16.11.2007)
Schöne Lösung zu Übung 3, Aufgabe 2 (SynchGHS), freundlicherweise zur Verfügung gestellt von Tsvetelin und Yvan

Übung 4 (Ausgabetermin: 14.11.2007, Abgabe: 23.11.2007)

Übung 5 (Ausgabetermin: 21.11.2007, Abgabe: 30.11.2007)

Übung 6 (Ausgabetermin: 28.11.2007, Abgabe: 07.12.2007)

Mittsemestertest (Ausgabetermin: 03.12.2007, Abgabe: 17.12.2007)
Zusatzhinweise zu Aufgabe 3 des Mittsemestertests (Authenticated Byzantine Model) [Update am 06.12.2007]

Übung 8 (Ausgabetermin: 12.12.2007, Abgabe: 21.12.2007)

Übung 9 (Ausgabetermin: 19.12.2007, Abgabe: 11.01.2008)

Übung 10 (Ausgabetermin: 09.01.2008, Abgabe: 18.01.2008, [Deadline extension] Aufgabe 3 darf am Montag, 21.01.2008 in der Vorlesung oder per Mail bis 12:00 abgegeben werden)

Übung 11 (Ausgabetermin: 16.01.2008, Abgabe: [Deadline extension] Montag, 28.01.2008 in der Vorlesung oder per Mail bis 12:00)

Endsemestertest (Ausgabetermin: 28.01.2008, Abgabe: 11.02.2008)

3  Links

Folgendes enthält einige (nicht sehr geordnete) Sammlung von Verweisen, die für die Vorlesung nützlich sein können oder auch nicht.
This document was translated from LATEX by HEVEA.