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.

• Die Vorlesung ist vorbei.

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.

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

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 [6].

• 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)

• 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])