Distributed Consensus Algorithms in Sensor Networks With Imperfect Communication: Link Failures and Channel Noise

By Soummya Kar, José M. F. Moura. IEEE Transactions on Signal Processing, 2007

702 citations recorded by the source corpus.

The paper studies average consensus with random topologies (intermittent links) and noisy channels. Consensus with noise in the network links leads to the bias-variance dilemma-running consensus for long reduces the bias of the final average estimate but increases its variance. We present two different compromises to this tradeoff: the A-ND algorithm modifies conventional consensus by forcing the weights to satisfy a persistence condition (slowly decaying to zero;) and the A-NC algorithm where the weights are constant but consensus is run for a fixed number of iterations [^(iota)], then it is restarted and rerun for a total of [^(p)] runs, and at the end averages the final states of the [^(p)] runs (Monte Carlo averaging). We use controlled Markov processes and stochastic approximation arguments to prove almost sure convergence of A-ND to a finite consensus limit and compute explicitly the mean square error (mse) (variance) of the consensus limit. We show that A-ND represents the best of both worlds-zero bias and low variance-at the cost of a slow convergence rate; rescaling the weights balances the variance versus the rate of bias reduction (convergence rate). In contrast, A-NC, because of its constant weights, converges fast but presents a different bias-variance tradeoff. For the same number of iterations [^(iota)][^(p)] , shorter runs (smaller [^(iota)] ) lead to high bias but smaller variance (larger number [^(p)] of runs to average over.) For a static nonrandom network with Gaussian noise, we compute the optimal gain for A-NC to reach in the shortest number of iterations [^(iota)][^(p)] , with high probability (1-delta), (epsiv, delta)-consensus (epsiv residual bias). Our results hold under fairly general assumptions on the random link failures and communication noise.

View Paper: https://www.semanticscholar.org/paper/04fc5a703fd877d16802e22ad948a7a0ecc7bd14

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Asymptotic properties of consensus-type algorithms for networked systems with regime-switching topologies (2011, background): “Kar and Moura (2009) employs randomly switching Laplacian matrices together with observation noises that may be state dependent and Markovian.”
Supervised Learning Under Distributed Features (2018, background): “In this work, we focus on empirical risk minimization problems, which, by ergodicity arguments, provide a good approximation for average risks [7], [14]–[20].”
Distributed Consensus Algorithms in Sensor Networks: Quantized Data and Random Link Failures (2007, methodology): “In [19], we studied consensus with r andom topologies and (analog) noisy communications.”
Convergence Rates for Distributed Stochastic Optimization Over Random Networks (2018, unknown): “, [10]–[12].”
Distributed averaging on digital erasure networks (2011, background): “…quantized communication (Aysal, Coates, & Rabbat, 2008; Carli, Bullo, & Zampieri, 2010; Frasca, Carli, Fagnani, & Zampieri, 2009; Kar & Moura, 2010; Li, Fu, Xie, & Zhang, in press), or transmission affected by additive noise (Huang & Manton, 2009; Kar & Moura, 2009; Rajagopal & Wainwright, 2008).”
QD-Learning: A Collaborative Distributed Strategy for Multi-Agent Reinforcement Learning Through Consensus + Innovations (2012, background): “As such, the resulting value function update processes at the agents are mixed time-scale, in which the distinct potentials of consensus (corresponding to information mixing through neighborhood communication [30], [31], [32], [29], [33], [34], [35]) and local innovation (corresponding to the instan”
Distributed Estimation of Gauss - Markov Random Fields With One-Bit Quantized Data (2010, background): “So far a lot of existing works [1]–[5] studied the distributed estimation problem by modeling the phenomena of interest as a common scalar parameter.”
Distributed consensus over network with noisy links (2009, unknown): “Keywords: Consensus, time varying network, noisy links.”
Distributed Network Optimization With Heuristic Rational Agents (2012, background): “We show that models com- 1053-587X/$31.00 © 2012 IEEE monly used to study propagation of opinions in social networks [20], foraging of animal herds [11], [21], and quantization and communication issues in field estimation using WSNs [1], [2], [22], [23] can be cast in the language of heuristic…”
Distributed Sensor Localization in Random Environments Using Minimal Number of Anchor Nodes (2008, background): “, depend on the particular choice of , which is studied in the context of distributed stochastic consensus averaging in [33].”
On the O(1=k) convergence of asynchronous distributed alternating Direction Method of Multipliers (2013, background): “Such gradient (3)This work is clearly also related to the extensive literatur e on consensus and cooperative control, where the goal is to d esign local deterministic or random update rules to achieve global coor dination (for deterministic update rules, see [4], [7], [15 ], [23], [27], [38], [39], ”
Distributed Asynchronous Constrained Stochastic Optimization (2011, unknown): “The two main mathematical abstractions which have been employed to address these problems are the problem of reaching consensus on the decision variables [1]–[5] in a network of computational agents and the problem of cooperative solution to distributed optimization problems [6]–[11].”
Asynchronous Broadcast-Based Convex Optimization Over a Network (2011, background): “this paper is related to the literature on distributed consensus and averaging [10], [11], [15]–[17], [19]–[ 22 ].”