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.

Ämnesord

TEKNIK OCH TEKNOLOGIER  -- Elektroteknik och elektronik -- Reglerteknik (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Electrical Engineering, Electronic Engineering, Information Engineering -- Control Engineering (hsv//eng)

Nyckelord

Consensus algorithms

Dynamics Randomization

Random graphs

Threshold

Publikations- och innehållstyp

ref (ämneskategori)

kon (ämneskategori)