Characterizing Convergence Speed for Consensus Seeking over Dynamically Switching Directed Random Networks

Characterizing convergence speed is one of the 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 directed random network. Each link in the network, which represents the directed information flow between any ordered pair of agents, could be subject to failure with certain probability. Hence we model the information flow using dynamic random digraphs. 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 per-step (mean square) convergence factor as a measure of the convergence speed and derive the exact value for this factor. Numerical examples are also given to illustrate our theoretical results.