Deterministic Distributed Algorithms and Lower Bounds in the Hybrid Model
share
The model was recently introduced by Augustine et al. <cit.> in order to characterize from an algorithmic standpoint the capabilities of networks which combine multiple communication modes. Concretely, it is assumed that the standard 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 (). 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 . 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/loglog n-approximate algorithms for unweighted and weighted graphs respectively with round complexity 𝒪(√(n)) in , closely matching the performance of the state of the art randomized algorithm of Kuhn and Schneider <cit.>. Moreover, we make a connection with the Ghaffari-Haeupler framework of low-congestion shortcuts <cit.>, leading – among others – to a (1 + ϵ)-approximate algorithm for Min-Cut after log^𝒪(1)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.
READ FULL TEXT