Distributed Graph Algorithms Sebastian Brandt

News

Currently, no news are available
 

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. We will cover a fresh topic every week. 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.



Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators