Convergence Rate of Push-Sum Algorithms on Random Graphs
Pouya Rezaienia, Bahman Gharesifard, Tamás Linder, Behrouz Touri · 2018
We consider push-sum algorithms for average consensus over a random time-varying sequence of directed graphs. Motivated by the notion of infinite flow property used in the consensus literature, we introduce the notion of directed infinite flow property, which allows us to establish the ergodicity of matrices corresponding to the push-sum protocol. Using this result and the assumption that the auxiliary states of agents are uniformly bounded away from zero infinitely often, we prove the almost sure convergence of the evolutions of this class of algorithms to the average of initial states. We demonstrate that many interesting time-varying sequences of random directed graphs satisfy our condition. In particular, for a random sequence of directed graphs, we obtain uniform convergence rates for the push-sum algorithm.