6.S899 Distributed Graph Algorithms


Graduate H-level
Units: 2-0-4
Prerequisites: Basic algorithms (6.046), Basic probability (6.042 or 6.041)
Instructors:  Mohsen Ghaffari, PhD student (ghaffari@mit.edu), Dr. Stephan Holzer (holzer@mit.edu), Prof. Nancy Lynch (lynch@csail.mit.edu)
Schedule:  F11-12:30, Room 4-145
This will be a short (12 lecture) graduate course designed to familiarize students with the fundamentals of distributed algorithms for solving graph problems.  The course will be technique-oriented and will cover most of the basic techniques used in the area.
The course will be divided into two parts. The first part will focus on the issue of “locality” in graph problems.  We will study local “symmetry-breaking” problems such as graph coloring and constructing a maximal independent set.  We will then cover a number of “network decomposition” techniques that are central tools in the study of locality in graph problems.  
In the second part of the course, we study problems that are “non-local” by nature. This means that, while solving these graph problems, any node needs to (implicitly or explicitly) learn some information that is far away. In this part, the main challenges are due to communication aspects, particularly the fact that message sizes are limited to some small bound. We will review a number of recent (near-optimal) distributed algorithms for problems such as minimum spanning tree, shortest paths, and distance approximation. We will then explain techniques for using communication complexity to prove lower bounds for exact and approximate distributed algorithms. Finally, we will study more general tools such as graph spanners and metric embeddings.