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 ofthe local majority rule. We show that this task is failure-free onlyin the networks that are nowhere truly local. In other words, theidea 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 thatare nowhere truly local might fail to reach democratic consensuswhen the local majority rule is applied iteratively. Structuralproperties of democratic consensus computers, i.e., the networksin which iterative application of the local majority rule alwaysyields consensus in the initial majority state, are presented.