Accelerated linear iterations for distributed averaging

Distributed averaging deals with a network of n > 1 agents and the constraint that each agent is able to communicate only with its neighbors. The purpose of the distributed averaging problem is to devise a protocol which will enable all n agents to asymptotically determine in a decentralized manner, the average of the initial values of their scalar agreement variables. Most distributed averaging protocols involve a linear iteration which depends only on the current estimates of the average. Building on the idea proposed in Muthukrishnan, Ghosh, and Schultz (1998), this paper investigates an augmented linear iteration for fast distributed averaging in which local memory is exploited. A thorough characterization of the behavior of the augmented system is obtained under appropriate assumptions. It is shown that the augmented linear iteration can solve the distributed averaging problem faster than the original linear iteration, but the adjustable parameter must be chosen carefully. The optimal choice of the parameter and the corresponding fastest rate of convergence are also provided in closed form.