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
Year:
2008
Publisher:
Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa
ISBN:
978-1-4244-2925-7
Laboratories:




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


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)