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 pk. 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 pk = ∞ 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 pk converges, and jumps to 1 for all initial conditions if Σk pk diverges.