Message Optimality and Message-Time Trade-offs for APSP and Beyond

Fabien Dufoulon; Shreyas Pai; Gopal Pandurangan; Sriram Pemmaraju; Peter Robinson

doi:10.1145/3732772.3733506

Back

Message Optimality and Message-Time Trade-offs for APSP and Beyond

Conference proceeding

Open access

Message Optimality and Message-Time Trade-offs for APSP and Beyond

Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan, Sriram Pemmaraju and Peter Robinson

Proceedings of the ACM Symposium on Principles of Distributed Computing, pp.299-309

ACM Conferences

PODC '25: ACM Symposium on Principles of Distributed Computing

06/16/2025

DOI: 10.1145/3732772.3733506

Files and links (1)

url

https://doi.org/10.1145/3732772.3733506View

Published (Version of record) Open Access

Abstract

Round complexity is an extensively studied metric of distributed algorithms. In contrast, our knowledge of the 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, All Pairs Shortest Path (APSP), whose message complexity is still unresolved. We present two main results: (1) An algorithm that solves weighted APSP, using Õ(n2) messages in Õ(n2) rounds. This algorithm is message-optimal (up to logarithmic factors) for algorithms that take poly(n) rounds. (2) For any 0 ≤ ϵ ≤ 1, we show how to solve unweighted APSP in Õ(n2–ϵ) rounds and Õ(n2+ϵ) messages. At one end of this smooth trade-off, we obtain a (nearly) message-optimal algorithm (for algorithms that take poly(n) rounds) using Õ(n2) messages (for ϵ = 0), whereas at the other end we get a (nearly) round-optimal algorithm using Õ(n) rounds (for ϵ = 1).

Theory of computation -- Design and analysis of algorithms -- Distributed algorithms

Details

Title: Subtitle: Message Optimality and Message-Time Trade-offs for APSP and Beyond
Creators: Fabien Dufoulon - Lancaster University
Shreyas Pai - Indian Institute of Technology Madras
Gopal Pandurangan - University of Houston
Sriram Pemmaraju - University of Iowa, Iowa City, Iowa, USA
Peter Robinson - Augusta University
Resource Type: Conference proceeding
Publication Details: Proceedings of the ACM Symposium on Principles of Distributed Computing, pp.299-309
Conference: PODC '25: ACM Symposium on Principles of Distributed Computing
Series: ACM Conferences
DOI: 10.1145/3732772.3733506
Publisher: ACM
Grant note: Army Research Office (ARO): W911NF-231-0191 National Science Foundation (NSF): CCF-2402836, CCF-2402837, CCF-2402835
Gopal Pandurangan was supported in part by Army Research Office (ARO) grant W911NF-231-0191 and National Science Foundation (NSF) grant CCF-2402837. Sriram V. Pemmaraju was supported in part by the National Science Foundation (NSF) grant CCF-2402835. Peter Robinson was supported in part by the National Science Foundation (NSF) grant CCF-2402836.
Language: English
Date published: 06/16/2025
Academic Unit: Computer Science
Record Identifier: 9984829022602771

Metrics

3 Record Views