Consensus Over Random Graph Processes: Network Borel-Cantelli Lemmas for Almost Sure Convergence
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
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.
Consensus algorithms, random graphs, zero-one law, gossiping
Information Systems Signal Processing Discrete Mathematics
IdentifiersURN: urn:nbn:se:kth:diva-174914DOI: 10.1109/TIT.2015.2468584ISI: 000361486800031ScopusID: 2-s2.0-84942342524OAI: oai:DiVA.org:kth-174914DiVA: diva2:862493
QC 201510222015-10-222015-10-092015-10-22Bibliographically approved