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 no(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 · no(1) log(1/ε) rounds, where D is the hop-diameter of the network; as well as no(1) log (1/ε)-round algorithms for the case of SQ(G) ≤ no(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 (NCC) model. In this model, we show the existence of a Laplacian solver with round complexity no(1) log(1/ε). The unifying thread of these results, and our main technical contribution, is the development of near-optimal algorithms for a novel ρ-congested generalization of the standard part-wise aggregation problem, which could be of independent interest.
2023-07-31
2024-10-08