Inhalt des Dokuments
zur Navigation
Foundations of Distributed Systems (Integrierte Veranstaltung, SoSe 2012)
Diese Vorlesung befasst sich mit fundamentalen Prinzipen und Problemen von verteilten Systemen, angefangen von Multi-Core Prozessoren bis hin zu globalen Internetanwendungen wie Peer-to-Peer Systemen. Ein Verständnis dieser Grundlagen ist wichtig, um Grenzen der verteilten Berechenbarkeit zu erkennen, um die Korrektheit existierender Systeme formal zu analysieren, aber auch um selber effiziente Algorithmen und skalierbare Architekturen zu entwerfen. Der erste Teil der Vorlesung befasst sich mit Shared-Memory Architekturen, während der Fokus des zweiten Teils auf dem Message-Passing Paradigma liegt.
Überblick
| Dozenten: | Petr Kuznetsov, Stefan Schmid, Uwe Nestmann (FG MTV) |
| weiterer Ansprechpartner: | Srivatsan Ravi |
| Veranstaltungstyp: | Integrierte Veranstaltung |
| Gebiet: | Master Informatik: Verlässliche Systeme, Kommunikationsbasierte Systeme Master Technische Informatik: Software Engineering |
| Modul: | MINF-VS-FDS.S12 |
| Prüfungs-&Modulanmeldung: | tba |
| SWS: | 4 |
| LP: | 6 |
| Zeit: | dienstags, 12–14 Uhr, wöchentlich |
| Erster Termin: | 10. April 2012 |
| Raum: | Auditorium 2 (TEL 20) |
| Übung: | montags, 16–18 Uhr, wöchentlich TEL 1118/19 |
| Veranstaltungsnummer: | 0432 L 819 / 0434 L 350 |
| Hörerkreis: | Bachelor-Studierende nach dem Grundlagenstudium (ab dem fünften Semester), Master-Studierende und Diplom-Studierende |
| Voraussetzungen: | kein bestimmtes Modul, es werden aber Kenntnisse der Mathematik, Algorithmik und der Programmierung vorausgesetzt. |
| Prüfung: | mündlich. Weitere Informationen werden später bekannt gegeben. |
| weitere Informationen: | s. zugehörige ISIS-Seite |
Inhalte
Die Vorlesung vermittelt ein grundlegendes Verständnis der wichtigen Aspekte beim Design von verteilten Algorithmen, Werkzeuge um die Korrektheit und Komplexität dieser Algorithmen formal zu analysieren, sowie Techniken zur Ermittlung von Lower Bounds. Der Begriff von "verteilten Systemen" ist algorithmisch zu verstehen; es werden keine realen Systeme programmiert.
Anmeldung
Falls du an der Vorlesung teilnehmen willst, trag dich bitte auf der zugehörigen ISIS-Seite (tba) ein, um wichtige Informationen und Ankündigungen zu erhalten.
Für Master-Studierende ist außerdem eine Modulanmeldung erforderlich. Weitere Informationen dazu werden in der Vorlesung und via ISIS bekannt gegeben.
Prüfungen
Es wird mündliche Prüfungen geben. Weitere Informationen werden in der Vorlesung oder via ISIS bekannt gegeben.
Download der Vorlesungsfolien
- Class 01a: Overview: Message Passing (FDS 2012) PDF, 788 KB
- Class 01b: Overview: Shared memory (FDS 2012) PDF, 7 MB
- Class 02: safety and liveness (FDS 2012) PDF, 200 KB
- Class 03: shared memory basics (FDS 2012) PDF, 148 KB
- Class 04: implementing an atomic bit (FDS 2012) PDF, 194 KB
- Class 05: atomic and immediate snapshots (FDS 2012) PDF, 213 KB
- Class 06: atomic and immediate snapshots (part 2; FDS 2012) PDF, 179 KB
- Class 07: consensus and set agreement (FDS 2012) PDF, 198 KB
- Class 08: universality and consensus numbers (FDS 2012) PDF, 121 KB
- Class 09: Topology (FDS 2012) PDF, 2 MB
- Class 10: Leader Election (FDS 2012) PDF, 362 KB
- Class 11: Trees (FDS 2012) PDF, 915 KB
- Class 12: Vertex Coloring (FDS 2012) PDF, 448 KB
- Class 13: Distributed Maximal Independent Sets (FDS 2012) PDF, 782 KB
- Class 14: Locality Lower Bounds (Coloring; FDS 2012; UPDATED) PDF, 568 KB
Übungszettel
- Exercise Set 01: shared memory transformations (FDS 2012) PDF, 41 KB
- Exercise Set 02: atomic-bit construction (due May 7, FDS 2012) PDF, 56 KB
- Exercise Set 03: atomic and immediate snapshot (due May 14, FDS 2012; updated) PDF, 40 KB
- Exercise Set 04: immediate snapshot (due May 21; FDS 2012; updated) PDF, 50 KB
- Exercise Set 05: consensus (due June 4; FDS 2012) PDF, 39 KB
- Exercise Set 06: Asymptotic Notations and Graph Terminologies (due June 11; FDS 2012) PDF, 125 KB
- Exercise Set 07: Topology (due June 11; FDS 2012) PDF, 132 KB
- Exercise Set 08 (due June 18; FDS 2012) PDF, 50 KB
- Exercise Set 09 (due June 25; FDS 2012) PDF, 103 KB
- Exercise Set 10 (due July 9; FDS 2012) PDF, 103 KB
Allgemeines
- Lynch, N: Distributed Algorithms. Morgan Kaufmann Publishers, 1996.
- H. Attiya, J. Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition). Wiley. 2004
- M. Herlihy and N. Shavit. The art of multiprocessor programming. Morgan Kaufman, 2008
- David Peleg, Distributed Computing: A Locality Sensitive Approach, SIM, 1987.