Message Optimality and Message-Time Trade-offs for APSP and Beyond
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912355258990592 |
|---|---|
| author | Dufoulon, Fabien Pai, Shreyas Pandurangan, Gopal Pemmaraju, Sriram Robinson, Peter |
| author_facet | Dufoulon, Fabien Pai, Shreyas Pandurangan, Gopal Pemmaraju, Sriram Robinson, Peter |
| contents | Round complexity is an extensively studied metric of distributed algorithms. In contrast, our knowledge of the \emph{message complexity} of distributed computing problems and its relationship (if any) with round complexity is still quite limited. To illustrate, for many fundamental distributed graph optimization problems such as (exact) diameter computation, All-Pairs Shortest Paths (APSP), Maximum Matching etc., while (near) round-optimal algorithms are known, message-optimal algorithms are hitherto unknown. More importantly, the existing round-optimal algorithms are not message-optimal. This raises two important questions: (1) Can we design message-optimal algorithms for these problems? (2) Can we give message-time tradeoffs for these problems in case the message-optimal algorithms are not round-optimal?
In this work, we focus on a fundamental graph optimization problem, \emph{All Pairs Shortest Path (APSP)}, whose message complexity is still unresolved. We present two main results in the CONGEST model: (1) We give a message-optimal (up to logarithmic factors) algorithm that solves weighted APSP, using $\tilde{O}(n^2)$ messages. This algorithm takes $\tilde{O}(n^2)$ rounds. (2) For any $0 \leq \varepsilon \le 1$, we show how to solve unweighted APSP in $\tilde{O}(n^{2-\varepsilon })$ rounds and $\tilde{O}(n^{2+\varepsilon })$ messages. At one end of this smooth trade-off, we obtain a (nearly) message-optimal algorithm using $\tilde{O}(n^2)$ messages (for $\varepsilon = 0$), whereas at the other end we get a (nearly) round-optimal algorithm using $\tilde{O}(n)$ rounds (for $\varepsilon = 1$). This is the first such message-time trade-off result known. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_21781 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Message Optimality and Message-Time Trade-offs for APSP and Beyond Dufoulon, Fabien Pai, Shreyas Pandurangan, Gopal Pemmaraju, Sriram Robinson, Peter Distributed, Parallel, and Cluster Computing Data Structures and Algorithms Round complexity is an extensively studied metric of distributed algorithms. In contrast, our knowledge of the \emph{message complexity} of distributed computing problems and its relationship (if any) with round complexity is still quite limited. To illustrate, for many fundamental distributed graph optimization problems such as (exact) diameter computation, All-Pairs Shortest Paths (APSP), Maximum Matching etc., while (near) round-optimal algorithms are known, message-optimal algorithms are hitherto unknown. More importantly, the existing round-optimal algorithms are not message-optimal. This raises two important questions: (1) Can we design message-optimal algorithms for these problems? (2) Can we give message-time tradeoffs for these problems in case the message-optimal algorithms are not round-optimal? In this work, we focus on a fundamental graph optimization problem, \emph{All Pairs Shortest Path (APSP)}, whose message complexity is still unresolved. We present two main results in the CONGEST model: (1) We give a message-optimal (up to logarithmic factors) algorithm that solves weighted APSP, using $\tilde{O}(n^2)$ messages. This algorithm takes $\tilde{O}(n^2)$ rounds. (2) For any $0 \leq \varepsilon \le 1$, we show how to solve unweighted APSP in $\tilde{O}(n^{2-\varepsilon })$ rounds and $\tilde{O}(n^{2+\varepsilon })$ messages. At one end of this smooth trade-off, we obtain a (nearly) message-optimal algorithm using $\tilde{O}(n^2)$ messages (for $\varepsilon = 0$), whereas at the other end we get a (nearly) round-optimal algorithm using $\tilde{O}(n)$ rounds (for $\varepsilon = 1$). This is the first such message-time trade-off result known. |
| title | Message Optimality and Message-Time Trade-offs for APSP and Beyond |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.21781 |