Local Interference Can Accelerate Gossip Algorithms
- 5 April 2011
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal of Selected Topics in Signal Processing
- Vol. 5 (4) , 876-887
Abstract
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(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.Keywords
This publication has 33 references indexed in Scilit:
- Gossip Algorithms for Distributed Signal ProcessingProceedings of the IEEE, 2010
- The Impact of Mobility on Gossip Algorithms2009
- Lattices are everywhere2009
- Fast Distributed Algorithms for Computing Separable FunctionsIEEE Transactions on Information Theory, 2008
- A scalable wireless communication architecture for average consensus2007
- Distributed Detection in Sensor Networks With Packet Losses and Finite Capacity LinksIEEE Transactions on Signal Processing, 2006
- Achieving$ 1over 2log (1+ hboxSNR)$on the AWGN Channel With Lattice Encoding and DecodingIEEE Transactions on Information Theory, 2004
- Analysis and optimization of randomized gossip algorithms2004
- Nested linear/lattice codes for structured multiterminal binningIEEE Transactions on Information Theory, 2002
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity FlowCombinatorics, Probability and Computing, 1992