Distributed Graph Algorithms
Graduate Course - Winter Term 2025/26
Fabian Kuhn
Course Description
Many of today's computing systems are inherently distributed. Some systems operate over large networks that possibly span large distances. And even if systems are built in one physical location, often the data is so large that it data and computation has to be spread over several servers. The goal of this course is to learn the fundamentals of designing and analyzing distributed algorithms in the context of graph algorithms. The course covers the basic abstract models to study graph algorithms in the context of networks and modern large-scale parallel systems, algorithmic tools to efficiently solve graph problems in those abstract models, and also techniques to prove lower bounds in the context of distributed graph algorithms. Some of the topics covered in the class are:
- the standard models to study distributed graph algorithms (LOCAL and CONGEST)
- the MPC (massively parallel computation) model, which is used to model large-scale parallel cluster computations
- distributed algorithms to efficiently solve local problems (e.g., graph coloring, maximal independents sets)
- distributed algorithms to efficiently solve global problems (e.g., minimum spanning tree, shortest paths)
- methods for derandomizing distributed graph algorithms
- lower bound techniques
Schedule
Lectures: Mondays, 14:15 - 16:00, room 101-00-010/14
Exercise Tutorials: Fridays, 14:15 - 16:00, room 101-00-017/19
Exercises: There will be an exercise sheet every week which you should work on at home. Doing and handing in the exercises is not mandatory, but it is highly recommened. It is OK to work on and hand in exercise sheets in groups. The exercises will be published at the latest on Friday and they are due on the Friday one week later.
Scribe Notes: In order to obtain the "Studienleistung" for the course, every student has to write the lecture notes for one of the lectures. More details on this will be provided.
Lecture Material
We provide recordings and the written notes of the Monday lectures.
Important note: The recordings can only be accessed from within the university network. This can be done by establishing a VPN tunnel to the university network.
Exam Information
There will be a 30-minute oral exam at the end of the semesterForum
Instant Messenger: We will offer an instant messaging platform (Zulip) for all students to discuss all topics related to this lecture, where you are free to discuss among yourself or pose questions to us. Please consider the section below on technical information.
Exercises
Format: All submissions must be in, or converted to pdf format and be written in English. We strongly recommend to prepare your solutions with Latex for best readability (being able to work with latex is a good skill to have anyway). Solutions prepared with Word or similar text editors are ok. Scans or photos of handwritten solutions in pdf format are ok as well, but must be well readable!
Submission:Information on how to submit exercise solutions will be provided here soon.
Responsible for the exercises are Gustav Schmid and Zahra Parsaeian.
| Exercise sheet | Assigned | Due (2 pm) | Solution | |
| Exercise 01 (Basic Coloring and MIS) | 17.10. | 24.10. | Solution 01 (tba) | |