Page Content
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.
Overview
| Lecturers: | Petr Kuznetsov, Stefan Schmid, Uwe Nestmann (FG MTV) |
| Additional contact person: | Srivatsan Ravi |
| Event type: | Integrated course (Integrierte Veranstaltung) |
| Area: | Diplom Informatik: tba Master of Computer Science: Dependabale Systems (Master Informatik: Verlässliche Systeme) Master of Computer Engineering: Software Engineering (Master Technische Informatik: Software Engineering) |
| Module: | MINF-VS-TDC.S11 |
| exam&module registration: | via exam office (Prüfungsamt) |
| SWS: | 2 |
| ECTS/LP: | 3 |
| Time: | tuesdays, 12–2 p.m., weekly |
| First meeting: | 12 April 2011 |
| Room: | Auditorium 1 (TEL 20) |
| Course ID: | 0432 L 817 |
| Audience: | bachelor students after their basic studies (from the fifth semester on), master students, and Diplom students |
| Prerequisites: | No particular module, but maturity in mathematics and programming is expected. |
| Exam: | written, further details will be announced later |
| Further information: | see corresponding ISIS page |
Registration
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.
Download of lecture slides
- 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
More slides and further information (research papers, exercises) are available on the ISIS page.
General Literature
- 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)
Further Literature on certain topics
- 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)