文章基本信息

标题：Democratic Consensus and the Local Majority Rule
本地全文：下载
作者：Nabil H. Mustafa ; Aleksandar Pekec
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：2000
卷号：7
期号：8
出版社：Aarhus University
摘要：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.