Agreeing under randomized network dynamics

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 Σ_k p_k = ∞ is a sharp threshold corresponding to a consensus 0 - 1 law, i.e., the consensus probability is 0 for almost all initial conditions if Σ_k p_k converges, and jumps to 1 for all initial conditions if Σ_k p_k diverges.