On Spatial Gossip Algorithms for Average Consensus
Michael Rabbat · 2007 IEEE/SP 14th Workshop on Statistical Signal Processing · 2007
This paper investigates the use of spatial gossip to compute the average consensus in networks such as grids or random geometric graphs, where connectivity is a function of proximity. Randomized gossip is a framework for distributed computation where, at each iteration, a random pair of nodes exchanges information, and then updates their local values by averaging. This simple protocol converges to an average consensus: every node obtains the average of the initial values across the network. In spatial gossip, if the distance between two nodes is d, then they communicate with probability proportional to d-ß for some ß ≥ 0. The special case ß = 0 corresponds to an algorithm known in the sensor network literature as geographic gossip. Dimakis et al. have shown that geographic gossip computes the average to accuracy n-1 in O(n3/2√log n) transmissions. In this paper we show that the same rates are achieved for ß = 2 and ß = 3. Each setting offers a different balance between the rate of convergence (in gossip rounds) and the average number of transmissions per gossip round. We illustrate, via simulation, that spatial gossip with ß = 2 generally yields superior performance over geographic gossip by a constant factor.