Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Žužić, Themis Gouleakis · Distributed Computing · 2023
Abstract 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 $$\textrm{SQ}(G)$$ SQ ( G ) can be solved after $$n^{o(1)} \text {SQ}(G) \log (1/\epsilon )$$ n o ( 1 ) SQ ( G ) log ( 1 / ϵ ) rounds, where $$\epsilon >0$$ ϵ > 0 is the required accuracy. This almost matches our lower bound that guarantees that any correct algorithm on G requires $$\widetilde{\Omega }(\textrm{SQ}(G))$$ Ω ~ ( SQ ( G ) ) rounds, even for a crude solution with $$\epsilon \le 1/2$$ ϵ ≤ 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 \cdot n^{o(1)} \log (1/\epsilon )$$ D · n o ( 1 ) log ( 1 / ϵ ) rounds, where D is the hop-diameter of the network; as well as $$n^{o(1)} \log (1/\epsilon )$$ n o ( 1 ) log ( 1 / ϵ ) -round algorithms for the case of $$\textrm{SQ}(G) \le n^{o(1)}$$ SQ ( G ) ≤ n o ( 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 cli