Majority consensus and the local majority rule
Publication
, Conference
Mustafa, NH; Pekeč, A
Published in: Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 2001
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 by means of local computation only? We describe the architecture of networks that are always capable of reaching the consensus on the majority initial state of its agents. In particular, we show that, for any truly local network of agents, there are instances in which the network is not capable of reaching such consensus. Thus, every truly local computation approach that requires reaching consensus is not failurefree. © 2011 Springer-Verlag Berlin Heidelberg.
Duke Scholars
Published In
Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
ISBN
9783540422877
Publication Date
January 1, 2001
Volume
2076 LNCS
Start / End Page
530 / 542
Related Subject Headings
- Artificial Intelligence & Image Processing
Citation
APA
Chicago
ICMJE
MLA
NLM
Mustafa, N. H., & Pekeč, A. (2001). Majority consensus and the local majority rule. In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 2076 LNCS, pp. 530–542). https://doi.org/10.1007/3-540-48224-5_44
Mustafa, N. H., and A. Pekeč. “Majority consensus and the local majority rule.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2076 LNCS:530–42, 2001. https://doi.org/10.1007/3-540-48224-5_44.
Mustafa NH, Pekeč A. Majority consensus and the local majority rule. In: Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2001. p. 530–42.
Mustafa, N. H., and A. Pekeč. “Majority consensus and the local majority rule.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2076 LNCS, 2001, pp. 530–42. Scopus, doi:10.1007/3-540-48224-5_44.
Mustafa NH, Pekeč A. Majority consensus and the local majority rule. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2001. p. 530–542.
Published In
Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
ISBN
9783540422877
Publication Date
January 1, 2001
Volume
2076 LNCS
Start / End Page
530 / 542
Related Subject Headings
- Artificial Intelligence & Image Processing