Deterministic Distributed Algorithms and Lower Bounds in the Hybrid\n Model

The $\\hybrid$ model was recently introduced by Augustine et al.\n\\cite{DBLP: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{\\mathcal{O}}(\\sqrt{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 + \\epsilon)$-\nand $\\log n/\\log \\log n$-approximate algorithms for unweighted and weighted\ngraphs respectively with round complexity $\\widetilde{\\mathcal{O}}(\\sqrt{n})$\nin $\\hybrid$, closely matching the performance of the state of the art\nrandomized algorithm of Kuhn and Schneider \\cite{10.1145/3382734.3405719}.\nMoreover, we make a connection with the Ghaffari-Haeupler framework of\nlow-congestion shortcuts \\cite{DBLP:conf/soda/GhaffariH16}, leading -- among\nothers -- to a $(1 + \\epsilon)$-approximate algorithm for Min-Cut after\n$\\log^{\\mathcal{O}(1)}n$ rounds, with high probability, even if we restrict\nlocal edges to transfer $\\mathcal{O}(\\log n)$-bits per round. Finally, we prove\nvia a reduction from the set disjointness problem that\n$\\widetilde{\\Omega}(n^{1/3})$ rounds are required to determine the radius of an\nunweighted graph, as well as a $(3/2 - \\epsilon)$-approximation for weighted\ngraphs.\n

Paper

Similar papers

© 2026 NYSGPT2525 LLC