[Christian-Albrechts-Universität] [Technical Faculty]

Verteilte Algorithmen
Seminar im Sommersemester 2004

Vorbesprechung: Dienstag 13. April um 10:00 2004 im Diplomandenraum bei uns am Lehrstuhl (eine Zeitlang war hier der Freitag 9. April gestanden, aber das ist, wie man so sagt, ein Feiertag :-)
  Wer in der Vorlesungsfreien Zeit bereits ein Thema haben will, soll vorher vorbeikommen
Termin: Freitags, 10 ct
Beginn: n.V.
Ort: siehe Univis
Dozent: Willem-Paul de Roever und Mitarbeiter

Die vollständigen studientechnischen Daten sind über das Univis-System zu erfragen.

Bei Fragen zum Kurs, email an Harald Fecher oder Martin Steffen.



Die Bedeutung verteilter Algorithmen rührt von der Allgegenwart verteilter, vernetzter und nebenläufiger Systeme. Trotz der Vielfalt der Erscheinungsformen liegen verteilter Software eine Reihe fundamentaler immer wiederkehrender Prinzipien und Algorithmen zugrunde. Beispiele für typische Fragestellungen sind Informationsverbreitung und -sammlung in Netzen, Konsensfindung, Bestimmung eines ausgezeichneten Prozesses (``Leader Election''), Fehlerentdeckung und -behebung, Herstellung von Synchronizität, Bestimmung eines globalen, konsistenten Schnappschusses und ähnliches.

Die zugehörigen Algorithem sind oft elegant und kompakt. Dennoch ist ihre fehlerfreie Entwicklung und Analyse anspruchsvoll, da sich das nebenläufige Geschehen in beliebigen Netzen nur schwer intuitiv (und korrekt ...) durchschauen läßt. Die Kenntis der grundlegenden Prinzipien sowie wichtiger Algorithmen auf diesem Gebiet gehört demzufolge zum unverzichtbaren Handwerkszeug zur Entwicklung moderner, verteilter Systeme.

Aufbauend auf die Vorlesung im WS0304 werden im Seminar ausgewählten Kapitel aus den Büchern Distributed Computing [1] und Distributed Algorithms [2] behandelt. Je nach Umfang des Stoffes werden die Kapitel an ein oder zwei Seminarteilnehmer vergeben.

·  Das Teilzeitparlament von Paxos [gafni.lamport:diskpaxos] [lamport:parttime]
·  Verteilte Einigung Kapitel 12/17.2.3 aus [2]
·  Atomare Objekte Kapitel 13 von [2] (2 Vorträge)
·  Resourcenzuteilung in Netzwerken Kapitel 20 aus [2]
·  Asynchrone Netzwerke und Prozessfehler Kapitel 21 aus [2]
·  Data-Link Protokolle Kapitel 22 aus [2]
·  Uhrensynchronisation und Fehlertoleranz Kapitel 6.3 + 13 aus [1]
·  Verteilter gemeinsamer Speicher Kapitel 7,9 aus [1]
·  Fault-tolerant simulations of read-write objects Kap. 10 aus [1], Kap. 13 aus [2] (2 Vorträge)
·  Simulating synchrony Kap. 11 aus [1], Kap. 16 aus [2] (ein Vortrag)
·  Improving the fault-tolerance of algorithms Kap. 12 aus [1] (2 Vorträge)
·  Wait-free simulations of arbitrary objects Kap. 15 aus [1], Kap. 13 aus [2] (2 Vorträge)


Scheinkriterium

Verlangt ist die Ausarbeitung (mit Hilfestellung natürlich) und die Präsentation eines Vortrages über das gewählte Thema. Relevant sind

Links

References

[1]
H. Attiya and J. Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics. McGraw-Hill, 1998.

[2]
N. Lynch. Distributed Algorithms. Kaufmann Publishers, 1996.
Pages last (re-)generated April 1, 2004
This document was translated from LATEX by HEVEA.