Termin: Dienstag, 10:15 - 11:45 in C-221 (SoSe 2015)
Lernziel
Verteilte Algorithmen werden z.B. in Netzwerken von Prozessoren verwendet, in denen nicht auf eine zentrale Instanz (effektiv) zugegriffen werden kann und die gestellte algorithmische Aufgabe nur durch asynchrone Kommunikation über Kanäle zu erreichen ist, wobei die Laufzeiten von Nachrichten auf diesen Kanälen nicht eingeschränkt sind. Nicht nur traditionelle Algorithmen für Einprozessormaschinen müssen für diesen Einsatz grundlegend modifiziert werden, sondern es gibt wichtige Probleme, die überhaupt erst bei Rechnernetzen auftreten. Verteilte Algorithmen werden gerne auch im Scenario der Multiagenten formuliert.
Lernziel ist daher das Verständnis der besonderen Problematik verteilter Algorithmen, das Erlernen spezieller solcher Algorithmen in und über Netzwerken und Agentensystemen, ihre Beschreibung, Korrektheit und Komplexität.
Vorgehen
Es werden Verfahren zur Lösung von Problemen behandelt, die bei der Kommunikation in Agentensystemen und 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 verteilte Routenplanung im Netzwerk, verteiltes minimales Gerüst (spanning tree), verteilter wechselseitiger Ausschluss, Auswahlverfahren, Broadcast-Algorithmen, Konsens-Algorithmen, verteilte Termination, verteilte Freispeicher-Verwaltung (garbage collection).
Zusätzliche Hinweise zu Prüfungen
Die Vorlesung unterteilt sich in die Veranstaltung "Modelle von Petrinetzen (A)" und "Höhere Modellierungskonzepte und - algorithmen (Verteilte Algorithmen) (B)". Beide Teile sind jeweils in sich abgeschlossen, so dass Studierende (insb. des Diplomstudiengangs) wahlweise auch nur eine der beiden Veranstaltung besuchen können.
Anrechbarkeit ist grundsätzlich gegeben.
Das Modul "InfM WPM7 (MVS) Modellierung verteilter Systeme (MVS)" enthält weiterhin das auch separat belegbare Seminar "Modellierung verteilter Systeme".
Das Modul „Modellierung“ (MV2) wurde bereits im Sommer 2011 durch das Master-Wahlpflichtmodul WPM7 abgelöst. Studierende, die vor 2010 das Masterstudium aufgenommen haben, können eine Anrechnung der Vorlesungen als MV2 beim Prüfungsausschuss beantragen.
Die Veranstaltung lässt sich auf einfachen Antrag entsprechend anrechnen!
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
pdf-Folien:
Passwort wie zu FGI-2/PNL oder erfragen bei:
Rüdiger Valk
