Constant-round spanners and shortest paths in congested clique and MPC

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(n1+1/k) edges in unweighted graphs, and O ( k )-spanners with O(n1+1/k log n) edges in weighted graphs. An O (1)-round algorithm for O(log n) -approximation for APSP in unweighted graphs. An O (1)-round algorithm for O(log ²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\,(log k) rounds [Parter, Yogev, DISC ’18] [Biswas, Dory, Ghaffari, Mitrovic, Nazari, SPAA ’21], and the fastest algorithms for approximate shortest paths require \,poly\,(log log 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.