direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

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.

Aktuelles

  • Die Vorlesung ist vorbei.

Überblick

Informationen
Dozenten:
Petr Kuznetsov, Stefan Schmid,
Uwe Nestmann (FG MTV)
weiterer Ansprechpartner:
Srivatsan Ravi
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

Organisatories

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.

Hausaufgaben

Es wird Übungen (Übungszettel) geben. Zum Bestehen sind mind. 50% der Punkte notwendig.

Prüfungen

Es wird schriftliche Prüfungen geben. Weitere Informationen werden in der Vorlesung oder via ISIS bekannt gegeben.

Mehr Folien und weitere Informationen (Veröffentlichungen, Übungszettel) gibt's im ISIS.

Literatur

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)
  • Moni Naor, Udi Wieder. Novel architectures for P2P applications: The continuous-discrete approach. ACM Transactions on Algorithms (TALG), 3(3), August 2007. (link)
  • J. Kleinberg. Navigation in a Small World. Nature, Volume 406(2000), 845 (pdf)
  • 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)
  • Christian Scheideler and Stefan Schmid. A Distributed and Oblivious Heap. 36th International Colloquium on Automata, Languages and Programming (ICALP) 2009. (pdf)

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Anmeldung im Prüfungsamt

Anmeldungen zu Modulen
und Prüfungen bei INET
übers Prüfungsamt

Theory of Distributed Computing 1: Algorithms and Lower Bounds
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
ISIS

Complete domains

...of e-mail addresses
@inet =
@inet.tu-berlin.de
@tub = @tu-berlin.de