Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts

DOI10.1007/S00446-023-00454-0MaRDI QIDQ6071121zbMATH OpenFDO

Authors Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, Themis Gouleakis

Publication date 21 November 2023

Published in Distributed Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2109.05151

zbMATH Keywords

distributed algorithmsLaplacian solverslow-congestion shortcutsuniversal optimality

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: In this paper, we refine the (almost) emph{existentially optimal} distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS `21) into an (almost) emph{universally optimal} distributed Laplacian solver. Specifically, when the topology is known, we show that any Laplacian system on an $n$-node graph with emph{shortcut quality} $extSQ(G)$ can be solved within $n^{o(1)}extSQ(G)log(1/varepsilon)$ rounds, where $varepsilon$ is the required accuracy. This almost matches our lower bound which guarantees that any correct algorithm on $G$ requires $widetildeOmega(extSQ(G))$ rounds, even for a crude solution with $varepsilonle1/2$. Even in the unknown-topology case (i.e., standard CONGEST), the same bounds also hold in most networks of interest. Furthermore, conditional on conjectured improvements in state-of-the-art constructions of low-congestion shortcuts, the CONGEST results will match the known-topology ones. Moreover, following a recent line of work in distributed algorithms, we consider a hybrid communication model which enhances CONGEST with limited global power in the form of the node-capacitated clique (NCC) model. In this model, we show the existence of a Laplacian solver with round complexity $n^{o(1)}log(1/varepsilon)$. The unifying thread of these results, and our main technical contribution, is the study of novel emph{congested} generalization of the standard emph{part-wise aggregation} problem. We develop near-optimal algorithms for this primitive in the Supported-CONGEST model, almost-optimal algorithms in (standard) CONGEST, as well as a very simple algorithm for bounded-treewidth graphs with slightly worse bounds. This primitive can be readily used to accelerate the FOCS`21 Laplacian solver. We believe this primitive will find further independent applications.

Recommendations

• Near-optimal low-congestion shortcuts on bounded parameter graphs
• A queueing network-based distributed Laplacian solver
• Low-congestion shortcuts without embedding
• Low-congestion shortcuts without embedding
• A queueing network-based distributed Laplacian solver for directed graphs

Cites work

• A Graph-Theoretic Game and Its Application to the k-Server Problem
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• An efficient parallel solver for SDD linear systems
• Approaching optimality for solving SDD linear systems
• Approximate undirected maximum flows in \(O(m\operatorname{polylog}(n))\) time
• Computing Shortest Paths and Diameter in the Hybrid Network Model
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
• Distributed Computing: A Locality-Sensitive Approach
• Distributed verification and hardness of distributed approximation
• Fully dynamic spectral vertex sparsifiers and applications
• scientific article; zbMATH DE number 5485569 (Why is no real title available?)
• Locality in Distributed Graph Algorithms
• Localization of electrical flows
• Low-congestion shortcuts without embedding
• Lx = b
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• Near-optimal distributed maximum flow (extended abstract)
• Near-optimal low-congestion shortcuts on bounded parameter graphs
• Near-optimal scheduling of distributed algorithms
• Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
• Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
• On the power of the congested clique model
• Shortest Paths in a Hybrid Network Model
• Simple distributed +1-coloring of graphs
• Sparsified Cholesky and multigrid solvers for connection Laplacians
• Stable distributions, pseudorandom generators, embeddings, and data stream computation
• Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
• Universally-optimal distributed algorithms for known topologies

Cited in

(1)

• Minimum cost flow in the CONGEST model

This page was built for publication: Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6071121)