Paper Info
Title
Convergence Rate Of Push-Sum Algorithms On Random Graphs
Abstract
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.
Year
DOI
Venue
2018
10.1109/CDC.2018.8618933
2018 IEEE CONFERENCE ON DECISION AND CONTROL (CDC)
Field
DocType
ISSN
Convergence of random variables,Ergodicity,Random graph,Computer science,Random sequence,Directed graph,Uniform convergence,Algorithm,Uniform boundedness,Rate of convergence
Conference
0743-1546
Citations 
PageRank 
References 
0
0.34
0
Authors
4
Name
Order
Citations
PageRank
Pouya Rezaienia100.34
Bahman Gharesifard234026.54
Tamás Linder361768.20
Behrouz Touri417621.12