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

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

doi:10.48550/arxiv.2504.21781

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 in the CONGEST model: • We give a message-optimal (up to logarithmic factors) algorithm that solves weighted APSP, using ˜𝑂 (𝑛2) messages. This algorithm takes ˜𝑂 (𝑛2) rounds. • For any 0 ≤ 𝜀 ≤ 1, we show how to solve unweighted APSP in ˜𝑂 (𝑛2−𝜀 ) rounds and ˜𝑂 (𝑛2+𝜀 ) messages. At one end of this smooth trade-off, we obtain a (nearly) message-optimal algorithm using ˜𝑂 (𝑛2) messages (for 𝜀 = 0), whereas at the other end we get a (nearly) round-optimal algorithm using ˜𝑂 (𝑛) rounds (for 𝜀 = 1). This is the first such message-time trade-off result known. Our first result is based on a simple, uniform simulation algorithm, that utilizes the Miller-Peng-Xu (MPX) graph decomposition [SPAA 2013], for designing message-efficient distributed algorithms. Our approach simulates any distributed algorithm with broadcast complexity 𝐵 in (essentially) ˜𝑂 (𝐵) message complexity. Note that the broadcast complexity of an algorithm is the number of broadcasts by all nodes over the entire execution, which can be significantly smaller than the algorithm’s message complexity. We then use our simulation technique to derive the first-known message-optimal distributed algorithms not only for weighted APSP, but also for Maximum Matching in bipartite graphs, and neighborhood cover construction. Our second result, which is our main technical contribution, is based on a new technique that allows us to simulate many Breadth First Search (BFS) algorithms in parallel in a way that allows us to control the maximum congestion of an edge and the dilation (i.e., maximum running time) of the algorithms. Our technique uses a modification the well-known hierarchical cluster decomposition of Baswana-Sen [RSA 2007] in a novel way. The main novelty is running the simulation on an ensemble of independently constructed cluster hierarchies. We believe that our technique can be useful in obtaining message-time tradeoffs for other problems

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

Files and links (1)

Abstract

Details

Metrics