Network decomposition: Introduction

This post is an introduction (and a table of contents) for a series of posts on distributed network decomposition.

One of the most important papers of these recent years in distributed graph algorithms will appear at STOC this summer:

“Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization” by Václav Rozhoň and Mohsen Ghaffari from ETH Zurich.

It is basically the description of a distributed algorithm that performs what is called a network decomposition, faster than before. This decomposition can then be used to do many other things fast, and the paper solves several important open problems of the field.

I quickly looked at the paper when it appeared on arxiv, but I want to understand it better, and writing a series of posts about it is good way to do this.

Here is the my current plan for this series:

1. Local algorithms, an introduction to local algorithms, with the example of the maximal independent set problem.
2. Impact for distributed algorithms, that is, why is a network decomposition so useful.
3. Centralized construction, how to build a network decomposition with good parameters in a centralized manner.
4. Weak and strong decomposition, some useful precisions about the decomposition
5. The algorithm of Ghaffari and Rozhon.

[Many thanks to Fabien Dufoulon and Yannic Maus for their helpful comments.]