Consensus and Products of Random Stochastic Matrices: Exact Rate for Convergence in Probability

Abstract

Distributed consensus and other linear systems with system stochastic matrices $W_k$ emerge in various settings, like opinion formation in social networks, rendezvous of robots, and distributed inference in sensor networks. The matrices $W_k$ are often random, due to, e.g., random packet dropouts in wireless sensor networks. Key in analyzing the performance of such systems is studying convergence of matrix products $W_k{W}_{k-1}...W_1$. In this paper, we find the exact exponential rate $I$ for the convergence in probability of the product of such matrices when time $k$ grows large, under the assumption that the $W_k$'s are symmetric and independent identically distributed in time. Further, for commonly used random models like with gossip and link failure, we show that the rate $I$ is found by solving a min-cut problem and, hence, easily computable. Finally, we apply our results to optimally allocate the sensors' transmission power in consensus+innovations distributed detection.

References in corpus (6)

• Gossip Algorithms for Distributed Signal Processing
• Geographic Gossip: Efficient Averaging for Sensor Networks
• Weight Optimization for Consensus Algorithms with Correlated Switching Topology
• Large Deviations Performance of Consensus+Innovations Distributed Detection with Non-Gaussian Observations
• Greedy Gossip with Eavesdropping
• Product of Random Stochastic Matrices

Cited by in corpus (7)

• Large Deviations Performance of Consensus+Innovations Distributed Detection with Non-Gaussian Observations
• Convergence Rates of Distributed Nesterov-like Gradient Methods on Random Networks
• Distributed Gradient Methods with Variable Number of Working Nodes
• Distributed inference over directed networks: Performance limits and optimal design
• Lyapunov Approach to Consensus Problems
• Distributed Task Allocation in Homogeneous Swarms Using Language Measure Theory
• Distributed Averaging With Random Network Graphs and Noises