Abstract In this work we present the first constant-round algorithms for computing spanners and approximate All-Pairs Shortest Paths (APSP) in the distributed Congested Clique model. Specifically, we show the following results for undirected n -node graphs. For every integer k 1, O (1) -round algorithms for constructing O (k) -spanners with O (n^1+1/k) edges in unweighted graphs, and O (k) -spanners with O (n^1+1/k n) edges in weighted graphs. An O (1) -round algorithm for O (n) -approximation for APSP in unweighted graphs. An O (1) -round algorithm for O (²n) -approximation for APSP in weighted graphs. All our algorithms are randomized and succeed with high probability. Prior to our work, the fastest algorithms for computing O (k) -spanners in this model require {\, poly\, } (k) rounds Parter, Yogev, DISC ’18 Biswas, Dory, Ghaffari, Mitrovic, Nazari, SPAA ’21, and the fastest algorithms for approximate shortest paths require {\, poly\, } ({n}) rounds Dory, Parter, PODC ’20. Our results extend to the closely related massively parallel computation (MPC) model with near-linear memory per machine, leading to the first O (1) -round algorithms for spanners and approximate shortest paths in this model as well.
Dory et al. (Wed,) studied this question.