Theory of Distributed Systems 1+2 (Summer 2020)
Topical
- Logbook with detailed information about schedule and content.
- Part I ends with Lecture 13 on June 3. Part II starts with Lecture 14 on June 9.
Organization
- Lecturer: Prof. Dr. Martin Hoefer
- Exercises: Marco Schmalhofer
- LSF Entries: Part 1, Part 2, Complete course
- Lectures: Tuesday and Wednesday, 14:15h - 15:45h, Video Recording
- Exercises: Friday, 10:15h - 11:45h, Live Video Session
Material
Lecture Notes
Last update on 2 Sep 2020. (restricted access)
Videos
Available here (restricted access)
Exercise Sheets
Part 1:- Exercise Sheet 1. Issued: 28.04.2020. Due: 05.05.2020, 14:15h.
- Exercise Sheet 2. Issued: 05.05.2020. Due: 12.05.2020, 14:15h.
- Exercise Sheet 3. Issued: 12.05.2020. Due: 19.05.2020, 14:15h.
- Exercise Sheet 4. Issued: 19.05.2020. Due: 26.05.2020, 14:15h.
- Exercise Sheet 5. Issued: 26.05.2020. Due: 02.06.2020, 14:15h.
- Exercise Sheet 6. Issued: 02.06.2020. Due: 09.06.2020, 14:15h.
Part 2:
- Exercise Sheet 7. Issued: 16.06.2020. Due: 23.06.2020, 14:15h.
- Exercise Sheet 8. Issued: 23.06.2020. Due: 30.06.2020, 14:15h.
- Exercise Sheet 9. Issued: 30.06.2020. Due: 07.07.2020, 14:15h.
- Exercise Sheet 10. Issued: 07.07.2020. Due: 14.07.2020, 14:15h.
Topic
The course gives an introduction to theoretical and algorithmic foundations of distributed systems that are composed of many processing units. For message passing models we discuss algorithms that solve broadcast, tree construction, coloring or independent set problems. We study basic networking problems like routing, contention resolution or congestion minimization. In addition, the course gives an introduction to the analysis of algorithms for wireless networks, population protocols and game-theoretic aspects of distributed systems.
Literature
- [P] Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000.
Free online access at Google Books. - [AW] Attiya, Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics. Wiley, 2004.
- [L] Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, 1992.