Allgemeines

Veranstaltungsnummer  040604
Veranstalter Thomas Zeume
Klassifikation Proseminar
Semester Wintersemester 2016/17
Ort und Zeit  OH12-3.031, Mi 16.00 Uhr -18.00 Uhr
Vorbesprechung 21.7., 14.00 Uhr
Querverbindungen DAP 2, GTI
Voraussetzungen wünschenswert DAP2, MafI I + II

 

Inhalt

In vielen modernen Anwendungen werden Probleme durch den Einsatz mehrerer Prozessoren gelöst. Diese können lokal in einem Computer liegen oder über ein Netzwerk verbunden sein. Verteilte Algorithmen steuern Berechnungen, die auf mehreren solcher Prozessoren verteilt ablaufen. Die einzelnen Teile eines verteilten Algorithmus laufen dabei nebenläufig und unabhängig auf den unterschiedlichen Prozessoren. Im Gegensatz zu parallelen Algorithmen gibt es in verteilten Algorithmen keine zentrale Steuerung.

Typische algorithmische Probleme die durch verteilte Algorithmen gelöst werden, sind beispielsweise

  • die Erzielung eines Konsenses,
  • die Verteilung von Ressourcen sowie die Regelung des wechselseitigen Ausschluss beim Zugriff auf Ressourcen, und
  • die Synchronisation der beteiligten Prozesse,

Verteilte Algorithmen sollen möglichst robust gegen Ausfälle von Prozessoren, Speichern oder Verbindungen sein. Zudem sollen sie möglichst effizient ablaufen.

Im Proseminar werden wir grundlegende verteilte Algorithmen kennenlernen. Wir werden lernen, wie sich ihre Laufzeit abschätzen und ihre Korrektheit beweisen lässt. Das Proseminar basiert auf den Büchern "Distributed Algorithms" von Nancy Lynch und "Cake-Cutting Algorithms" von Jack Robertson und William Webb.

Für die Teilnahme am Proseminar sind solide algorithmische Grundkenntnisse (erworben beispielsweise in DAP2) sowie ein grundlegendes Verständnis formaler Beweismethoden (wie in den Vorlesungen Mathematik für Informatiker 1 und 2 sowie den Grundlagen der theoretischen Informatik vermittelt) wünschenswert.