Robust Average Consensus over Packet Dropping Links: Analysis via Coefficients of Ergodicity

We consider a networked system in which each component (node) iteratively exchanges information with its neighbors according to an arbitrary, possibly directed topology. Based on an iterative exchange of (local and possibly directed) information, we develop an average-consensus distributed algorithm that is robust to unreliable (packet-dropping) communication links. By introducing virtual nodes, we show that the execution of the proposed algorithm is mathematically equivalent to a finite inhomogenous Markov chain. Then, by using coefficients of ergodicity, we can prove convergence of the robust distributed algorithm to the exact average, in the presence of packet drops and under a very broad set of conditions.