Democratic Consensus and the Local Majority Rule

Abstract

In this paper we study a rather generic communication/
coordination/ computation problem: in a finite network of agents,
each initially having one of the two possible states, can the majority
initial state be computed and agreed upon (i.e., can a democratic
consensus be reached) by means of iterative application of
the local majority rule. We show that this task is failure-free only
in the networks that are nowhere truly local. In other words, the
idea of solving a truly global task (reaching consensus on majority
) by means of truly local computation only (local majority rule)
is doomed for failure.
We also show that even well connected networks of agents that
are nowhere truly local might fail to reach democratic consensus
when the local majority rule is applied iteratively. Structural
properties of democratic consensus computers, i.e., the networks
in which iterative application of the local majority rule always
yields consensus in the initial majority state, are presented.