LADA Algorithms: Performance Lower Bound and Cluster-Based Variant

The observation that certain non-reversible chains lifted from reversible ones mix substantially faster than the original chains, has motivated the authors' recent work, where a Location-Aided Distributed Averaging (LADA) algorithm is proposed to achieve fast distributed consensus. They continue their study in this paper to gain a better understanding of distributed consensus via chain lifting and explore possible improvements for LADA. First, lower bounds for the averaging time via lifting Markov chains in a wireless network with a common transmission range r, as modeled by a geometric random graph G(n, r), are derived based on resistance, an invariant of Markov chains.