Linear Time Average Consensus on Fixed Graphs∗

We describe a protocol for the average consensus problem on any fixed undirected graph whose convergence time scales linearly in the total number nodes n. More precisely we provide a protocol which results in each node having a value within an e of the initial average after O Inln l|x ‘ xl|2) iterations. The protocol is completely distributed, with the exception of requiring all nodes to know the same upper bound U on the total number of nodes which is correct within a constant multiplicative factor.