Gossip Algorithms for Distributed Signal Processing
arXiv:1003.5309 · doi:10.1109/JPROC.2010.2052531
Abstract
Gossip algorithms are attractive for in-network processing in sensor networks because they do not require any specialized routing, there is no bottleneck or single point of failure, and they are robust to unreliable wireless network conditions. Recently, there has been a surge of activity in the computer science, control, signal processing, and information theory communities, developing faster and more robust gossip algorithms and deriving theoretical performance guarantees. This article presents an overview of recent work in the area. We describe convergence rate results, which are related to the number of transmitted messages and thus the amount of energy consumed in the network for gossiping. We discuss issues related to gossiping over wireless links, including the effects of quantization and noise, and we illustrate the use of gossip algorithms for canonical signal processing tasks including distributed estimation, source localization, and compression.
Submitted to Proceedings of the IEEE, 29 pages
References in corpus (4)
Cited by in corpus (66)
- On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
- Diffusion Adaptation Strategies for Distributed Optimization and Learning over Networks
- Diffusion Strategies Outperform Consensus Strategies for Distributed Estimation over Adaptive Networks
- A Tutorial on Modeling and Analysis of Dynamic Social Networks. Part II
- Diffusion LMS over Multitask Networks
- Convergence Rate Analysis of Distributed Gossip (Linear Parameter) Estimation: Fundamental Limits and Tradeoffs
- Likelihood Consensus and Its Application to Distributed Particle Filtering
- Diffusion Adaptation over Networks under Imperfect Information Exchange and Non-stationary Data
- Distributed Pareto Optimization via Diffusion Strategies
- -Learning: A Collaborative Distributed Strategy for Multi-Agent Reinforcement Learning Through Consensus + Innovations
- A Spectral Graph Uncertainty Principle
- Consensus+Innovations Distributed Kalman Filter with Optimized Gains
- Chebyshev Polynomial Approximation for Distributed Signal Processing
- Performance Limits for Distributed Estimation Over LMS Adaptive Networks
- Distributed Clustering and Learning Over Networks
- Cooperative Network Synchronization: Asymptotic Analysis
- Distributed Learning for Stochastic Generalized Nash Equilibrium Problems
- Distributed Diffusion-Based LMS for Node-Specific Adaptive Parameter Estimation
- Decentralized Frank-Wolfe Algorithm for Convex and Non-convex Problems
- Distributed Discrete-time Optimization in Multi-agent Networks Using only Sign of Relative State
- Optimization and Learning with Information Streams: Time-varying Algorithms and Applications
- Online Distributed Learning Over Networks in RKH Spaces Using Random Fourier Features
- Diffusion LMS Strategies in Sensor Networks with Noisy Input Data
- Proximal Multitask Learning over Networks with Sparsity-inducing Coregularization
- Empirical Centroid Fictitious Play: An Approach For Distributed Learning In Multi-Agent Games
- Decentralized Gaussian Filters for Cooperative Self-localization and Multi-target Tracking
- Asynchronous Gradient-Push
- Convergence Rates of Distributed Nesterov-like Gradient Methods on Random Networks
- Distributed Variational Bayesian Algorithms Over Sensor Networks
- Diffusion-Based Adaptive Distributed Detection: Steady-State Performance in the Slow Adaptation Regime
- Stability and Performance Limits of Adaptive Primal-Dual Networks
- Analysis of Sum-Weight-like algorithms for averaging in Wireless Sensor Networks
- Estimation of Space-Time Varying Parameters Using a Diffusion LMS Algorithm
- Cyber-Social Systems: Modeling, Inference, and Optimal Design
- Distributed Decision-Making over Adaptive Networks
- On the Influence of Informed Agents on Learning and Adaptation over Networks
- Adaptation and learning over networks under subspace constraints -- Part I: Stability Analysis
- Convergence and Applications of a Gossip-based Gauss-Newton Algorithm
- Energy Efficiency of Distributed Signal Processing in Wireless Networks: A Cross-Layer Analysis
- Quantization for decentralized learning under subspace constraints
- Consensus and Products of Random Stochastic Matrices: Exact Rate for Convergence in Probability
- Finite-time Convergent Gossiping
- Distributed Constrained Recursive Nonlinear Least-Squares Estimation: Algorithms and Asymptotics
- Order-2 Asymptotic Optimality of the Fully Distributed Sequential Hypothesis Test
- Networked Signal and Information Processing
- Diffusion Estimation Over Cooperative Multi-Agent Networks With Missing Data
- Federated Bandit: A Gossiping Approach
- Information-Sharing over Adaptive Networks with Self-interested Agents
- Coordinate-Descent Diffusion Learning by Networked Agents
- Local Tomography of Large Networks under the Low-Observability Regime
- Scaling-up Distributed Processing of Data Streams for Machine Learning
- On Constrained Randomized Quantization
- Ergodicity in Stationary Graph Processes: A Weak Law of Large Numbers
- A Unified Algorithmic Framework for Distributed Adaptive Signal and Feature Fusion Problems -- Part I: Algorithm Derivation
- Distributed Adaptive Learning Under Communication Constraints
- FADE: Fast and Asymptotically efficient Distributed Estimator for dynamic networks
- Convergence Rate Analysis for Periodic Gossip Algorithms in Wireless Sensor Networks
- Local Graph Clustering with Network Lasso
- Stochastic Optimization from Distributed, Streaming Data in Rate-limited Networks
- Convergence Results on Pulse Coupled Oscillator Protocols in Locally Connected Networks
- Compressed Regression over Adaptive Networks
- A Chemistry-Inspired Framework for Achieving Consensus in Wireless Sensor Networks
- Distributed Voting in Beep Model
- A Graphical Evolutionary Game Approach to Social Learning
- Spatial Whitening Framework for Distributed Estimation
- Asymptotically Achieving Centralized Rate on the Decentralized Network MISO Channel