Accelerating Distributed Consensus Via Lifting Markov Chains

Existing works on distributed averaging explore linear iterations based on reversible Markov chains. The convergence of such algorithms is bounded to be slow due to the diffusive behavior of the reversible chains. It has been observed that certain nonreversible chains lifted from reversible ones mix substantially faster than the original chains. We show that the idea of nonreversible lifting lends itself naturally to a fast distributed averaging algorithm, where each node maintains multiple estimates, corresponding to multiple lifted states in the Markov chain. We give a rigorous proof that it is possible to achieve an e-averaging time of Theta(k log(1/isin)) on a k times k grid. For a general wireless network, we propose a Location-Aided Distributed Averaging (LADA) algorithm, which utilizes local information to construct a fast-mixing nonreversible chain in a distributed manner. We show that using LADA, an e-averaging time of Theta(r^-1 log(1/isin)) is achievable in a wireless network with transmission radius r.