On Spatial Gossip Algorithms for Average Consensus

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.