Local Interference Can Accelerate Gossip Algorithms

In this paper, we show how interference can be exploited to perform gossip computations for average-based consensus over a larger local neighborhood, rather than only pairs of nodes. We use a new channel coding technique called computation coding to compute sums reliably over the wireless medium. Since many nodes can simultaneously average in a single round, our neighborhood gossip algorithm converges faster than the standard nearest neighbor gossip algorithm. For a network with n nodes and size m neighborhoods, neighborhood gossip requires O(n(2)/m(2)) rounds while standard gossip requires circle dot(n(2)) rounds. Furthermore, we show that if the power path loss coefficient is less than 4, the total transmit energy employed by neighborhood gossip is polynomially smaller than that employed by standard gossip.