2021/08/03 by Ioannis Anagnostides, Anagnostides, Ioannis, Themis Gouleakis +1
Computer Science · #Complexity and Algorithms in Graphs #Distributed #FOS: Computer and information sciences #Parallel #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2108.01740
openalex publication_date 2021/08/03 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
The hybrid model was recently introduced by Augustine et al.\n citeDBLP:conf/soda/AugustineHKSS20 in order to characterize from an\nalgorithmic standpoint the capabilities of networks which combine multiple\ncommunication modes. Concretely, it is assumed that the standard local model\nof distributed computing is enhanced with the feature of all-to-all\ncommunication, but with very limited bandwidth, captured by the\nnode-capacitated clique ( ncc). In this work we provide several new insights\non the power of hybrid networks for fundamental problems in distributed\nalgorithms.\n First, we present a deterministic algorithm which solves any problem on a\nsparse n-node graph in widetilde\O(\√(n)) rounds of\n hybrid. We combine this primitive with several sparsification techniques to\nobtain efficient distributed algorithms for general graphs. Most notably, for\nthe all-pairs shortest paths problem we give deterministic (1 + \ε)-\nand \log n/\log \log n-approximate algorithms for unweighted and weighted\ngraphs respectively with round complexity widetilde\O(\√(n))\nin hybrid, closely matching the performance of the state of the art\nrandomized algorithm of Kuhn and Schneider cite10.1145/3382734.3405719.\nMoreover, we make a connection with the Ghaffari-Haeupler framework of\nlow-congestion shortcuts citeDBLP:conf/soda/GhaffariH16, leading -- among\nothers -- to a (1 + \ε)-approximate algorithm for Min-Cut after\n\log\O(1)n rounds, with high probability, even if we restrict\nlocal edges to transfer \O(\log n)-bits per round. Finally, we prove\nvia a reduction from the set disjointness problem that\n widetilde\Ω(n1/3) rounds are required to determine the radius of an\nunweighted graph, as well as a (3/2 - \ε)-approximation for weighted\ngraphs.\n