Termin: Dienstag, 8:30 - 10:00 in C-221 (SoSe 2013)
Vorgehen
Das Thema "Berechenbarkeit und Komplexität" wird aus der Perspektive verteilter Systeme behandelt. Anders als in klassischen Algorithmen für Einprozessor-Rechner kann hier keine zemtrale Steuerung und Datenhaltung eingesetzt werden. Vielmehr hat jeder der in dem Prozessorsystem eingebundenen Rechner eigene, lokale Daten. Nur durch Kooperation mittels ausgetauschter Nachrichten kann ein globales Ziel, ein Rechen- oder Entscheidungsergebnis erreicht werden.
Inhalte:
Es werden Verfahren zur Lösung von Problemen behandelt, die bei der Kommunikation in Rechnernetzen auftreten und auf einer abstrakten, algorithmischen Ebene gelöst werden können. Beispielsweise besteht ein schwieriges Problem darin festzustellen, ob alle Prozesse eines Prozessornetzes terminiert haben ("verteilte Termination"). Andere Problemfelder beinhalten die (verteilte) Konstruktion eines Gerüsts (aufspannender Baum), Flüsse und Routenplanung in Netzwerken, den verteilten wechselseitigen Ausschluss, die verteilte und konsistente Verwaltung von Objekten.
Die Probleme werden unter unterschiedlichen Randbedingungen betrachtet:
offene Systeme,
bekannte Knotenzahl,
Baum-, Ringstruktur usw. und es wird, wo möglich, ihre Komplexität untersucht.
Lernziel:
Verständnis der besonderen Problematik verteilter Algorithmen, spezielle Algorithmen in und über Netzwerken, ihre Beschreibung, Korrektheit und Komplexität
Literatur als Monographien:
H. Attiya, J. Welch: Distributed Computing, McGraw-Hill, London, 1998
W. Reisig: Elements of Distributed Algorithms, Springer, Berlin 1998
N.A. Lynch: Distributed Algorithms, Morgan Kaufmann, San Francisco, 1996
F. Mattern: Verteilte Basicalgorithmen, Springer, Berlin, 1989
V.K. Garg: Elements of Distributed Computing, Wiley, New York, 2002
aktuelle Folien:
Passwort wie zu FGI-2/PNL oder erfragen bei:
Rüdiger Valk
