Page Content
to Navigation
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.
News
- May 24: No class!
- May 2: Slides for the lectures and additional material are available at the TDC ISIS page
- This course will be held in Engilish.
- The module registration takes place in the Prüfungsamt (exam office). Further information in the first lecture.
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 |
Organization
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.
Homework
There will be exercises (exercise sheets). You need 50% of the possible points to pass.
Exam
Written exam. Further information will be announced in the lecture or via ISIS.
Download of lecture slides
- TDC-1 01: Introduction: Message-Passing ModelsPDF, 5,7 MB
- TDC-1 01: Introduction: Shared-Memory ModelsPDF, 1,1 MB
- TDC-1 02: Safety and Liveness in Concurrent ImplementationsPDF, 236,0 KB
- TDC-1 03: Shared memory transformationsPDF, 176,1 KB
- TDC-1 04: Atomic snapshots and atomic bitsPDF, 801,1 KB
- TDC-1 05: Consensus and 1-resilient BG simulationPDF, 282,9 KB
- TDC-1 06: Solving consensusPDF, 134,9 KB
- TDC-1 07: Universal constructionPDF, 190,5 KB
- TDC-1 08: TopologiesPDF, 1,2 MB
- TDC-1 09: Leader ElectionPDF, 250,3 KB
- TDC-1 10: Tree AlgorithmsPDF, 661,6 KB
- TDC-1 11: Vertex ColoringPDF, 485,5 KB
- TDC-1 12: Maximal Independent SetPDF, 561,2 KB
- TDC-1 13: Lower BoundsPDF, 321,9 KB
- TDC-1 14: Social NetworksPDF, 785,0 KB
Script
More slides and further information (research papers, exercises) are available on the ISIS page.
Literature
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)