Institut für Betriebssysteme und Rechnerverbund
- News
- Wir über uns
- Connected and Mobile Systems
- Verlässliche Systemsoftware
  - Team
  - Advent(2)
- Algorithmik
- Mikroprozessorlabor
- Studium
- Service
- Spin-Offs
- Forschungsverbünde
  - IST.hub

Verteilte Algorithmen

Semester	Sommersemester 2010 Sommersemester 2014 Sommersemester 2012 Sommersemester 2008
Modulnummer	INF-ALG-06
Veranstaltungsnummer	INF-ALG-011, INF-ALG-012
Studiengänge	Informatik Master, Informations-Systemtechnik Master, Wirtschaftsinformatik Master
IBR Gruppe	ALG (Prof. Fekete)
Art	Vorlesung & Übung
Dozent	Dr. Alexander Kröller Ehemaliger Juniorprofessor
Assistent	Dr. Christiane Schmidt Ehemalige Wissenschaftliche Mitarbeiterin
LP	4
SWS	2+1
Ort & Zeit	zweijährlich ab SoSe 2008 Vorlesung: Mittwoch, 09:45 - 11:15, Raum SN 23.1 Übung: Montag, 16:45 - 18:15, Raum 161 . (Termine für die Übung: 19.04., 03.05., 17.05., 07.06., 21.06., 05.07. (12.07.))
Beginn	Die erste Vorlesung findet am 07.04.2010 statt. Die erste Übung findet am 19.04.2010 statt.
Voraussetzungen	Grundkenntnisse aus Algorithmen und Datenstrukturen. Bei einigen Themen sind Kenntnisse auf Netzwerkalgorithmen und Computational Geometry (Algorithmische Geometrie) vorteilhaft, werden aber nicht vorausgesetzt (und jeweils in der VL eingeführt).
Scheinerwerb	Erfolgreiche Bearbeitung der Hausaufgaben und erfolgreiche Teilnahme an der mündlichen Prüfung.
Inhalt	In dieser Vorlesung werden theoretische und algorithmische Grundlagen verteilter Systeme diskutiert. Dafür betrachten wir Problemstellungen, bei denen beispielsweise die Knoten eines Netzwerks gemeinsam ein algorithmisches Problem lösen sollen, indem sie miteinander kommunizieren und lokale Berechnungen ausführen. Die Fragen sind der Art "Wie schnell kann dieses Problem gelöst werden?", "Wieviel Kommunikation ist dafür notwendig?", "Welche Charakteristika muss ein Netz haben, um dieses Problem überhaupt lösen zu können?". Das vorläufige Programm ist das folgende; das kann bei Interesse (oder Desinteresse) an bestimmten Themen auch angepasst werden. Modelle, Schranken, Komplexitäten, Berechenbarkeit. Grundlegende Netzwerkalgorithmen und -strukturen, Kommunikationsparadigmen. Lokale und selbstabilisierende Algorithmen. Asynchrone vs. synchrone Netzwerke. Geometrische und drahtlose Netzwerke.
Literatur/Links	Nancy Lynch: Distributed Algorithms. Morgan Kaufmann Publishers. David Peleg: Distributed Computing - A Locality-Sensitive Approach. SIAM. Dorothea Wagner und Roger Wattenhofer: Algorithms for Sensor and Ad Hoc Networks, Advanced Lectures. Springer Verlag.
Hausaufgaben Hausaufgabenblatt Nr. 1: [PDF] Hausaufgabenblatt Nr. 2: [PDF] Hausaufgabenblatt Nr. 3: [PDF] Hausaufgabenblatt Nr. 4: [PDF] Hausaufgabenblatt Nr. 5: [PDF] Eine kleine [Hilfe für Aufgabe 1] (verwende ein Blatt pro Iteration). Hausaufgabenblatt Nr. 6: [PDF]