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.
WOS:000268229600086
2008
978-1-4244-2925-7
591
598
REVIEWED
Event name | Event place | Event date |
Monticello, IL | Sep, 2008 | |