Randomized Gossip Algorithms for Solving Laplacian Systems

Abstract—We consider the problem of solving a Lapla-cian system of equations Lx = b in a distributed fashion, where L is the Laplacian of the communication graph. Solv-ing Laplacian systems arises in a number of applications including consensus, distributed control, clock synchro-nization, localization and calculating effective resistances, to name a few. We leverage our analysis on a randomized variant of Kaczmarz’s algorithm to propose a distributed asynchronous gossip algorithm with expected exponential convergence. We quantify the convergence rate depending solely on properties of the network topology, and further propose an accelerated version that scales favorably for larger networks. Our approach naturally extends to least-squares estimation of general linear systems where each row/column is assigned to nodes of a given network. Last but not least, we show that average consensus is a special case in our framework