Change search
ReferencesLink to record
Permanent link

Direct link
Consensus Over Random Graph Processes: Network Borel-Cantelli Lemmas for Almost Sure Convergence
KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre.
2015 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 61, no 10, 5690-5707 p.Article in journal (Refereed) Published
Abstract [en]

Distributed consensus computation over random graph processes is considered. The random graph process is defined as a sequence of random variables which take values from the set of all possible digraphs over the node set. At each time step, every node updates its state based on a Bernoulli trial, independent in time and among different nodes: either averaging among the neighbor set generated by the random graph, or sticking with its current state. The connectivity-independence and arc-independence are introduced to capture the fundamental influence of the random graphs on the consensus convergence. Necessary and/or sufficient conditions are presented on the success probabilities of the Bernoulli trials for the network to reach a global almost sure consensus, with some sharp threshold established revealing a consensus zero-one law. Convergence rates are established by the lower and upper bounds of the epsilon-computation time. We also generalize the concepts of connectivity/arc independence to their analogues from the *-mixing point of view, so that our results apply to a very wide class of graphical models, including the majority of random graph models in the literature, e.g., Erdos-Renyi, gossiping, and Markovian random graphs. We show that under *-mixing, our convergence analysis continues to hold and the corresponding almost sure consensus conditions are established. Finally, we further investigate almost sure finite-time convergence of random gossiping algorithms, and prove that the Bernoulli trials play a key role in ensuring finite-time convergence. These results add to the understanding of the interplay between random graphs, random computations, and convergence probability for distributed information processing.

Place, publisher, year, edition, pages
IEEE Communications Society, 2015. Vol. 61, no 10, 5690-5707 p.
Keyword [en]
Consensus algorithms, random graphs, zero-one law, gossiping
National Category
Information Systems Signal Processing Discrete Mathematics
URN: urn:nbn:se:kth:diva-174914DOI: 10.1109/TIT.2015.2468584ISI: 000361486800031ScopusID: 2-s2.0-84942342524OAI: diva2:862493

QC 20151022

Available from: 2015-10-22 Created: 2015-10-09 Last updated: 2015-10-22Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus
By organisation
ACCESS Linnaeus Centre
In the same journal
IEEE Transactions on Information Theory
Information SystemsSignal ProcessingDiscrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 21 hits
ReferencesLink to record
Permanent link

Direct link