论文标题
改进的确定性网络分解
Improved Deterministic Network Decomposition
论文作者
论文摘要
网络分解是分布式图算法的中心工具。我们对网络分解的最新技术进行了两个改进，从而改善了几个经过良好研究的图形问题的（确定性和随机）复杂性。 - 使用$ O（\ log n）$ - 位消息，我们提供了$ O（\ log^5 n）$ round复杂性的确定性分布式网络分解算法。这改善了Rozhoň和Ghaffari [stoc'20]的$ O（\ log^7 n）$ - 圆形算法，该算法使用大消息，以及其$ O（\ log^8 n）$ - 圆形算法，带有$ o（\ log log n）$ - bit messages。这直接导致了广泛的确定性和随机分布式算法的类似改进，这些算法的解决方案依赖于网络分解，包括Ghaffari，Kuhn和Harris的一般分布式降低[focs'18]。 - Rozhoň和Ghaffari算法的一个缺点，在$ \ Mathsf {colesest} $模型中，其依赖于标识符的长度。因此，例如，在$ \ mathsf {colesest} $模型中的破碎框架中无法使用该算法。因此，该模型中几个问题随机复杂性的最新状态保留在添加$ 2^{o（\ sqrt {\ log \ log n}）} $项中，这是旧网络分解复杂性的明显剩余[Panconesi和srinivasan stoc'92]。我们提出了一个修改版本，该版本对此进行了纠正，构建了一个分解，其质量不取决于标识符，从而改善了各种问题的随机圆形复杂性。
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ň 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ň and Ghaffari, in the $\mathsf{CONGEST}$ 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{CONGEST}$ 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.
