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.

Published in:
2008 46Th Annual Allerton Conference On Communication, Control, And Computing, Vols 1-3, 591-598
Presented at:
46th Annual Allerton Conference on Communication, Control and Computing, Monticello, IL, Sep, 2008
Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa

 Record created 2011-10-17, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)