Aktuelle Themen der Theoretischen Informatik:
Theory of Distributed Systems 1+2 (Winter 2018/19)
Topical
- For detailed information about schedule and covered material, see the logbook.
Organization
- Lecturer: Prof. Dr. Martin Hoefer
- Exercises: Niklas Hahn
- LSF Entries: Part 1, Part 2, Complete course
- Lectures:
Tuesday, 14:15h - 15:45h, Magnus-Hörsaal (R.M.S. 11-15)
Wednesday, 14:15h - 15:45h, Hörsaal H11, Hörsaalgebäude - Exercises: Friday, 10:15h - 11:45h, Hörsaal H11, Hörsaalgebäude
Material
Lecture Notes
Updated on 04 Mar 2019. (restricted access)
Exercise Sheets
Part 1:- Exercise Sheet 1. Issued: 23.10.2018. Due: 30.10.2018, 14:15h.
- Exercise Sheet 2. Issued: 30.10.2018. Due: 06.11.2018, 14:15h.
- Exercise Sheet 3. Issued: 06.11.2018. Due: 13.11.2018, 14:15h.
- Exercise Sheet 4. Issued: 13.11.2018. Due: 20.11.2018, 14:15h.
- Exercise Sheet 5. Issued: 20.11.2018. Due: 27.11.2018, 14:15h.
Part 2:
- Exercise Sheet 6. Issued: 04.12.2018. Due: 11.12.2018, 14:15h.
- Exercise Sheet 7. Issued: 11.12.2018. Due: 18.12.2018, 14:15h.
- Exercise Sheet 8. Issued: 18.12.2018. Due: 22.01.2019, 14:15h.
- Exercise Sheet 9. Issued: 22.01.2019. Due: 29.01.2019, 14:15h.
- Exercise Sheet 10. Issued: 29.01.2019. Due: 05.02.2019, 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.