TY - GEN

T1 - An upper bound on the convergence time for distributed binary consensus

AU - Shang, Shang

AU - Cuff, Paul W.

AU - Kulkarni, Sanjeev R.

AU - Hui, Pan

PY - 2012/10/24

Y1 - 2012/10/24

N2 - The problem addressed in this paper is the analysis of a distributed consensus algorithm for arbitrary networks, proposed by Bénézit et al. In the initial setting, each node in the network has one of two possible states ("yes" or "no"). Nodes can update their states by communicating with their neighbors via a 2-bit message in an asynchronous clock setting. Eventually, all nodes reach consensus on the majority states. We use the theory of electric networks, random walks, and couplings of Markov chains to derive an O(N 4 log N) upper bound for the expected convergence time on an arbitrary graph of size N.

AB - The problem addressed in this paper is the analysis of a distributed consensus algorithm for arbitrary networks, proposed by Bénézit et al. In the initial setting, each node in the network has one of two possible states ("yes" or "no"). Nodes can update their states by communicating with their neighbors via a 2-bit message in an asynchronous clock setting. Eventually, all nodes reach consensus on the majority states. We use the theory of electric networks, random walks, and couplings of Markov chains to derive an O(N 4 log N) upper bound for the expected convergence time on an arbitrary graph of size N.

KW - Distributed binary consensus

KW - convergence time

KW - gossip

UR - http://www.scopus.com/inward/record.url?scp=84867654571&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867654571&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84867654571

SN - 9780982443859

T3 - 15th International Conference on Information Fusion, FUSION 2012

SP - 369

EP - 375

BT - 15th International Conference on Information Fusion, FUSION 2012

T2 - 15th International Conference on Information Fusion, FUSION 2012

Y2 - 7 September 2012 through 12 September 2012

ER -