Consensus Over Random Graph Processes: Network Borel–Cantelli Lemmas for Almost Sure Convergence

DOI10.1109/TIT.2015.2468584zbMATH Open1359.94283arXiv1112.1336OpenAlexW3104269091WikidataQ124805316 ScholiaQ124805316MaRDI QIDQ2977249FDOQ2977249

Authors: Karl Henrik Johansson, Guodong Shi, Brian D. O. Anderson 

Publication date: 28 April 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: 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. 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 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., ErdH{o}s-R'{e}nyi, 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.

Full work available at URL: https://arxiv.org/abs/1112.1336

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Information theory (general) (94A15) Measures of information, entropy (94A17) Linear codes (general theory) (94B05)

Cited In (6)

• Dynamics over Signed Networks
• Almost sure exponential convergence to consensus of random gossip algorithms
• Dynamics of opinions with social biases
• On the Equivalence and Condition of Different Consensus Over a Random Network Generated by i.i.d. Stochastic Matrices
• Interval consensus over random networks
• Convergence analysis of max-consensus algorithm in probabilistic communication networks with Bernoulli dropouts

This page was built for publication: Consensus Over Random Graph Processes: Network Borel–Cantelli Lemmas for Almost Sure Convergence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977249)