Distributed Graph Algorithms

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! This course cannot accomodate more than 100 students. Technically, the slots will be handed out on a first-come-first-serve basis, but we expect the number of slots to be sufficient for everyone interested.

 

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 Mondays, 10:00 (c.t.) - 12:00. The first lecture is on April 17. The course will be fully in person (no online option). The lectures will take place in building E9 1 (CISPA), room 0.05 (lecture hall 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 Mondays, 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. The exercise sheet is released here 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 Monday. Solutions to the exercise questions, typeset with latex, can be submitted via email to the responsible assistant 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 take place in building E9 1 (CISPA), room 0.02 (ground floor). The first tutorial will be on April 24.

 

Exam

Your grade for the course is determined via an exam taking place on July 25, 9:00 - 12:00, in the usual lecture hall (building E9 1 (CISPA), room 0.05). Note that this is 9:00 sharp, not c.t. We will also have a re-exam on September 12, 9:00 - 12:00 (same place). Even if you pass the exam, you are allowed to participate in the re-exam to improve your grade.

 

Mattermost

As a forum for communication and discussion, we will use a Mattermost instance. You can sign up via the link provided in the materials tab (for registered students only).

 

Resources

A list of resources (books, lecture notes from other courses) is available here. Regarding the mentioned books (and their availability), please see also the literature page provided by the campus library for computer science and mathematics.