Abstract | ||
---|---|---|
We consider the consensus and ergodicity for a random linear discrete-time system driven by stochastic matrices. We focus on independent models with certain properties, and we study the ergodicity and consensus of such random models through a novel property, termed infinite flow property. Our key result is the establishment that for a class of independent random models, this property is a necessary and sufficient condition for ergodicity. Using this result, we show that the ergodicity of these models and the ergodicity of their expected models are the same. The result provides us with new tools for studying various aspects of dynamic networks and beyond. We demonstrate the potential use of our key result through several different applications. In particular, we apply it to provide a generalization of the randomized gossip algorithm and to study a consensus over a dynamic network with link failures. Also, we use the result to investigate necessary and sufficient conditions for the ergodicity of an equal-neighbor average algorithm on Erdös-Rényi random graphs. Finally, we demonstrate that our result can be employed to provide an alternative proof of the second Borel-Cantelli lemma. |
Year | DOI | Venue |
---|---|---|
2010 | 10.1109/CDC.2010.5717769 | Decision and Control |
Keywords | Field | DocType |
discrete time systems,graph theory,graphs,matrix algebra,randomised algorithms,stochastic processes,Erdos-Renyi random graphs,dynamic network,equal-neighbor average algorithm,ergodicity,infinite flow,random linear discrete time system,random model,randomized gossip algorithm,second Borel-Cantelli lemma,stochastic matrices,Borel-Cantelli lemma,Ergodicity,gossip algorithm,linear random model,link failure,product of random stochastic matrices | Graph theory,Dynamic network analysis,Mathematical optimization,Ergodicity,Random graph,Computer science,Matrix (mathematics),Borel–Cantelli lemma,Stochastic process,Lemma (mathematics) | Conference |
ISSN | ISBN | Citations |
0743-1546 | 978-1-4244-7745-6 | 7 |
PageRank | References | Authors |
0.78 | 3 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Behrouz Touri | 1 | 176 | 21.12 |
Angelia Nedic | 2 | 2323 | 148.65 |