Polylogarithmic-time deterministic network decomposition and distributed derandomization
Polylogarithmic-time deterministic network decomposition and distributed derandomization
复制标题
多对数时间确定性网络分解和分布式去随机化
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
M. Ghaffari
中科院分区：
文献类型：
--
作者：
Václav Rozhoň;M. Ghaffari
提出了一种简单的多步时间确定性分布式网络分解算法。这改进了著名的2 O（logn）-时间算法的Panconesi和Srinivasan [STOC'92]，并解决了一个中心和长期存在的问题，在分布式图算法。它还导致了许多其他问题的第一个多项式时间确定性分布式算法，从而解决了几个著名的和几十年前的开放问题，包括Linial关于最大独立集的确定性复杂性的问题[FOCS'87; SICOMP'92]-这被称为该领域最突出的问题。其主要含义是一个更一般的分布式去随机化定理：将Ghaffari，Kuhn和Maus [STOC'17]和Ghaffari，Harris和Kuhn [FOCS'18]的结果放在一起，我们的网络分解意味着P-Rth = P-Rth。也就是说，对于任何问题，其解决方案可以在多周期时间内确定性地检查，任何多周期时间随机算法可以去随机化为多周期时间确定性算法。非正式地，对于效率的标准一阶解释为多随机时间，分布式算法不需要随机性来提高效率。通过已知的连接，我们的结果也导致了许多研究得很好的问题，包括（Δ+1）-着色，极大独立集和Lovász局部引理，以及大规模并行算法（Δ+1）-着色的快速随机分布式算法。
We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated 2 O(√logn)-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 P-RLOCAL = P-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 (Δ+1)-coloring, maximal independent set, and Lovász Local Lemma, as well as massively parallel algorithms for (Δ+1)-coloring.
影响因子：
1.3
作者：
Kai-Min Chung;Seth Pettie;Hsin-Hao Su
通讯作者：
Kai-Min Chung;Seth Pettie;Hsin-Hao Su
局部模型的时间层次定理
影响因子：
1.6
作者：
Chang, Yi-Jun;Pettie, Seth
通讯作者：
Pettie, Seth