Convergence rate of Controlled Hopwise Averaging on various graphs

This paper analyzes the convergence properties of Ideal Controlled Hopwise Averaging (ICHA) and Controlled Hopwise Averaging (CHA), two recently proposed asynchronous distributed averaging algorithms for wireless networks, which were shown via simulation to be more bandwidth/energy efficient than several existing schemes. We first derive deterministic upper bounds on the exponential convergence rate of ICHA on general graphs and specific ones (i.e., path, cycle, regular, strongly regular, and complete graphs), expressing the bounds explicitly in terms of the graph invariants. We then show that such bounds of ICHA are roughly 20% better than the average-case, stochastic convergence rate of Pairwise Averaging on path, cycle, and complete graphs. Finally, we obtain upper bounds on the convergence rate of CHA with respect to iteration and time, and show that iteration-wise CHA enjoys the same bounds as ICHA, closely mimicking its behavior while being practical.