# Network decomposition: Introduction

08 Apr 2020This 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:

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

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