v1_covered_da59b81a-48fa-4661-97d0-66d74517bcac.pdf (916.93 kB)

Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts

Download (916.93 kB)
journal contribution
posted on 2024-03-26, 09:05 authored by Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, Themis Gouleakis

 In this paper, we refine the (almost) existentially optimal distributed Laplacian solver of Forster, Goranci, Liu, Peng, Sun, and Ye (FOCS ‘21) into an (almost) universally optimal distributed Laplacian solver. Specifically, when the topology is known (i.e., the Supported-CONGEST model), we show that any Laplacian system on an n-node graph with shortcut quality SQ(G) can be solved after n ° (1)SQ(G)log⁡(1/€) rounds, where €>0 is the required accuracy. This almost matches our lower bound that guarantees that any correct algorithm on G requires Ω~(SQ(G)) rounds, even for a crude solution with € ≤1/2. Several important implications hold in the unknown-topology (i.e., standard CONGEST) case: for excluded-minor graphs we get an almost universally optimal algorithm that terminates in D⋅n ° (1)log⁡(1/€) rounds, where D is the hop-diameter of the network; as well as n ° (1)log⁡(1/€)-round algorithms for the case of SQ(G)≤n ° (1), which holds for most networks of interest. 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 model. In this model, we show the existence of a Laplacian solver with round complexity n ° (1)log⁡(1/€). The unifying thread of these results, and our main technical contribution, is the development of near-optimal algorithms for a novel p-congested generalization of the standard part-wise aggregation problem, which could be of independent interest. 


Primary Research Area

  • Algorithmic Foundations and Cryptography


Distributed Computing


Springer Nature

Open Access Type

  • Green

Sub Type

  • Article


@article{Anagnostides:Lenzen:Haeupler:Zuzic:Gouleakis:2023, title = "Almost Universally Optimal Distributed Laplacian Solvers via Low-Congestion Shortcuts", author = "Anagnostides, Ioannis" AND "Lenzen, Christoph" AND "Haeupler, Bernhard" AND "Zuzic, Goran" AND "Gouleakis, Themis", year = 2023, month = 7, journal = "Distributed Computing", publisher = "Springer Nature", issn = "0178-2770", doi = "10.21203/" }