%0 Generic %1 Shi2011 %A Shi, Guodong %A Johansson, Karl Henrik %D 2011 %K graphs network_analysis %T Randomized Consensus Processing over Random Graphs: Independence and Convergence %U http://arxiv.org/PS_cache/arxiv/pdf/1112/1112.1336v2.pdf %X Various consensus algorithms over random networks have been investigated in the literature. In this paper, we focus on the role that randomized individual decision-making plays to consensus seeking under stochastic communications. At each time step, each node will independently choose to follow the consensus algorithm, or to stick to current state by a simple Bernoulli trial with time-dependent success probabilities. This node decision strategy characterizes the random node-failures on a communication networks, or a biased opinion selection in the belief evolution over social networks. Connectivity-independent and arc-independent graphs are defined, respectively, to capture the fundamental nature of random network processes with regard to the convergence of the consensus algorithms. A series of sufficient and/or necessary conditions are given on the success probability sequence for the network to reach a global consensus with probability one under different stochastic connectivity assumptions, by which a comprehensive understanding on the fundamental independence of random communication graphs is achieved under the metric of collective coordination. Lower and upper bounds for the $\epsilon$-computation time are proposed. As an illustration of the use of the results, a gossip consensus algorithm is investigated under decision randomization.

@misc{Shi2011, abstract = { Various consensus algorithms over random networks have been investigated in the literature. In this paper, we focus on the role that randomized individual decision-making plays to consensus seeking under stochastic communications. At each time step, each node will independently choose to follow the consensus algorithm, or to stick to current state by a simple Bernoulli trial with time-dependent success probabilities. This node decision strategy characterizes the random node-failures on a communication networks, or a biased opinion selection in the belief evolution over social networks. Connectivity-independent and arc-independent graphs are defined, respectively, to capture the fundamental nature of random network processes with regard to the convergence of the consensus algorithms. A series of sufficient and/or necessary conditions are given on the success probability sequence for the network to reach a global consensus with probability one under different stochastic connectivity assumptions, by which a comprehensive understanding on the fundamental independence of random communication graphs is achieved under the metric of collective coordination. Lower and upper bounds for the $\epsilon$-computation time are proposed. As an illustration of the use of the results, a gossip consensus algorithm is investigated under decision randomization. }, added-at = {2011-12-07T14:31:51.000+0100}, author = {Shi, Guodong and Johansson, Karl Henrik}, biburl = {https://www.bibsonomy.org/bibtex/256f3afb39f7c077ad0c66189835685e7/maxirichter}, description = {Randomized Consensus Processing over Random Graphs: Independence and Convergence}, interhash = {fea3024bec9b069c3e21af96bcfe1ba7}, intrahash = {56f3afb39f7c077ad0c66189835685e7}, keywords = {graphs network_analysis}, note = {cite arxiv:1112.1336}, timestamp = {2012-01-14T20:47:45.000+0100}, title = {Randomized Consensus Processing over Random Graphs: Independence and Convergence}, url = {http://arxiv.org/PS_cache/arxiv/pdf/1112/1112.1336v2.pdf}, year = 2011 }