Paper Info
Title
Convergence Rate Estimates For Consensus Over Random Graphs
Abstract
Multi-agent coordination algorithms with randomized interactions have seen use in a variety of settings in the multi-agent systems literature. In some cases, these algorithms can be random by design, as in a gossip-like algorithm, and in other cases they are random due to external factors, as in the case of intermittent communications. Targeting both of these scenarios, we present novel convergence rate estimates for consensus problems solved over random graphs. Established results provide asymptotic convergence in this setting, and we provide estimates of the rate of convergence in two forms. First, we estimate decreases in a quadratic Lyapunov function over time to bound how quickly the agents' disagreement decays, and second we bound the probability of being at least a given distance from the point of agreement. Simulation results are provided to support the theoretical developments made.
Year
DOI
Venue
2017
10.23919/ACC.2017.7963087
2017 AMERICAN CONTROL CONFERENCE (ACC)
Field
DocType
ISSN
Convergence (routing),Discrete mathematics,Convergence of random variables,Mathematical optimization,Random graph,Compact convergence,Proofs of convergence of random variables,Convergence tests,Rate of convergence,Mathematics,Modes of convergence
Conference
0743-1619
Citations 
PageRank 
References 
0
0.34
10
Authors
2
Name
Order
Citations
PageRank
Hale, M.T.1176.84
Magnus Egerstedt22862384.94