Geographic Gossip: Efficient Averaging for Sensor Networks

Abstract

Gossip algorithms for distributed computation are attractive due to their simplicity, distributed nature, and robustness in noisy and uncertain environments. However, using standard gossip algorithms can lead to a significant waste in energy by repeatedly recirculating redundant information. For realistic sensor network model topologies like grids and random geometric graphs, the inefficiency of gossip schemes is related to the slow mixing times of random walks on the communication graph. We propose and analyze an alternative gossiping scheme that exploits geographic information. By utilizing geographic routing combined with a simple resampling method, we demonstrate substantial gains over previously proposed gossip protocols. For regular graphs such as the ring or grid, our algorithm improves standard gossip by factors of $n$ and $\sqrt{n}$ respectively. For the more challenging case of random geometric graphs, our algorithm computes the true average to accuracy $\epsilon$ using $O(\frac{n^{1.5}}{\sqrt{\log n}}\log {\epsilon }^{-1})$ radio transmissions, which yields a $\sqrt{\frac{n}{\log n}}$ factor improvement over standard gossip algorithms. We illustrate these theoretical results with experimental comparisons between our algorithm and standard methods as applied to various classes of random fields.

To appear, IEEE Transactions on Signal Processing

References in corpus (1)

• Consensus Propagation

Cited by in corpus (22)

• Distributed quantum phase estimation with entangled photons
• Decentralized Federated Learning via Mutual Knowledge Transfer
• Polynomial Filtering for Fast Convergence in Distributed Consensus
• On Ergodicity, Infinite Flow and Consensus in Random Models
• Analysis of Sum-Weight-like algorithms for averaging in Wireless Sensor Networks
• Consensus and Products of Random Stochastic Matrices: Exact Rate for Convergence in Probability
• Efficient Information Aggregation Strategies for Distributed Control and Signal Processing
• Multi-hop Diffusion LMS for Energy-constrained Distributed Estimation
• Location-Aided Fast Distributed Consensus in Wireless Networks
• Toward Resource-Optimal Consensus over the Wireless Medium
• Fault-Tolerant Aggregation: Flow-Updating Meets Mass-Distribution
• Extending Gossip Algorithms to Distributed Estimation of U-Statistics
• Extensions of Fast-Lipschitz Optimization
• Non-Asymptotic Analysis of an Optimal Algorithm for Network-Constrained Averaging with Noisy Links
• Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
• A Chemistry-Inspired Framework for Achieving Consensus in Wireless Sensor Networks
• Differentially Private Distributed Estimation and Learning
• Randomized Consensus based Distributed Kalman Filtering over Wireless Sensor Networks
• Random walk based in-network computation of arbitrary functions
• Asynchrony and Acceleration in Gossip Algorithms
• A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip