A Queueing Network-Based Distributed Laplacian Solver

We use queueing networks to present a new approach to solving Laplacian systems. Our distributed solver works for a large and important class of Laplacian systems that we call "one-sink" Laplacian systems, i.e., systems of the form Lx = b where exactly one of the coordinates of b is negative. Our solver is a distributed algorithm that takes ~O(thit dmax) time (where ~O hides poly log n factors) to produce an approximate solution where thit is the worst-case hitting time of the random walk on the graph, which is Θ(n) for a large set of important graphs, and dmax is the generalized maximum degree of the graph. The class of one-sink Laplacians includes the important voltage computation problem and allows us to compute the effective resistance between nodes in a distributed setting. As a result, our Laplacian solver can be used to adapt the approach by Kelner and Madry (2009) to give the first distributed algorithm to compute approximate random spanning trees efficiently.