EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Michal Dory, Orr Fischer, Seri Khoury, Dean Leitersdorf

Distributed Computing · 2026-06 · 39 (2)

DOI: 10.1007/s00446-025-00503-w ↗

Kurz gefasst

Fachartikel in der Zeitschrift Distributed Computing, online erschienen am 18.03.2026. Verfasst von Michal Dory und 3 weiteren Autor:innen. Die Arbeit nennt 61 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: University of Haifa.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • University of Haifa

Zitieren

APA

Dory, M., Fischer, O., Khoury, S., & Leitersdorf, D. (2026). Constant-round spanners and shortest paths in congested clique and MPC. Distributed Computing, 39(2). https://doi.org/10.1007/s00446-025-00503-w

Vancouver

Dory M, Fischer O, Khoury S, Leitersdorf D. Constant-round spanners and shortest paths in congested clique and MPC. Distributed Computing. 2026;39(2). doi:10.1007/s00446-025-00503-w

BibTeX
@article{Dory2026,
  author = {Dory, Michal and Fischer, Orr and Khoury, Seri and Leitersdorf, Dean},
  title = {Constant-round spanners and shortest paths in congested clique and MPC},
  journal = {Distributed Computing},
  year = {2026},
  volume = {39},
  number = {2},
  doi = {10.1007/s00446-025-00503-w}
}
Kostenlos starten →