Termin: Montag, 10:15 - 11:45 in C-221 (SoSe 2009)
Vorgehen
Die Vorlesung unterteilt sich in die Veranstaltung "Verteilte Algorithmen (A)" am Montag und "The Corporate Web: Selbstorganisierende Architekturen (B)" am Dienstag. Beide Teile sind jeweils in sich abgeschlossen, so dass Studenten des Diplomstudiengangs wahlweise auch nur eine der beiden Veranstaltung besuchen können.
Die Darstellung ist unabhängig von dem entsprechenden Inhalt der Vorlesung FGI 2 / PNL führt diese jedoch mit weiteren Verfahren fort (siehe unten). Beispielweise wird am Anfang am Beispiel des Problems der kürzesten Wege in einem Graphen gezeigt, wie verteilte Algorithmen aus den klassischen Algorithmen zu diesem Problem entwickelt werden können. "Kürzeste Wege" sind in Netzwerken von besonderer Bedeutung für Routing-Entscheidungen. Anders als in FGI 2 / PNL wird - dem Charakter einer kleineren Vorlesung entsprechend - auf die speziellen Wünsche und Bedürfnisse der Teilnehmenden eingegangen.
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:
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
Impressum
Korrekturen, Anmerkungen bitte an:
Rüdiger Valk
