Local Interference Can Accelerate Gossip Algorithms

In this paper we show how interference can be exploited to perform gossip computations over a larger local neighborhood, rather than only pairs of nodes. We use a recently introduced technique called computation coding to perform reliable computation over noisy multiple access channels. Since many nodes can simultaneously average in a single round, neighborhood gossip clearly converges faster than nearest neighbor gossip. We characterize how many gossip rounds are required for a given neighborhood size. Also, we show that if the size of the collaboration neighborhood is larger than a critical value that depends on the path loss exponent and the network size, interference can yield exponential benefits in the energy required to compute the average.