Small logo of ETH main building ETH Zurich : Computer Science : Pervasive Computing : Distributed Systems : Education : DA WS2003/2004

Verteilte Algorithmen

Prof. Dr. Friedemann Mattern
Vorlesung WS2004/2005

Zeit und Ort:

Mittwoch 9:15 - 12:00 IFW A34

Inhalt:

Verteilte Algorithmen sind Verfahren, die dadurch charakterisiert sind, dass mehrere autonome Prozesse gleichzeitig Teile eines gemeinsamen Problems in kooperativer Weise bearbeiten und der dabei erforderliche Informationsaustausch ausschliesslich über Nachrichten erfolgt. Derartige Algorithmen kommen im Rahmen verteilter Systeme zum Einsatz, bei denen kein gemeinsamer Speicher existiert und die Übertragungszeit von Nachrichten i.a. nicht vernachlässigt werden kann. Da dabei kein Prozess eine akuelle konsistente Sicht das globalen Zustands besitzt, führt dies zu interessanten Problemen.

Im einzelnen werden folgende Themenschwerpunkte behandelt:

  • Modelle verteilter Berechnungen
  • Raum-Zeit Diagrammen
  • Virtuelle Zeit; logische Uhren und Kausalität
  • Wellenalgorithmen
  • Verteilte und parallele Graphtraversierung
  • Berechnung konsistenter Schnappschüsse
  • Election und Symmetriebrechung
  • Verteilte Terminierung
  • Garbage-Collection in verteilten Systemen
  • Beobachten verteilter Systeme
  • Berechnung globaler Prädikate

Folien:

Folien werden hier einige Tage nach der jeweiligen Vorlesungsstunde zum Download bereitgestellt bzw. in der Vorlesung ausgeteilt. Eventuelle Nachfragen oder Fehlermeldungen bitte an domnitch@inf.ethz.ch schicken.

TR> TR>
Nr. Datum PDF-Format
1 20.10.2004 VA0405_01.pdf
2 27.10.2004 VA0405_02.pdf
3 03.11.2004 VA0405_03.pdf
4 10.11.2004 VA0405_04.pdf
5 17.11.2004 VA0405_05.pdf
6 24.11.2004 VA0405_06.pdf
7 01.12.2004 VA0405_07a.pdf
VA0405_07b.pdf
8 08.12.2004 VA0405_08.pdf
9 15.12.2004 VA0405_09.pdf
10 22.12.2004 VA0405_10.pdf
11 12.01.2005
19.01.2005
VA0405_11.pdf
12 26.01.2005 VA0405_12.pdf

Literatur:

  • F. Mattern: Verteilte Basisalgorithmen, Springer-Verlag, 1989.
  • G.Tel: Topics in Distributed Algorithms., Cambridge University Press, 1991.
  • G. Tel: Introduction to Distributed Algorithms, Cambridge University Press, Second Edition, 2000.
  • V. Barbosa: An Introduction to Distributed Algorithms, MIT Press, 1996.
  • N. Lynch: Distributed Algorithms, Morgan Kaufmann Pub., 1996.
  • S. Mullender: Distributed Systems, Addison-Wesley, Second Edition, 1993.
  • V. K. Garg: Principles of Distributed Systems , Kluwer, 1996.
ETH ZurichDistributed Systems Group
Last updated August 23 2010 01:55:16 PM MET ml