Inhalt des Dokuments
Theory of Distributed Computing 1: Algorithms and Lower Bounds (Integrierte Veranstaltung, SoSe 2011)
Wir leben im Zeitalter der
verteilten Systeme: Es gibt kaum eine Computerarchitektur oder
-anwendung, die nicht verteilt ist, und
sowohl Multi-Core-Prozessoren, Peer-to-Peer-Systeme oder
Sensornetzwerke bestehen aus relativ autonomen Komponenten oder
sogenannten Knoten (z.B. mit eigener Hardware oder eigenem Code),
welche gleichzeitig aktiv sind. Natürlich gibt es aber auch wichtige
Unterschiede zwischen verschiedenen verteilten Systemen,
beispielsweise bezüglich der Anforderungen an die Synchronität der
Komponenten.
Diese Vorlesung befasst sich mit der
Berechenbarkeit in verschiedenen verteilten Systemen. Wir studieren
verteilte Algorithmen für fundamentale Probleme wie Symmetriebrechung
oder Graphfärbungen, und leiten Lower Bounds oder
Unmöglichkeitsresultate her. Wir beginnen mit dem
Share-Memory-Modell und gehen dann zu verteilten Systemen über,
welche auf einem Kommunikationsnetz basieren. Wir vergleichen
verschiedene Netzarchitekturen und analysieren die Zeit- und
Nachricht-Komplexitäten diverser Algorithmen auf diesen Netzen.
Abhängig von der verfügbaren Zeit werden wir uns zum Schluss mit
dynamischen und robusten Netzwerkarchitekturen befassen und auch
spieltheoretische Aspekte diskutieren.
Überblick
Dozenten: | Petr Kuznetsov [1], Stefan
Schmid [2], Uwe Nestmann [3] (FG MTV) |
weiterer
Ansprechpartner: | Srivatsan Ravi [4] |
Veranstaltungstyp: | Integrierte
Veranstaltung |
Gebiet: | Diplominformatik:
tba Master Informatik: Verlässliche Systeme Master Technische Informatik: Software Engineering |
Modul: | MINF-VS-TDC.S11 |
Prüfungs-&Modulanmeldung: | im
Prüfungsamt |
SWS: | 2 |
LP: | 3 |
Zeit: | dienstags, 12–14 Uhr,
wöchentlich |
Erster Termin: | 12.
April 2011 |
Raum: | Auditorium 1 (TEL 20) |
Veranstaltungsnummer: | 0432 L
817 |
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 und der
Programmierung voraus gesetzt. |
Prüfung: | schriftlich. Weitere
Informationen werden später bekannt
gegeben. |
weitere Informationen: | s. zugehörige ISIS-Seite
[5] |
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 schriftliche Prüfungen geben. Weitere Informationen werden in der Vorlesung oder via ISIS bekannt gegeben.
Download der Vorlesungsfolien
- TDC-1 04: Atomic snapshots and atomic bits PDF, 801 KB
- TDC-1 05: Consensus and 1-resilient BG simulation PDF, 283 KB
- TDC-1 06: Solving consensus PDF, 135 KB
- TDC-1 07: Universal construction PDF, 191 KB
- TDC-1 08: Topologies PDF, 1 MB
- TDC-1 09: Leader Election PDF, 250 KB
- TDC-1 10: Tree Algorithms PDF, 662 KB
- TDC-1 13: Lower Bounds PDF, 322 KB
- TDC-1 14: Social Networks PDF, 785 KB
Allgemeines
- Nancy Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, 1996. (english)
- H. Attiya and J. Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition). Wiley. 2004 (english)
- M. Herlihy and N. Shavit. The art of multiprocessor programming. Morgan Kaufman, 2008. (english)
- David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia, PA, USA, 2000. (english)
- Juraj Hromkovic, Ralf Klasing, Andrzej Pelc, Peter Ruzicka, and Walter Unger. Dissemination of Information in Communication Networks. Springer. 2005 (english)
- Frank Thomson Leighton.
Introduction to Parallel Algorithms and Architectures: Arrays,
Trees, Hypercubes. Morgan Kaufmann Publishers, 1991 (english)
- Thomas Cormen, Charles Leiserson, and Ronald Rivest. Introduction to Algorithms. The MIT Press, 1998 (english)
Weitere Literaturhinweise zu bestimmten Themen
- Fabian Kuhn, Stefan Schmid, and Roger Wattenhofer. Towards Worst-Case Churn Resistant Peer-to-Peer Systems. Journal Distributed Computing (DIST), 22(4), 249-267, Springer, May 2010. (pdf [7])
- Moni Naor, Udi Wieder. Novel architectures for P2P applications: The continuous-discrete approach. ACM Transactions on Algorithms (TALG), 3(3), August 2007. (link [8])
- J. Kleinberg. Navigation in a Small World.
Nature, Volume 406(2000), 845 (pdf [9])
- Thomas Locher,
Stefan Schmid, and Roger Wattenhofer. eDonkey & eMule's Kad:
Measurements & Attacks. Fundamenta Informaticae, Volume 110,
IOS Press, 2011.
- Riko Jacob, Andréa Richa, Christian Scheideler, Stefan Schmid, and Hanjo Täubig. A Polylogarithmic Time Algorithm for Distributed Self-Stabilizing Skip Graphs. 28th ACM Symposium on Principles of Distributed Computing (PODC) 2009. (pdf [10])
- Christian Scheideler and Stefan Schmid. A Distributed and Oblivious Heap. 36th International Colloquium on Automata, Languages and Programming (ICALP) 2009. (pdf [11])
Lehre / Teaching, SoSe 2011
- Internet Routing (VL) [12]
- Internet Security (VL) [13]
- Network Optimization by Randomization (IV) [14]
- Theory of Distributed Computing 1 (IV) [15]
- NA: Internet Measurement (SE) [16]
- Routerlab (PR) [17]
0432 L 817
Integrierte LV (VL mit UE)
Dozent: Petr Kuznetsov, Stefan Schmid, Uwe Nestmann
Zeitraum:
12.04.2011 bis 12.07.2011
Di 12:00 - 14:00 Uhr
Ort: Auditorium 1 (TEL 20)
Webseite [18]
ISIS [19]
etr/parameter/de/
rchers/stefan/parameter/de/
rivatsan/parameter/de/
40
40
mp10.pdf
x?id=73859
ing/SS11/TDC1/art_rexhepaj_elton.pdf
angene_semester/ss2011/ir11/parameter/de/
angene_semester/ss2011/is11/parameter/de/
angene_semester/ss2011/nor11/parameter/de/
angene_semester/ss2011/tdc11/parameter/de/
angene_semester/ss2011/se11/parameter/de/
angene_semester/ss2011/rl11/parameter/de/
angene_semester/ss2011/tdc11/parameter/de/
640