Consensus over Random Graph Processes: Network Borel-Cantelli Lemmas for Almost Sure Convergence
Date
2015
Authors
Shi, Guodong
Anderson, Brian
Johansson , Karl Henrik
Journal Title
Journal ISSN
Volume Title
Publisher
Institute of Electrical and Electronics Engineers (IEEE Inc)
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. 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., Erds-Ré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.
Description
Keywords
Citation
Collections
Source
IEEE Transactions on Information Theory
Type
Journal article
Book Title
Entity type
Access Statement
License Rights
Restricted until
2037-12-31
Downloads
File
Description