Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization

被引:81
作者
Rozhon, Vaclav [1 ]
Ghaffari, Mohsen [1 ]
机构
[1] Swiss Fed Inst Technol, Zurich, Switzerland
来源
PROCEEDINGS OF THE 52ND ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '20) | 2020年
基金
欧洲研究理事会;
关键词
network decomposition; distributed algorithms; derandomization; PARALLEL ALGORITHM;
D O I
10.1145/3357713.3384298
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated 2(O(root log n))-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 polylogarithmictime 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 (Delta + 1)-coloring, maximal independent set, and Lovasz Local Lemma, as well as massively parallel algorithms for (Delta + 1)-coloring.
引用
收藏
页码:350 / 363
页数:14
相关论文
共 36 条
  • [1] A FAST AND SIMPLE RANDOMIZED PARALLEL ALGORITHM FOR THE MAXIMAL INDEPENDENT SET PROBLEM
    ALON, N
    BABAI, L
    ITAI, A
    [J]. JOURNAL OF ALGORITHMS, 1986, 7 (04) : 567 - 583
  • [2] NETWORK DECOMPOSITION AND LOCALITY IN DISTRIBUTED COMPUTATION
    AWERBUCH, B
    LUBY, M
    GOLDBERG, AV
    PLOTKIN, SA
    [J]. 30TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 1989, : 364 - 369
  • [3] Fast distributed network decompositions and covers
    Awerbuch, B
    Berger, B
    Cowen, L
    Peleg, D
    [J]. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1996, 39 (02) : 105 - 114
  • [4] Balliu Alkida, 2019, P FDN COMP SCI FOCS
  • [5] The Locality of Distributed Symmetry Breaking
    Barenboim, Leonid
    Elkin, Michael
    Pettie, Seth
    Schneider, Johannes
    [J]. JOURNAL OF THE ACM, 2016, 63 (03)
  • [6] Deterministic Distributed Vertex Coloring in Polylogarithmic Time
    Barenboim, Leonid
    Elkin, Michael
    [J]. JOURNAL OF THE ACM, 2011, 58 (05)
  • [7] Deterministic Distributed Vertex Coloring in Polylogarithmic Time
    Barenboim, Leonid
    Elkin, Michael
    [J]. PODC 2010: PROCEEDINGS OF THE 2010 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, 2010, : 410 - 419
  • [8] Distributed graph coloring: Fundamentals and recent developments
    Barenboim, Leonid
    Elkin, Michael
    [J]. Synthesis Lectures on Distributed Computing Theory, 2013, 4 (01): : 1 - 173
  • [9] Censor-Hillel Keren, 2017, 31 INT S DISTR COMP
  • [10] Chang Y.-J., 2018, P 50 ACM S THEOR COM