News
Aktuell gibt es keine Neuigkeiten
Distributed Graph Algorithms
In this course, we will study the theory of distributed message-passing algorithms in computer networks, abstracted as graphs. Our focus will be on fundamental local graph problems, such as computing a vertex coloring or a maximal matching. How many rounds of (synchronous) computation between the vertices of the graph do we need to solve these problems (or, equivalently, how far do the vertices have to see in the graph)? We will design algorithms, analyze their (distributed) time complexity, and prove lower bounds. Starting with the very basics, we will gradually work our way towards more complex algorithms and results, including exciting developments at the frontier of current research. Note that this is a theory course, i.e., we will mathematically design and analyze algorithms and prove impossibility results, but won't implement them practically.
At the end of the course, the students will have a good overview of distributed algorithms for local graph problems. They will know the fundamental techniques for designing distributed algorithms and will be able to combine them to create more involved algorithms. They know how to analyze the time complexity of such algorithms and prove lower bounds that no algorithm can beat.
The course language is English. In particular, all material that will be graded (such as solutions to exercise or exam questions) has to be written in English.
Topics
If you want to know more about which topics we will cover in this course, here is a rough overview. Note that this outline might be subject to change.
- the LOCAL model and local complexity
- coloring directed paths and rooted trees
- coloring general graphs
- lower bounds for coloring
- solving problems on trees
- problems on power graphs and greedy problems
- maximal independent set and maximal matching
- randomized algorithms and shattering
- network decomposition and derandomization
- locally checkable problems
- distributed complexity theory
- sinkless orientation
- lower bounds via round elimination
Registration
Registration is open now!
Prerequisites
There are no formal prerequisites for this course, but a general interest in graph theory and designing/analyzing algorithms as well as a basic understanding of probabilities and algorithmic analysis (e.g., O-notation) will be helpful.
Lectures
There will be one lecture per week, taking place on Thursdays, 10:00 (c.t.) - 12:00. The first lecture is on April 18. The course will be fully in person (no online option). The lectures will take place in building E9 1 (CISPA), room 0.02 (to the right of the front entrance, ground floor). To allow for unconstrained interaction (and to increase attendance), there will be no recordings of the lectures. However, we will provide lecture notes.
Exercises
Accompanying the lectures, we will have one exercise sheet for (almost) each lecture, and a weekly tutorial on Thursdays, 16:00 (c.t.) - 18:00, in which we will have time to discuss the solutions to the exercises and potential questions from the lectures. [Update: For everyone who cannot make it to the exercise class, the responsible assistant will be there already at 15:30, so that you can discuss the exercises between 15:30 and 16:15.] The exercise sheet is released on the day of the lecture, then you have almost a week to solve the exercises, and the tutorial for the exercise sheet is on the subsequent Thursday. Solutions to the exercise questions, typeset with latex, can be submitted for the respective lecture until 10:00 in the morning of the day of the corresponding tutorial. You need to receive at least 50% of the available points (across all exercise sheets) to be admitted to the exam.
The tutorial will also take place in building E9 1 (CISPA), room 0.02. The first tutorial will be on April 25.
Exam
Your grade for the course is determined via an exam taking place on August 13, 9:30 - 12:30, in the lecture hall that you reach if you turn left after entering the building where the lectures are taking place (building E9 1 (CISPA), room 0.05). Note that this is 9:30 sharp, not c.t. We will also have a re-exam on September 3, 10:10 - 13:10 (same place, also sharp). Even if you pass the exam, you are allowed to participate in the re-exam to improve your grade.