We consider the binary consensus problem where each node in the network
initially observes one of two states and the goal for each node is to eventually
decide which one of the two states was initially held by the majority of the
nodes. Each node contacts other nodes and updates its current state based on the
state communicated by the last contacted node. We assume that both signaling (the
information exchanged at node contacts) and memory (computation state at each
node) are limited and restrict our attention to systems where each node can
contact any other node (i.e., complete graphs). It is well known that for systems
with binary signaling and memory, the probability of reaching incorrect consensus
is equal to the fraction of nodes that initially held the minority state. We show
that extending both the signaling and memory by just one state dramatically
improves the reliability and speed of reaching the correct consensus.
Specifically, we show that the probability of error decays exponentially with the
number of nodes *N* and the convergence time is logarithmic in *N* for
large *N*. We also examine the case when the state is ternary and signaling
is binary. The convergence of this system to consensus is again shown to be
logarithmic in *N* for large *N*, and is therefore faster than purely
binary systems. The type of distributed consensus problems that we study arises
in a variety of applications including those of sensor networks and opinion
formation in social networks – our results suggest that robust and efficient
protocols can be built with rather limited signaling and memory.