Agreeing under randomized network dynamics
2012 (English)In: 2012 American Control Conference (ACC), IEEE Computer Society, 2012, 2394-2400 p.Conference paper (Refereed)
In this paper, we study randomized consensus processing over general random graphs. At time step k, each node will follow the standard consensus algorithm, or stick to current state by a simple Bernoulli trial with success probability pk. Connectivity-independent and arc-independent graphs are defined, respectively, to capture the fundamental independence of random graph processes with respect to a consensus convergence. Sufficient and/or necessary conditions are presented on the success probability sequence for the network to reach a global a.s. consensus under various conditions of the communication graphs. Particularly, for arc-independent graphs with simple self-confidence condition, we show that Σk pk is a sharp threshold corresponding to a consensus 0 1 law, i.e., the consensus probability is 0 for almost all initial conditions if Σk pk converges, and jumps to 1 for all initial conditions if Σk pk diverges.
Place, publisher, year, edition, pages
IEEE Computer Society, 2012. 2394-2400 p.
, Proceedings of the American Control Conference, ISSN 0743-1619
Consensus algorithms, Dynamics Randomization, Random graphs, Threshold
IdentifiersURN: urn:nbn:se:kth:diva-108015ISI: 000310776202112ScopusID: 2-s2.0-84869487129ISBN: 978-145771095-7OAI: oai:DiVA.org:kth-108015DiVA: diva2:580260
2012 American Control Conference, ACC 2012, 27 June 2012 through 29 June 2012, Montreal, QC
FunderICT - The Next Generation
QC 201212212012-12-212012-12-192013-04-11Bibliographically approved