Theory of Distributed Systems 1+2 (Winter 2021/22)
Topical
- Logbook with detailed information about schedule and content.
- Lectures are provided as video recordings by studiumdigitale.
- Part I ends with Lecture 13. Part II starts with Lecture 14.
Organization
- Lecturer: Prof. Dr. Martin Hoefer
- Exercises: Dr. Giovanna Varricchio, Marco Schmalhofer
- LSF Entries: Part 1, Part 2, Complete course
- Lecture videos published Mon/Tue every week
- Exercises: Friday, 10:00h - 12:00h, Zoom
Material
Access to course material is restricted to participating students.
Lecture Notes
Last update on 01 Mar 2022
Videos
Lectures 1,...,9 here (access via HRZ mediasite)
Lectures 10,...,25 here (recorded in summer 2020)
Exercise Sheets
Part 1:- Exercise Sheet 1. Issued: 26.10.2021. Due: 02.11.2021, 08:15h.
- Exercise Sheet 2. Issued: 02.11.2021. Due: 09.11.2021, 08:15h.
- Exercise Sheet 3. Issued: 09.11.2021. Due: 16.11.2021, 08:15h.
- Exercise Sheet 4. Issued: 16.11.2021. Due: 23.11.2021, 08:15h.
- Exercise Sheet 5. Issued: 23.11.2021. Due: 30.11.2021, 08:15h.
- Exercise Sheet 6. Issued: 30.11.2021. Due: 07.12.2021, 08:15h.
Part 2:
- Exercise Sheet 7. Issued: 07.12.2021. Due: 14.12.2021, 08:15h.
- Exercise Sheet 8. Issued: 14.12.2021. Due: 18.01.2022, 08:15h.
- Exercise Sheet 9. Issued: 18.01.2022. Due: 25.01.2022, 08:15h.
- Exercise Sheet 10. Issued: 25.01.2022. Due: 01.02.2022, 08:15h.
- Exercise Sheet 11. Issued: 01.02.2022. Due: 08.02.2022, 08: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.