Small logo of ETH main building ETH Zurich : Computer Science : Pervasive Computing : Distributed Systems : Education : VA HS2016

Verteilte Algorithmen

Prof. Dr. Friedemann Mattern

Zeit und Ort:

Mittwoch 9:15 – 12:00 (Vorlesung in deutscher Sprache mit integrierter Übung)

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 aktuelle konsistente Sicht das globalen Zustands besitzt, führt dies zu interessanten Problemen.

Im einzelnen werden folgende Themenschwerpunkte behandelt:

  • Modelle verteilter Berechnungen
  • Raum-Zeit Diagramme
  • 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

Literatur:

  • Folienkopien
  • F. Mattern: Verteilte Basisalgorithmen, Springer-Verlag
  • G.Tel: Topics in Distributed Algorithms., Cambridge University Press
  • G. Tel: Introduction to Distributed Algorithms, Cambridge University Press, 2nd Edition
  • A. Kshemkalyani, M. Singhal: Distributed Computing: Principles, Algorithms, and Systems, Cambridge University Press
  • N. Lynch: Distributed Algorithms, Morgan Kaufmann Pub.
  • S. Mullender: Distributed Systems, Addison-Wesley, 2nd Edition
  • V. K. Garg: Principles of Distributed Systems , Kluwer
ETH ZurichDistributed Systems Group
Last updated June 20 2023 01:44:50 PM MET ko