License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2021.5
URN: urn:nbn:de:0030-drops-148077
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14807/
Anagnostides, Ioannis ;
Gouleakis, Themis
Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model
Abstract
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.
BibTeX - Entry
@InProceedings{anagnostides_et_al:LIPIcs.DISC.2021.5,
author = {Anagnostides, Ioannis and Gouleakis, Themis},
title = {{Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model}},
booktitle = {35th International Symposium on Distributed Computing (DISC 2021)},
pages = {5:1--5:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-210-5},
ISSN = {1868-8969},
year = {2021},
volume = {209},
editor = {Gilbert, Seth},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14807},
URN = {urn:nbn:de:0030-drops-148077},
doi = {10.4230/LIPIcs.DISC.2021.5},
annote = {Keywords: Distributed Computing, Hybrid Model, Sparse Graphs, Deterministic Algorithms, All-Pairs Shortest Paths, Minimum Cut, Radius}
}
|
Keywords: |
|
Distributed Computing, Hybrid Model, Sparse Graphs, Deterministic Algorithms, All-Pairs Shortest Paths, Minimum Cut, Radius |
|
Collection: |
|
35th International Symposium on Distributed Computing (DISC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.10.2021 |
