Distributed Averaging Using Periodic Gossiping

The distributed averaging problem is a consensus problem whose objective is to devise a protocol which will enable all the members of a group of autonomous agents to compute the average of the initial values of their individual consensus variables in a distributed manner. Periodic gossiping is a deterministic method for solving the distributed averaging problem by stipulating that each pair of agents which are allowed to gossip, do so repeatedly in accordance with a prespecified periodic schedule. Agent pairs which are allowed to gossip correspond to edges on a given connected, undirected graph. In general, the rate at which the agents' consensus variables converge to the desired average value depends on the order in which the gossips occur over a period. The main contributions of this paper are first to characterize the classes of periodic gossip sequences which have the same convergence rate and second to prove that if the graph of allowable gossips is a tree with each edge restricted to gossiping once per period, the convergence rate is quite surprisingly, fixed and invariant over all possible periodic gossip sequences the graph allows. To arrive at these results, a new and unusual graph theoretic concept, namely the transfer function of a node of an undirected graph, is used. Among all the trees with the same number of edges, optimal tree structures, which yield the fastest convergence rate, can then be sought.