Theory of Distributed Computing 1: Algorithms and Lower Bounds (Integrated course, SoSe 2011)

We live in the age of distributed systems: Virtually any computer architecture or application today is distributed. Examples include multi-core computers, peer-to-peer systems, or sensor networks. All these applications have in common that the entities have certain degrees of freedom (e.g., have their own hardware or code) and many entities are active at any time. Despite these commonalities, there are important differences, e.g., peer-to-peer systems may operate more asynchronously than multi-core computers.

In this lecture we study what can and cannot be computed in the different kinds of distributed systems. We start with the shared memory model and consider fundamental problems such as the election of a leader. We then extend our investigations to distributed systems that connect the entities via a communication network. We compare different networks and introduce different complexity measures such as time and message complexity. We then revisit important problems such as leader election or vertex coloring for this model. Finally, if time permits, dynamic, robust, and selfish networks are discussed.

• The lecture is over.

If you are interested in attending, please make sure you are subscribed to this course in ISIS to receive information and announcements.

A module registration is also obligatory for Master studetns. Further information will be given in the lecture or via ISIS.

There will be exercises (exercise sheets). You need 50% of the possible points to pass.

Written exam. Further information will be announced in the lecture or via ISIS.

More slides and further information (research papers, exercises) are available on the ISIS page.

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