{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:52:20Z","timestamp":1760151140611,"version":"build-2065373602"},"reference-count":50,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2022,2,25]],"date-time":"2022-02-25T00:00:00Z","timestamp":1645747200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In this work, we analyze the performance of a simple majority-rule protocol solving a fundamental coordination problem in distributed systems\u2014binary majority consensus\u2014in the presence of probabilistic message loss. Using probabilistic analysis for a large-scale, fully-connected, network of 2n agents, we prove that the Simple Majority Protocol (SMP) reaches consensus in only three communication rounds, with probability approaching 1 as n grows to infinity. Moreover, if the difference between the numbers of agents that hold different opinions grows at a rate of n, then the SMP with only two communication rounds attains consensus on the majority opinion of the network, and if this difference grows faster than n, then the SMP reaches consensus on the majority opinion of the network in a single round, with probability converging to 1 as exponentially fast as n\u2192\u221e. We also provide some converse results, showing that these requirements are not only sufficient, but also necessary.<\/jats:p>","DOI":"10.3390\/e24030333","type":"journal-article","created":{"date-parts":[[2022,2,27]],"date-time":"2022-02-27T20:46:17Z","timestamp":1645994777000},"page":"333","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Simple Majority Consensus in Networks with Unreliable Communication"],"prefix":"10.3390","volume":"24","author":[{"given":"Ran","family":"Tamir","sequence":"first","affiliation":[{"name":"Signal and Information Processing Laboratory, ETH Z\u00fcrich, 8092 Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ariel","family":"Livshits","sequence":"additional","affiliation":[{"name":"The Andrew and Erna Viterbi Faculty of Electrical and Computer Engineering, Technion-Israel Institute of Technology, Technion City, Haifa 3200003, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6492-6377","authenticated-orcid":false,"given":"Yonatan","family":"Shadmi","sequence":"additional","affiliation":[{"name":"The Andrew and Erna Viterbi Faculty of Electrical and Computer Engineering, Technion-Israel Institute of Technology, Technion City, Haifa 3200003, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,2,25]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Vuji\u010di\u0107, D., Jagodi\u0107, D., and Rani\u0107, S. (2018, January 21\u201323). Blockchain technology, bitcoin, and ethereum: A brief overview. Proceedings of the 2018 17th International Symposium Infoteh-Jahorina (Infoteh), IEEE, East Sarajevo, Bosnia.","DOI":"10.1109\/INFOTEH.2018.8345547"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/s00607-014-0399-4","article-title":"On construction of a distributed data storage system in cloud","volume":"98","author":"Yang","year":"2016","journal-title":"Computing"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Dingledine, R., Freedman, M.J., and Molnar, D. (2001). The free haven project: Distributed anonymous storage service. Designing Privacy Enhancing Technologies, Springer.","DOI":"10.1007\/3-540-44702-4_5"},{"key":"ref_4","first-page":"56","article-title":"Timestamps in message-passing systems that preserve the partial ordering","volume":"10","author":"Fidge","year":"1987","journal-title":"Proc. Aust. Comput. Sci. Conf."},{"key":"ref_5","unstructured":"Mattern, F. (1989). Virtual Time and Global States of Distributed Systems, Department of Computer Science, University of Kaiserslautem."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1145\/3303868","article-title":"A hitchhiker\u2019s guide to the blockchain universe","volume":"Volume 62","author":"Waldo","year":"2019","journal-title":"Communications of the ACM"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1109\/TNSM.2013.122613.130411","article-title":"Consistency as a service: Auditing cloud consistency","volume":"Volume 11","author":"Liu","year":"2014","journal-title":"Proceedings of the IEEE Transactions on Network and Service Management"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Kraska, T., Hentschel, M., Alonso, G., and Kossmann, D. (2009, January 24\u201328). Consistency rationing in the cloud: Pay only when it matters. Proceedings of the VLDB Endowment, Lyon, France.","DOI":"10.14778\/1687627.1687657"},{"key":"ref_9","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 (JACM)"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/s004460050067","article-title":"A simple and fast asynchronous consensus protocol based on a weak failure detector","volume":"12","author":"Hurfin","year":"1999","journal-title":"Distrib. Comput."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/s004460050032","article-title":"Early consensus in an asynchronous system with a weak failure detector","volume":"10","author":"Schiper","year":"1997","journal-title":"Distrib. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Aguilera, M.K. (2010). Stumbling over consensus research: Misunderstandings and issues. Replication, Springer.","DOI":"10.1007\/978-3-642-11294-2_4"},{"key":"ref_13","unstructured":"Borran, F., Prakash, R., and Schiper, A. (2022, January 14). Consensus Problem in Wireless Ad Hoc Networks: Addressing the Right Issues. Technical Reports. Available online: https:\/\/infoscience.epfl.ch\/record\/114619."},{"key":"ref_14","unstructured":"Zieli\u0144ski, P. (2007). Indirect Channels: A Bandwidth-Saving Technique for Fault-Tolerant Protocols, University of Cambridge, Computer Laboratory. Tech. Rep."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Guerraoui, R., Hurfinn, M., Most\u00e9faoui, A., Oliveira, R., Raynal, M., and Schiper, A. (2000). Consensus in asynchronous distributed systems: A concise guided tour. Advances in Distributed Systems, Springer.","DOI":"10.1007\/3-540-46475-1_2"},{"key":"ref_16","unstructured":"Tanenbaum, A.S., and Wetherall, D. (2011). Computer Networks, Prentice Hall. [5th ed.]."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1883612.1883616","article-title":"The failure detector abstraction","volume":"43","author":"Freiling","year":"2011","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Gray, J.N. (1978). Notes on data base operating systems. Operating Systems, Springer.","DOI":"10.1007\/3-540-08755-9_9"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Fischer, M.J. (1983). The consensus problem in unreliable distributed systems (a brief survey). International Conference on Fundamentals of Computation Theory, Springer.","DOI":"10.1007\/3-540-12689-9_99"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1145\/1132863.1132867","article-title":"Consensus on transaction commit","volume":"31","author":"Gray","year":"2006","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"ref_21","unstructured":"Antoniadis, K., Guerraoui, R., Malkhi, D., and Seredinschi, D.-A. (2022, January 14). State Machine Replication Is More Expensive than Consensus; Technical Reports. Available online: https:\/\/infoscience.epfl.ch\/record\/256238."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1137\/S0097539795279463","article-title":"Atomic snapshots in o(nlogn) operations","volume":"27","author":"Attiya","year":"1998","journal-title":"SIAM J. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Lamport, L. (2019). Time, clocks, and the ordering of events in a distributed system. Concurrency: The Works of Leslie Lamport, ACM Books.","DOI":"10.1145\/3335772.3335934"},{"key":"ref_24","unstructured":"Lynch, N.A. (1996). Distributed Algorithms, Elsevier."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"917","DOI":"10.1145\/153724.153770","article-title":"Knowledge, probability, and adversaries","volume":"40","author":"Halpern","year":"1993","journal-title":"J. ACM (JACM)"},{"key":"ref_26","first-page":"385","article-title":"The electronic mail game: Strategic behavior under almost common knowledge","volume":"79","author":"Rubinstein","year":"1989","journal-title":"Am. Econ. Rev."},{"key":"ref_27","first-page":"92","article-title":"One-dimensional uniform arrays that wash out finite islands","volume":"14","author":"Kurdyumov","year":"1978","journal-title":"Probl. Peredachi Inform."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Mustafa, N.H., and Peke\u010d, A. (2001). Majority consensus and the local majority rule. International Colloquium on Automata, Languages, and Programming, Springer.","DOI":"10.1007\/3-540-48224-5_44"},{"key":"ref_29","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_30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2746347","article-title":"Distributed binary consensus in networks with disturbances","volume":"10","author":"Gogolev","year":"2015","journal-title":"ACM Trans. Auton. Adapt. Syst. (TAAS)"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1145\/320071.320076","article-title":"A majority consensus approach to concurrency control for multiple copy databases","volume":"4","author":"Thomas","year":"1979","journal-title":"ACM Trans. Database Syst. (TODS)"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Breitwieser, H., and Leszak, M. (1982, January 18\u201320). A distributed transaction processing protocol based on majority consensus. Proceedings of the First ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Ottawa, ON, Canada.","DOI":"10.1145\/800220.806701"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Kanrar, S., Chattopadhyay, S., and Chaki, N. (2016). A new hybrid mutual exclusion algorithm in the absence of majority consensus. Advanced Computing and Systems for Security, Springer.","DOI":"10.1007\/978-81-322-2653-6_14"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Mostofi, Y. (2007, January 12\u201314). Binary consensus with gaussian communication noise: A probabilistic approach. Proceedings of the 2007 46th IEEE Conference on Decision and Control, IEEE, New Orleans, LA, USA.","DOI":"10.1109\/CDC.2007.4434598"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Perron, E., Vasudevan, D., and Vojnovic, M. (2009, January 19\u201325). Using three states for binary consensus on complete graphs. Proceedings of the IEEE INFOCOM 2009, IEEE, Rio de Janeiro, Brazil.","DOI":"10.1109\/INFCOM.2009.5062181"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/s11134-014-9397-7","article-title":"Probabilistic consensus via polling and majority rules","volume":"78","author":"Cruise","year":"2014","journal-title":"Queueing Syst."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1240","DOI":"10.1109\/PROC.1978.11114","article-title":"Sift: Design and analysis of a fault-tolerant computer for aircraft control","volume":"66","author":"Wensley","year":"1978","journal-title":"Proc. IEEE"},{"key":"ref_38","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 (JACM)"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Santoro, N., and Widmayer, P. (1989). Time is not a healer. Annual Symposium on Theoretical Aspects of Computer Science, Springer.","DOI":"10.1007\/BFb0028994"},{"key":"ref_40","unstructured":"Padhye, J., Firoiu, V., Towsley, D., and Kurose, J. (September, January 31). Modeling tcp throughput: A simple model and its empirical validation. Proceedings of the ACM SIGCOMM\u201998 conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, Vancouver, BC, Canada."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1109\/COMST.2005.1610546","article-title":"A survey and comparison of peer-to-peer overlay network schemes","volume":"7","author":"Lua","year":"2005","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.dam.2014.07.026","article-title":"Global majority consensus by local majority polling on graphs of a given degree sequence","volume":"180","author":"Abdullah","year":"2015","journal-title":"Discret. Appl. Math."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"G\u00e4rtner, B., and Zehmakan, A.N. (2018, January 16\u201319). Majority model on random regular graphs. Proceedings of the Latin American Symposium on Theoretical Informatics, Buenos Aires, Argentina.","DOI":"10.1007\/978-3-319-77404-6_42"},{"key":"ref_44","first-page":"20:1","article-title":"Reaching a consensus on random networks: The power of few. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2020)","volume":"176","author":"Tran","year":"2020","journal-title":"Leibniz Int. Proc. Inform."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1002\/rsa.20970","article-title":"Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs","volume":"57","author":"Fountoulakis","year":"2020","journal-title":"Random Struct. Algorithms"},{"key":"ref_46","unstructured":"Durrett, R. (1996). Probability: Theory and Examples, Cambridge University Press. [2nd ed.]."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Billingsley, P. (1999). Convergence of Probability Measures, John Wiley & Sons Inc.. [2nd ed.].","DOI":"10.1002\/9780470316962"},{"key":"ref_48","first-page":"299","article-title":"Information-type measures of difference of probability distributions and indirect observations","volume":"2","year":"1967","journal-title":"Stud. Sci. Math. Hung."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1109\/TIT.1967.1053968","article-title":"A lower bound for discrimination information in terms of variation","volume":"13","author":"Kullback","year":"1967","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"5973","DOI":"10.1109\/TIT.2016.2603151","article-title":"f-divergence inequalities","volume":"62","author":"Sason","year":"2016","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/3\/333\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:27:50Z","timestamp":1760135270000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/24\/3\/333"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,25]]},"references-count":50,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2022,3]]}},"alternative-id":["e24030333"],"URL":"https:\/\/doi.org\/10.3390\/e24030333","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2022,2,25]]}}}