{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,15]],"date-time":"2025-11-15T10:16:59Z","timestamp":1763201819048,"version":"build-2065373602"},"reference-count":39,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2014,5,21]],"date-time":"2014-05-21T00:00:00Z","timestamp":1400630400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>This paper investigates self-organizing binary majority consensus disturbed by faulty nodes with random and persistent failure. We study consensus in ordered and random networks with noise, message loss and delays. Using computer simulations, we show that: (1) explicit randomization by noise, message loss and topology can increase robustness towards faulty nodes; (2) commonly-used faulty nodes with random failure inhibit consensus less than faulty nodes with persistent failure; and (3) in some cases, such randomly failing faulty nodes can even promote agreement.<\/jats:p>","DOI":"10.3390\/e16052820","type":"journal-article","created":{"date-parts":[[2014,5,21]],"date-time":"2014-05-21T10:38:31Z","timestamp":1400668711000},"page":"2820-2838","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Randomized Binary Consensus with Faulty Agents"],"prefix":"10.3390","volume":"16","author":[{"given":"Alexander","family":"Gogolev","sequence":"first","affiliation":[{"name":"Institute of Networked and Embedded Systems, University of Klagenfurt, Lakeside B02a Klagenfurt, Austria"},{"name":"Department of Naval, Electric, Electronic and Telecommunication Engineering, University of Genoa, Via Opera Pia 11a Genoa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lucio","family":"Marcenaro","sequence":"additional","affiliation":[{"name":"Department of Naval, Electric, Electronic and Telecommunication Engineering, University of Genoa, Via Opera Pia 11a Genoa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2014,5,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/1994.2207","article-title":"An algorithm for concurrency control and recovery in replicated distributed databases","volume":"9","author":"Bernstein","year":"1984","journal-title":"ACM Trans. Database Syst"},{"key":"ref_2","unstructured":"Olfati-Saber, R., and Shamma, J.S. (2005, January 12\u201315). Consensus filters for sensor networks and distributed sensor fusion, Seville, Spain."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Alighanbari, M., and How, J.P. (2006, January 14\u201316). An unbiased Kalman consensus algorithm, Minneapolis, MN, USA.","DOI":"10.1109\/ACC.2006.1657263"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Aspnes, J. (2000, January 16\u201319). Fast deterministic consensus in a noisy environment, Portland, OR, USA.","DOI":"10.1145\/343477.343631"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Carli, R., Fagnani, F., Frasca, P., Taylor, T., and Zampieri, R. (2007, January 2\u20135). Average consensus on networks with transmission noise or quantization, Kos, Greece.","DOI":"10.23919\/ECC.2007.7068829"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Kar, S., and Moura, J.M.F. (2007, January 04\u201307). Distributed average consensus in sensor networks with random link failures and communication channel noise, Pacific Grove, CA, USA.","DOI":"10.1109\/ICASSP.2007.366410"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Kingston, D.B., and Beard, R.W. (2006, January 14\u201316). Discrete-time average consensus under switching network topologies, Minnesota, MN, USA.","DOI":"10.1109\/ACC.2006.1657268"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1145\/3149.214121","article-title":"Impossibility of distributed consensus with one faulty process","volume":"32","author":"Fischer","year":"1985","journal-title":"J. ACM"},{"key":"ref_9","unstructured":"Fischer, M.J., Lynch, N.A., and Merritt, M.S. Easy impossibility proofs for distributed consensus problems, Minaki, ON, Canada, USA."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1145\/226643.226647","article-title":"Unreliable failure detectors for reliable distributed systems","volume":"43","author":"Chandra","year":"1996","journal-title":"J. ACM"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1145\/234533.234549","article-title":"The weakest failure detector for solving consensus","volume":"43","author":"Chandra","year":"1996","journal-title":"J. ACM"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1145\/7531.7533","article-title":"On the minimal synchronism needed for distributed consensus","volume":"34","author":"Dolev","year":"1987","journal-title":"J. ACM"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1145\/42282.42283","article-title":"Consensus in the presence of partial synchrony","volume":"35","author":"Dwork","year":"1988","journal-title":"J. ACM"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/s00446-002-0081-5","article-title":"Randomized protocols for asynchronous consensus","volume":"16","author":"Aspnes","year":"2003","journal-title":"Distr. Comput"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"12085","DOI":"10.1073\/pnas.0400672101","article-title":"Efficient system-wide coordination in noisy environments","volume":"101","author":"Moreira","year":"2004","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_16","unstructured":"Ben-Or, M. Another advantage of free choice: Completely asynchronous agreement protocols, Montreal, QC, Canada."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Gogolev, A., Marchenko, N., Bettstetter, C., and Marcenaro, L. (2014). Distributed Binary Consensus in Networks With Faults. ACM Trans. Autonom. Adapt. Syst, submitted.","DOI":"10.1145\/2746347"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Gogolev, A., and Marcenaro, L. (2014, January 21\u201324). Efficient binary consensus in randomized and noisy networks, Singapore.","DOI":"10.1109\/ISSNIP.2014.6827594"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u201csmall-world\u201d networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1617","DOI":"10.1109\/49.12889","article-title":"Routing of multipoint connections","volume":"6","author":"Waxman","year":"1988","journal-title":"IEEE J. Sel. Area"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1645","DOI":"10.1137\/0150098","article-title":"Synchronization of Pulse-Coupled Biological Oscillators","volume":"50","author":"Mirollo","year":"1990","journal-title":"SIAM J. Appl. Math"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1023\/A:1004823720305","article-title":"Reliable cellular automata with self-organization","volume":"103","author":"Gacs","year":"2001","journal-title":"J. Stat. Phys"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1002\/ctpp.201010107","article-title":"Effects of Harmonic Modulation of Current in Glow Discharge Dusty Plasma with Ordered Structures","volume":"51","author":"Gogolev","year":"2011","journal-title":"Contrib. Plasma Phys"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"073031","DOI":"10.1088\/1367-2630\/14\/7\/073031","article-title":"Guaranteeing global synchronization in networks with stochastic interactions","volume":"14","author":"Klinglmayr","year":"2012","journal-title":"New J. Phys"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Gogolev, A., and Bettstetter, C. (2012). Self-Organizing Systems, Springer.","DOI":"10.1007\/978-3-642-19167-1"},{"key":"ref_26","first-page":"92","article-title":"One-dimensional uniform arrays that wash out finite islands","volume":"14","author":"Gacs","year":"1978","journal-title":"Problemy Peredachi Informacii"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Saks, M., and Zaharoglou, F. (1993, January 16\u201318). Wait-free k-set agreement is impossible: The topology of public knowledge, San Diego, CA, USA.","DOI":"10.1145\/167088.167122"},{"key":"ref_28","unstructured":"Andre, D., Bennett, F.H., and Koza, J.R. (1996, January 28\u201331). Discovery by genetic programming of a cellular automata rule that is better than any known rule for the majority classification problem, Stanford, CA, USA."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"5148","DOI":"10.1103\/PhysRevLett.74.5148","article-title":"No perfect two-state cellular automata for density classification exists","volume":"74","author":"Land","year":"1995","journal-title":"Phys. Rev. Lett. E"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/s00224-012-9386-3","article-title":"Stochastic cellular automata solutions to the density classification problem","volume":"53","author":"Fates","year":"2013","journal-title":"Theor. Comput Syst"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1145\/322186.322188","article-title":"Reaching agreement in the presence of faults","volume":"27","author":"Pease","year":"1980","journal-title":"J. ACM"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Gogolev, A., and Marcenaro, L. (2014, January 12\u201314). Density classification in asynchronous random networks with faulty nodes, Turin, Italy.","DOI":"10.1109\/PDP.2014.62"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Reka","year":"1999","journal-title":"Science"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"88701","DOI":"10.1103\/PhysRevLett.110.088701","article-title":"Opinions, conflicts, and consensus: modelling social dynamics in a collaborative environment","volume":"110","author":"Yasseri","year":"2013","journal-title":"Phys. Rev. Lett"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1017\/S0269964801154070","article-title":"Paths in the simple random graph and the Waxman graph","volume":"15","year":"2001","journal-title":"Probab. Eng. Inform. Sci"},{"key":"ref_36","first-page":"R2081","article-title":"Solution of the density classification problem with two cellular automata rules","volume":"55","year":"1997","journal-title":"Phys.l Rev. Lett"},{"key":"ref_37","first-page":"89","article-title":"Revisiting the edge of chaos: Evolving cellular automata to perform computations","volume":"7","author":"Mitchell","year":"1993","journal-title":"Complex Syst"},{"key":"ref_38","unstructured":"Juille, H., and Pollack, J.B. (1998, January 22\u201325). Coevolving the \u201cideal\u201d trainer: Application to the discovery of cellular automata rules, Wisconsin, WI, USA."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1023\/A:1015493820232","article-title":"A uniform white-noise model for fixed-point roundoff errors in digital systems","volume":"63","author":"Vladimirov","year":"2002","journal-title":"Automat. Rem. Cont"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/16\/5\/2820\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:11:40Z","timestamp":1760217100000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/16\/5\/2820"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,5,21]]},"references-count":39,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2014,5]]}},"alternative-id":["e16052820"],"URL":"https:\/\/doi.org\/10.3390\/e16052820","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2014,5,21]]}}}