  We study the broadcast version of the CONGEST CLIQUE model of distributed
computing. In this model, 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 $\tilde{O}(\sqrt{n})$ on weighted graphs, where we use the convention
that $\tilde{\Omega}(f(n))$ is essentially $\Omega(f(n)/$polylog$f(n))$ and
$\tilde{O}(f(n))$ is essentially $O(f(n) $polylog$f(n))$. We complement this
result by proving that any randomized $(2-o(1))$-approximation of APSP and
$(2-o(1))$-approximation of the diameter of a graph takes $\tilde\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 $(2-o(1))$-approximation of all pairs
shortest paths is among the hardest graph-problems in the broadcast-version of
the CONGEST CLIQUE model and contrasts a recent $(1+o(1))$-approximation for
APSP that runs in time $O(n^{0.15715})$ in the unicast version of the CONGEST
CLIQUE 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 source-detection algorithm designed for the CONGEST model
presented by Lenzen and Peleg at PODC'13.
