Zur Hauptnavigation Zum Inhaltsbereich Zur Suche Zum Seitenfuß

Vorlesung: Höhere Modellierungskonzepte und -algorithmen: Verteilte Algorithmen

Veranstalter: Rüdiger Valk, Daniel Moldt

Termin: Dienstag, 10:15 - 11:45 in G-022 (SoSe 2016)

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 "Modellierung verteilter Systeme (MVS)" enthält das auch separat belegbare Seminar "Modellierung verteilter Systeme"..

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
  • A. D. Kshemkalyani, M. Singhal: Distributed Computing - Principles, Algorithms, and System, Cambridge University Press, Cambridge 2008

    • Folien zum SoSe 2017 im pdf-Format:

    Benutzername und Passwort wie in FGI 2 oder Vorlesung Petrinetze oder durch Anfrage bei Rüdiger Valk.
  • Folien zu Kapitel 1: Einleitung und Routenplanung im Netzwerk: Kap1-VA(wege)skript2017.pdf [Stand: 4.4.2017]

    • Folien im pdf-Format:

    Diese werden hier vor dem Vortrag abgelegt. Bitte zur Vorbereitung nutzen! Beachten Sie ggf. Nachbesserungen nach dem Vortrag! Benutzername und Passwort wie in FGI 2 oder Vorlesung Petrinetze oder durch Anfrage bei Rüdiger Valk. Zur Vorbereitung siehe die Folien aus dem Vorjahr.
  • Folien zu Kapitel 1: Einleitung und Routenplanung im Netzwerk: Kap1-VA(wege)skript.pdf [Stand: 5.4.2016]
  • Folien zu Kapitel 2: Verteilter wechselseitiger Ausschluss, Teil 1 Kap2-VA(wa)skript.pdf [Stand: 19.4.2016]
  • Folien zu Kapitel 3: Konsens-Algorithmen Kap3-VA(konsens)-skript-c.pdf [Stand: 10.5.2016]
  • Folien zu Kapitel 4: Asynchrone Systeme Kap4-VA(asynchron)-skript.pdf [Stand: 2.5.2016]
  • Folien zu Kapitel 5: Broadcast-Algorithmen Kap5-VA(broadcast)-skript-c.pdf [Stand: 18.5.2016]
  • Folien zu Kapitel 6: Verteiltes Gerüst Kap6-VA(geruest)-skript-c.pdf [Stand: 23.6.2016]
  • Folien zu Kapitel 7: Verteilte Termination und Rückblick Kap7-VA(termination)-skript-c.pdf [Stand: 5.7.2016]

    • Ablaufaufzeichnungen mit Audio im mov-Format:

    Benutzername und Passwort wie in FGI 2 oder Vorlesung Petrinetze oder durch Anfrage bei Rüdiger Valk.
  • Aufn. 5.4.2016: Einleitung und Routenplanung im Netzwerk: Kap1-VA(wege)05042016.mov [Stand: 5.4.2016]
  • Aufn. 12.4.2016 10:15: Routenplanung im Netzwerk Teil 2: Kap1-VA(wege)12042016-1.mov [Stand: 12.4.2016]
  • Aufn. 12.4.2016 12:15: Wechselseitiger Ausschluss Teil 1: Kap1-VA(wege)12042016-2.mov [Stand: 12.4.2016]
  • Aufn. 19.4.2016: Wechselseitiger Ausschluss Teil 2: Kap2-VA(wa)19042006.mov [Stand: 19.4.2016]
  • Aufn. 26.4.2016: WA Teil 3 und Konsens Teil 1 Kap2-VA(wa)26042016.mov [Stand: 26.4.2016]
  • Aufn. 3.5.2016: Konsens-Algorithmen Teil 2 Kap3-VA(konsens)03052016.mov [Stand: 3.5.2016]
  • Aufn. 10.5.2016: Konsens 3 und Asynchrone Systeme 1 Kap3-VA(konsens)10052016.mov [Stand: 12.5.2016]
  • Aufn. 24.5.2016: Konsens 4 und Asynchrone Systeme 2 Kap3-VA(konsens)24052016.mov [Stand: 24.5.2016]
  • Aufn. 7.6.2016: Asynchrone Systeme 3 und Broadcast 1 Kap4-VA(asynchron)07062016.mov [Stand: 7.6.2016]
  • Aufn. 14.6.2016: Broadcast 2 und verteiltes Gerüst 1 Kap5-VA(broadcast)14062016.mov [Stand: 14.6.2016]
  • Aufn. 21.6.2016: Verteiltes Gerüst 2 Kap6-VA(geruest)21062016.mov [Stand: 21.6.2016]
  • Aufn. 23.6.2016: Verteiltes Gerüst 3 und verteilte Termination 1 Kap6-VA(geruest)23062016.mov [Stand: 23.6.2016]
  • Aufn. 28.6.2016: Verteilte Termination 2 Kap7-VA(termination)28062016.mov [Stand: 28.6.2016]
  • Aufn. 5.7.2016: Verteilte Termination 3 und Rückblick Kap7-VA(termination)05072016.mov [Stand: 5.7.2016]

    als pdf-Dateien verfügbare Literatur:

  • Literatur zu Kapitel 1: Verteilte Routenplanung im Netzwerk Literatur kuerzeste Wege.zip
  • Literatur zu Kapitel 2: Wechselseitiger Ausschluss Literatur WA-web.zip
  • Literatur zu Kapitel 7: Verteiltes (minimales) Gerüst" Literatur geruest-web.zip
    • Impressum
    Letzte Änderung: 13:39 05.07.2016   Seitenanfang