On the Convergence of Perturbed Non-Stationary Consensus Algorithms

We consider consensus algorithms in their most general setting and provide conditions under which such algorithms are guaranteed to converge, almost surely, to a consensus. Let {A(t),B(t)} isin R^{N times N} be (possibly) random, non-stationary matrices and {x(t),m(t)} isin R^{N times 1} be state and perturbation vectors, respectively. For any consensus algorithm of the form x(t + 1) = A(t)x(t) + B(t)m(t), we provide conditions under which consensus is achieved almost surely, i.e., Pr {lim_trarrinfin x(t) = c1} = 1 for some c isin R. Moreover, we show that this general result subsumes recently reported results for specific consensus algorithms classes, including sum-preserving, non-sum-preserving, quantized and noisy gossip algorithms. Also provided are the e-converging time for any such converging iterative algorithm, i.e., the earliest time at which the vector x(t) is e close to consensus, and sufficient conditions for convergence in expectation to the initial node measurements average.