Consensus From Distributed Iterative Voting

摘要

Distributed algorithms executed by a network of nodes with limited computational resources have many practical applications, not only in computer science, but also in other areas of engineering, and in physics, biology, and the social sciences. This paper studies one such algorithm in which the nodes update their states by iteratively voting for one of a finite number of candidates. Our numerical simulations show that convergence for this algorithm depends on a parameter m that determines the mean of the normal distribution that generates the weights in the network. When m is above an upper threshold, the algorithm always converges to a consensus candidate. When m is below a lower threshold, the algorithm does not converge and there is no consensus. When m is between these two thresholds, then the algorithm converges, but not necessarily to a consensus candidate. The values of the thresholds depend on the size of the network.