Improved Deterministic Network Decomposition

Network decomposition is a central tool in distributed graph algorithms. We present two improvements on the state of the art for network decomposition, which thus lead to improvements in the (deterministic and randomized) complexity of several well-studied graph problems.

• We provide a deterministic distributed network decomposition algorithm with $O({\log }^{5}n)$ round complexity, using $O(\log n)$-bit messages. This improves on the $O({\log }^{7}n)$-round algorithm of Rozho\v{n} and Ghaffari [STOC’20], which used large messages, and their $O({\log }^{8}n)$-round algorithm with $O(\log n)$-bit messages. This directly leads to similar improvements for a wide range of deterministic and randomized distributed algorithms, whose solution relies on network decomposition, including the general distributed derandomization of Ghaffari, Kuhn, and Harris [FOCS’18].
• One drawback of the algorithm of Rozho\v{n} and Ghaffari, in the $\mathsf{C}\mathsf{O}\mathsf{N}\mathsf{G}\mathsf{E}\mathsf{S}\mathsf{T}$ model, was its dependence on the length of the identifiers. Because of this, for instance, the algorithm could not be used in the shattering framework in the $\mathsf{C}\mathsf{O}\mathsf{N}\mathsf{G}\mathsf{E}\mathsf{S}\mathsf{T}$ model. Thus, the state of the art randomized complexity of several problems in this model remained with an additive $2^{O(\sqrt{\log \log n})}$ term, which was a clear leftover of the older network decomposition complexity [Panconesi and Srinivasan STOC’92]. We present a modified version that remedies this, constructing a decomposition whose quality does not depend on the identifiers, and thus improves the randomized round complexity for various problems.