Local Interference Can Accelerate Gossip Algorithms
Bobak Nazer, Alexandros G. Dimakis, Michael Gastpar · IEEE Journal of Selected Topics in Signal Processing · 2011
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 withnnodes and sizemneighborhoods, neighborhood gossip requiresO(n2/m2) rounds while standard gossip requires Θ(n2) 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.