Randomized Gossip Algorithms for Achieving Consensus on the Majority Vote

摘要

This paper studies a decentralized, randomized gossip algorithm for computing a majority vote amongst the binary decisions associated to n nodes organized in a fixed, ad-hoc network. It is indicated how this problem can be reduced to computing the global average using a standard, randomized gossip algorithm. Then, we illustrate how the majority vote problem allows one to formulate individual stopping rules deciding when an individual node makes its final verdict. Finally, we will provide an illustration of how well the algorithm and associated stopping rule behaves.