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

Verteilte Algorithmen

Prof. Dr. Friedemann Mattern
Vorlesung WS2001/2002

Zeit und Ort:

Mittwoch 13-14 IFW C42
Donnerstag   9-11 IFW C42

Inhalt:

Verteilte Algoritmen 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 wurden 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
  • Wechselseitiger Ausschluss
  • Election und Symmetriebrechung
  • Verteilte Terminierung
  • Garbage-Collection in verteilten Systemen
  • Beobachten verteilter Systeme
  • Berechnung globaler Prädikate

Folien:

Die vollständige Sammlung der Vorlesungsfolien und Übungsaufgaben:

PDF-Format PS-Format Gnu-Zipped PS-Format
1
VorlVA1.pdf (594K) VorlVA1.ps (1.49M) VorlVA1.ps.gz (674K)
U1
VorlVAueb1.pdf (7K) VorlVAueb1.ps (93K) VorlVAueb1.ps.gz (25K)
2
VorlVA2.pdf (102K) VorlVA2.ps (608K) VorlVA2.ps.gz (131K)
U2
VorlVAueb2.pdf (12K) VorlVAueb2.ps (126K) VorlVAueb2.ps.gz (33K)
3
VorlVA3.pdf (155K) VorlVA3.ps (389K) VorlVA3.ps.gz (184K)
4
VorlVA4.pdf (22K) VorlVA4.ps (176K) VorlVA4.ps.gz (43K)
5
VorlVA5Watt0.pdf (32K) VorlVA5Watt0.ps (209K) VorlVA5Watt0.ps.gz (53K)
6
VorlVA6Watt1.pdf (50K) VorlVA6Watt1.ps (193K) VorlVA6Watt1.ps.gz (25K)
7
VorlVA7Watt2.pdf (77K) VorlVA7Watt2.ps (100K) VorlVA7Watt2.ps.gz (36K)
8
VorlVA8.pdf (50K) VorlVA8.ps (312K) VorlVA8.ps.gz (74K)
9
VorlVA9.pdf (176K) VorlVA9.ps (441K) VorlVA9.ps.gz (213K)
U3
VorlVAueb3.pdf (51K) VorlVAueb3.ps (136K) VorlVAueb3.ps.gz (65K)
10
VorlVA10.pdf (114K) VorlVA10.ps (263K) VorlVA10.ps.gz (127K)
11
VorlVA11.pdf (19K) VorlVA11.ps (141K) VorlVA11.ps.gz (36K)
12
VorlVA12.pdf (18K) VorlVA12.ps (135K) VorlVA12.ps.gz (36K)
13
VorlVA13Watt.pdf (24K) VorlVA13Watt.ps (138K) VorlVA13Watt.ps.gz (47K)
14
VorlVA14Watt2.pdf (96K) VorlVA14Watt2.ps (185K) VorlVA14Watt2.ps.gz (30K)
15
VorlVA15.pdf (10K) VorlVA15.ps (105K) VorlVA15.ps.gz (27K)
16
VorlVA16.pdf (11K) VorlVA16.ps (118K) VorlVA16.ps.gz (30K)
17
VorlVA17.pdf (31K) VorlVA17.ps (219K) VorlVA17.ps.gz (54K)
18
VorlVA18.pdf (10K) VorlVA18.ps (115K) VorlVA18.ps.gz (29K)
19
VorlVA19.pdf (69K) VorlVA19.ps (396K) VorlVA19.ps.gz (92K)
U4
VorlVAueb4.pdf (5K) VorlVAueb4.ps (85K) VorlVAueb4.ps.gz (23K)
20
VorlVA20.pdf (53K) VorlVA20.ps (309K) VorlVA20.ps.gz (73K)
21
VorlVA21.pdf (62K) VorlVA21.ps (407K) VorlVA21.ps.gz (92K)
22
VorlVA22.pdf (134K) VorlVA22.ps (674K) VorlVA22.ps.gz (156K)
23
VorlVA23.pdf (282K) VorlVA23.ps (958K) VorlVA23.ps.gz (338K)
24
VorlVA24.pdf (898K) VorlVA24.ps (2013K) VorlVA24.ps.gz (1208K)
25
VorlVA25.pdf (88K) VorlVA25.ps (448K) VorlVA25.ps.gz (111K)
26
VorlVA26.pdf (600K) VorlVA26.ps (1327K) VorlVA26.ps.gz (718K)
27
VorlVA27.pdf (227K) VorlVA27.ps (914K) VorlVA27.ps.gz (252K)
28
VorlVA28.pdf (29K) VorlVA28.ps (265K) VorlVA28.ps.gz (51K)

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, 1994.
  • V. Barbosa: An Introduction to Distributed Algorithms, MIT Press, 1996.
  • N. Lynch: Distributed Algorithms, Morgan Kaufmann Pub., 1996.
ETH ZurichDistributed Systems Group
Last updated August 23 2010 01:55:15 PM MET jb