Network Decomposition and Distributed Derandomization (Invited Paper)

We overview a recent line of work [Rozhoň and Ghaffari at STOC 2020; Ghaffari, Harris, and Kuhn at FOCS 2018; and Ghaffari, Kuhn, and Maus at STOC 2017], which proved that any (locally-checkable) graph problem that admits an efficient randomized distributed algorithm also admits an efficient deterministic distributed algorithm, thereby resolving several central and decades-old open problems in distributed graph algorithms. We present a short and self-contained version of the proofs, and conclude by discussing several related questions that remain open. This article accompanies a keynote talk of the author at the International Colloquium on Structural Information and Communication Complexity (SIROCCO) 2020. The writing is based on [24, 28, 45] and primarily targets non-experts.ISSN:0302-9743ISSN:1611-334