Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2011-12-06
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
In this paper, we study randomized consensus processing over general random graphs. At time step $k$, each node will follow the standard consensus algorithm, or stick to current state by a simple Bernoulli trial with success probability $p_k$. Connectivity-independent and arc-independent graphs are defined, respectively, to capture the fundamental independence of random graph processes with respect to a consensus convergence. Sufficient and/or necessary conditions are presented on the success probability sequence for the network to reach a global a.s. consensus under various conditions of the communication graphs. Particularly, for arc-independent graphs with simple self-confidence condition, we show that $\sum_k p_k =\infty$ is a sharp threshold corresponding to a consensus $0-1$ law, i.e., the consensus probability is $0$ for almost all initial conditions if $\sum_k p_k$ converges, and jumps to $1$ for all initial conditions if $\sum_k p_k $ diverges. Convergence rates are established by lower and upper bounds of $\epsilon$-computation time. Finally, a belief evolution model in social networks is investigated and convergence condition is given for an opinion agreement, as a simple application of previous result.
Johansson Karl Henrik
Shi Guodong
No associations
LandOfFree
Randomized Consensus Processing over Random Graphs: Independence and Threshold does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Randomized Consensus Processing over Random Graphs: Independence and Threshold, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Randomized Consensus Processing over Random Graphs: Independence and Threshold will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-381619