Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
From MaRDI portal
Abstract: We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated -time algorithm of Panconesi and Srinivasan [STOC'92] and settles a central and long-standing question in distributed graph algorithms. It also leads to the first polylogarithmic-time deterministic distributed algorithms for numerous other problems, hence resolving several well-known and decades-old open problems, including Linial's question about the deterministic complexity of maximal independent set [FOCS'87; SICOMP'92]---which had been called the most outstanding problem in the area. The main implication is a more general distributed derandomization theorem: Put together with the results of Ghaffari, Kuhn, and Maus [STOC'17] and Ghaffari, Harris, and Kuhn [FOCS'18], our network decomposition implies that mathsf{P} extit{-}mathsf{RLOCAL} = mathsf{P} extit{-}mathsf{LOCAL}. That is, for any problem whose solution can be checked deterministically in polylogarithmic-time, any polylogarithmic-time randomized algorithm can be derandomized to a polylogarithmic-time deterministic algorithm. Informally, for the standard first-order interpretation of efficiency as polylogarithmic-time, distributed algorithms do not need randomness for efficiency. By known connections, our result leads also to substantially faster randomized distributed algorithms for a number of well-studied problems including -coloring, maximal independent set, and Lov'{a}sz Local Lemma, as well as massively parallel algorithms for -coloring.
This page was built for publication: Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6322676)
