  In this paper, we consider lightweight decentralised algorithms for achieving
consensus in distributed systems. Each member of a distributed group has a
private value from a fixed set consisting of, say, two elements, and the goal
is for all members to reach consensus on the majority value. We explore
variants of the voter model applied to this problem. In the voter model, each
node polls a randomly chosen group member and adopts its value. The process is
repeated until consensus is reached. We generalize this so that each member
polls a (deterministic or random) number of other group members and changes
opinion only if a suitably defined super-majority has a different opinion. We
show that this modification greatly speeds up the convergence of the algorithm,
as well as substantially reducing the probability of it reaching consensus on
the incorrect value.
