Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
share
We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated 2^O(√(log n))-time algorithm of Panconesi and Srinivasan [STOC'93] and settles one of the long-standing and central questions in distributed graph algorithms. It also leads to the first polylogarithmic-time deterministic distributed algorithms for numerous other graph problems, hence resolving several open problems, including Linial's well-known question about the deterministic complexity of maximal independent set [FOCS'87]. Put together with the results of Ghaffari, Kuhn, and Maus [STOC'17] and Ghaffari, Harris, and Kuhn [FOCS'18], we get a general distributed derandomization result that implies P-RLOCAL = P-LOCAL. That is, for any distributed problem whose solution can be checked in polylogarithmic-time, any polylogarithmic-time randomized algorithm can be derandomized to a polylogarithmic-time deterministic algorithm. By known connections, our result leads also to substantially faster randomized algorithms for a number of fundamental problems including (Δ+1)-coloring, MIS, and Lovász Local Lemma.
READ FULL TEXT