Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model
| Autor: | Anagnostides, I., Gouleakis, T. |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Hybrid Model
FOS: Computer and information sciences Radius Computer Science - Distributed Parallel and Cluster Computing All-Pairs Shortest Paths TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Minimum Cut Sparse Graphs Distributed Parallel and Cluster Computing (cs.DC) Theory of computation → Distributed algorithms Distributed Computing Deterministic Algorithms MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | 35th International Symposium on Distributed Computing Leibniz International Proceedings in Informatics |
| DOI: | 10.48550/arxiv.2108.01740 |
| Popis: | The HYBRID model was recently introduced by Augustine et al. [John Augustine et al., 2020] in order to characterize from an algorithmic standpoint the capabilities of networks which combine multiple communication modes. Concretely, it is assumed that the standard LOCAL model of distributed computing is enhanced with the feature of all-to-all communication, but with very limited bandwidth, captured by the node-capacitated clique (NCC). In this work we provide several new insights on the power of hybrid networks for fundamental problems in distributed algorithms. First, we present a deterministic algorithm which solves any problem on a sparse n-node graph in 𝒪̃(√n) rounds of HYBRID, where the notation 𝒪̃(⋅) suppresses polylogarithmic factors of n. We combine this primitive with several sparsification techniques to obtain efficient distributed algorithms for general graphs. Most notably, for the all-pairs shortest paths problem we give deterministic (1 + ε)- and log n/log log n-approximate algorithms for unweighted and weighted graphs respectively with round complexity 𝒪̃(√n) in HYBRID, closely matching the performance of the state of the art randomized algorithm of Kuhn and Schneider [Kuhn and Schneider, 2020]. Moreover, we make a connection with the Ghaffari-Haeupler framework of low-congestion shortcuts [Mohsen Ghaffari and Bernhard Haeupler, 2016], leading - among others - to a (1 + ε)-approximate algorithm for Min-Cut after 𝒪(polylog (n)) rounds, with high probability, even if we restrict local edges to transfer 𝒪(log n) bits per round. Finally, we prove via a reduction from the set disjointness problem that Ω̃(n^{1/3}) rounds are required to determine the radius of an unweighted graph, as well as a (3/2 - ε)-approximation for weighted graphs. As a byproduct, we show an Ω̃(n) round-complexity lower bound for computing a (4/3 - ε)-approximation of the radius in the broadcast variant of the congested clique, even for unweighted graphs. LIPIcs, Vol. 209, 35th International Symposium on Distributed Computing (DISC 2021), pages 5:1-5:19 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|