Convergence speed in distributed consensus over dynamically switching random networks

Characterizing convergence speed is one of the most important research challenges in the design of distributed consensus algorithms for networked multi-agent systems. In this paper, we consider a group of agents that communicate via a dynamically switching random information network. Each link in the network, which represents the directed/undirected information flow between any ordered/unordered pair of agents, could be subject to failure with a certain probability. Hence we model the information flow using dynamically switching random graphs. We characterize the convergence speed for the distributed discrete-time consensus algorithm over a variety of random networks with arbitrary weights. In particular, we propose the asymptotic and per-step (mean square) convergence factors as measures of the convergence speed and derive the exact value for the per-step (mean square) convergence factor. Numerical examples are also given to illustrate our theoretical results. (C) 2009 Elsevier Ltd. All rights reserved.