Abstract
We study the broadcast version of the CONGESTCLIQUE model of distributed computing. This model operates in synchronized rounds; in each round, any node in a network of size n can send the same message (i.e. broadcast a message) of limited size to every other node in the network. Nanongkai presented in [STOC'14] a randomized (2+o(1))approximation algorithm to compute all pairs shortest paths (APSP) in time ~{O}(sqrt{n}) on weighted graphs. We complement this result by proving that any randomized (2o(1))approximation of APSP and (2o(1))approximation of the diameter of a graph takes ~Omega(n) time in the worst case. This demonstrates that getting a negligible improvement in the approximation factor requires significantly more time. Furthermore this bound implies that already computing a (2o(1))approximation of all pairs shortest paths is among the hardest graphproblems in the broadcastversion of the CONGESTCLIQUE model, as any graphproblem where each node receives a linear amount of input can be solved trivially in linear time in this model. This contrasts a recent (1+o(1))approximation for APSP that runs in time O(n^{0.15715}) and an exact algorithm for APSP that runs in time ~O(n^{1/3}) in the unicast version of the CONGESTCLIQUE model, a more powerful variant of the broadcast version.
This lower bound in the broadcast CONGESTCLIQUE model is derived by first establishing a new lower bound for (2o(1))approximating the diameter in weighted graphs in the CONGEST model, which is of independent interest. This lower bound is then transferred to the CONGESTCLIQUE model.
On the positive side we provide a deterministic version of Nanongkai's (2+o(1))approximation algorithm for APSP. To do so we present a fast deterministic construction of small hitting sets. We also show how to replace another randomized part within Nanongkai's algorithm with a deterministic sourcedetection algorithm designed for the CONGEST model.
BibTeX  Entry
@InProceedings{holzer_et_al:LIPIcs:2016:6597,
author = {Stephan Holzer and Nathan Pinsker},
title = {{Approximation of Distances and Shortest Paths in the Broadcast Congest Clique}},
booktitle = {19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
pages = {116},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897989},
ISSN = {18688969},
year = {2016},
volume = {46},
editor = {Emmanuelle Anceaume and Christian Cachin and Maria PotopButucaru},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6597},
URN = {urn:nbn:de:0030drops65971},
doi = {10.4230/LIPIcs.OPODIS.2015.6},
annote = {Keywords: distributed computing, distributed algorithms, approximation algorithms}
}
Keywords: 

distributed computing, distributed algorithms, approximation algorithms 
Collection: 

19th International Conference on Principles of Distributed Systems (OPODIS 2015) 
Issue Date: 

2016 
Date of publication: 

13.10.2016 