(2022) Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts.
|
Text
2109.05151.pdf Download (1MB) | Preview |
Abstract
In this paper, we refine the (almost) existentially optimal distributed Laplacian solver recently developed by Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS `21) into an (almost) universally optimal distributed Laplacian solver. Specifically, when the topology is known, we show that any Laplacian system on an n-node graph with shortcut quality SQ(G) can be solved within n^(o(1))SQ(G)log(1/ε) rounds, where ε is the required accuracy. This almost matches our lower bound which guarantees that any correct algorithm on G requires Ω˜(SQ(G)) rounds, even for a crude solution with ε≤1/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/ε). The unifying thread of these results, and our main technical contribution, is the study of novel congested generalization of the standard 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.
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Christoph Lenzen (CL) |
| Conference: | DISC International Symposium on Distributed Computing (was WDAG) |
| Depositing User: | Christoph Lenzen |
| Date Deposited: | 13 Oct 2022 07:54 |
| Last Modified: | 13 Oct 2022 07:54 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3824 |
Actions
Actions (login required)
 |
View Item |