Distributed Graph Algorithms Sebastian Brandt

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.

 

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

More details to follow.

 

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

More details to follow.

 

Exercises

More details to follow.

 

Exam

More details to follow.

 

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.