Distributed Computing Computational Theory and Mathematics

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

Dory, Michal, Fischer, Orr, Khoury, Seri, Leitersdorf, Dean
Springer Nature · 2026-03-18 · DOI 10.1007/s00446-025-00503-w

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 \ge 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} \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 ^2{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 $${{\,\textrm{poly}\,}}(\log {k})$$ rounds [Parter, Yogev, DISC ’18] [Biswas, Dory, Ghaffari, Mitrovic, Nazari, SPAA ’21], and the fastest algorithms for approximate shortest paths require $${{\,\textrm{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.

Read at publisher →