{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T14:00:28Z","timestamp":1766066428909,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,3,2]],"date-time":"2015-03-02T00:00:00Z","timestamp":1425254400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 2","award":["MOE2010-T2-2-082"],"award-info":[{"award-number":["MOE2010-T2-2-082"]}]},{"name":"Singapore MOE AcRF Tier 1","award":["MOE2012-T1-001-094"],"award-info":[{"award-number":["MOE2012-T1-001-094"]}]},{"name":"US-Israel Binational Science Foundation","award":["2008348"],"award-info":[{"award-number":["2008348"]}]},{"DOI":"10.13039\/501100001475","name":"Nanyang Technological University","doi-asserted-by":"crossref","award":["M58110000"],"award-info":[{"award-number":["M58110000"]}],"id":[{"id":"10.13039\/501100001475","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["894\/09"],"award-info":[{"award-number":["894\/09"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Singapore MoE Academic Research Fund (AcRF) Tier 2","award":["MOE2010-T2-2-082"],"award-info":[{"award-number":["MOE2010-T2-2-082"]}]},{"name":"Technion TASP center"},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"crossref","award":["2008348"],"award-info":[{"award-number":["2008348"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100006461","name":"Citi Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006461","id-type":"DOI","asserted-by":"crossref"}]},{"name":"I-CORE program of the Israel PBC and ISF","award":["4\/11"],"award-info":[{"award-number":["4\/11"]}]},{"name":"Israeli Ministry of Science and Technology"},{"name":"Israel Ministry of Science and Technology"},{"name":"Fault-tolerant Communication Complexity in Wireless Networks from the Singapore MoE AcRF-2"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,3,2]]},"abstract":"<jats:p>\n            Electing a leader is a fundamental task in distributed computing. In its\n            <jats:italic>implicit<\/jats:italic>\n            version, only the leader must know who is the elected leader. This article focuses on studying the message and time complexity of\n            <jats:italic>randomized<\/jats:italic>\n            implicit leader election in synchronous distributed networks. Surprisingly, the most \u201cobvious\u201d complexity bounds have not been proven for randomized algorithms. In particular, the seemingly obvious lower bounds of \u03a9(\n            <jats:italic>m<\/jats:italic>\n            ) messages, where\n            <jats:italic>m<\/jats:italic>\n            is the number of edges in the network, and \u03a9(\n            <jats:italic>D<\/jats:italic>\n            ) time, where\n            <jats:italic>D<\/jats:italic>\n            is the network diameter, are nontrivial to show for randomized (Monte Carlo) algorithms. (Recent results, showing that even \u03a9(\n            <jats:italic>n<\/jats:italic>\n            ), where\n            <jats:italic>n<\/jats:italic>\n            is the number of nodes in the network, is not a lower bound on the messages in complete networks, make the above bounds somewhat less obvious). To the best of our knowledge, these basic lower bounds have not been established even for deterministic algorithms, except for the restricted case of comparison algorithms, where it was also required that nodes may not wake up spontaneously and that\n            <jats:italic>D<\/jats:italic>\n            and\n            <jats:italic>n<\/jats:italic>\n            were not known. We establish these fundamental lower bounds in this article for the general case, even for randomized Monte Carlo algorithms. Our lower bounds are universal in the sense that they hold for all universal algorithms (namely, algorithms that work for all graphs), apply to every\n            <jats:italic>D<\/jats:italic>\n            ,\n            <jats:italic>m<\/jats:italic>\n            , and\n            <jats:italic>n<\/jats:italic>\n            , and hold even if\n            <jats:italic>D<\/jats:italic>\n            ,\n            <jats:italic>m<\/jats:italic>\n            , and\n            <jats:italic>n<\/jats:italic>\n            are known, all the nodes wake up simultaneously, and the algorithms can make any use of node's identities. To show that these bounds are tight, we present an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            ) messages algorithm. An\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>D<\/jats:italic>\n            ) time leader election algorithm is known. A slight adaptation of our lower bound technique gives rise to an \u03a9(\n            <jats:italic>m<\/jats:italic>\n            ) message lower bound for randomized broadcast algorithms.\n          <\/jats:p>\n          <jats:p>An interesting fundamental problem is whether both upper bounds (messages and time) can be reached simultaneously in the randomized setting for all graphs. The answer is known to be negative in the deterministic setting. We answer this problem partially by presenting a randomized algorithm that matches both complexities in some cases. This already separates (for some cases) randomized algorithms from deterministic ones. As first steps towards the general case, we present several universal leader election algorithms with bounds that tradeoff messages versus time. We view our results as a step towards understanding the complexity of universal leader election in distributed networks.<\/jats:p>","DOI":"10.1145\/2699440","type":"journal-article","created":{"date-parts":[[2015,3,3]],"date-time":"2015-03-03T14:08:19Z","timestamp":1425391699000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":57,"title":["On the Complexity of Universal Leader Election"],"prefix":"10.1145","volume":"62","author":[{"given":"Shay","family":"Kutten","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[{"name":"Nanyang Technological University and Brown University, Houston, TX"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[{"name":"The Weizmann Institute, Rehovot, Israel"}]},{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}]},{"given":"Amitabh","family":"Trehan","sequence":"additional","affiliation":[{"name":"Queen's University Belfast, Belfast, United Kingdom"}]}],"member":"320","published-online":{"date-parts":[[2015,3,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/645468.654755"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220023"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/983102"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28421"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/77600.77618"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v30:4"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1534"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7919"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33090-2_42"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958508"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0157-9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/77606.77610"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90103-5"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35668-1_24"},{"volume-title":"Proceedings of IFIP Congress. 155--160","year":"1977","author":"Lann G\u00e9rard Le","key":"e_1_2_1_15_1"},{"key":"e_1_2_1_16_1","unstructured":"Nancy Lynch. 1996. Distributed Algorithms. Morgan Kaufman Publishers Inc. San Francisco CA.   Nancy Lynch. 1996. Distributed Algorithms. Morgan Kaufman Publishers Inc. San Francisco CA."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"M. Mitzenmacher and E. Upfal. 2004. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.   M. Mitzenmacher and E. Upfal. 2004. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press.   Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1842733.1842736"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(90)90074-Y"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Nicola Santoro. 2006. Design and Analysis of Distributed Algorithms. (Wiley Series on Parallel and Distributed Computing). Wiley-Interscience.   Nicola Santoro. 2006. Design and Analysis of Distributed Algorithms. (Wiley Series on Parallel and Distributed Computing). Wiley-Interscience.","DOI":"10.1002\/0470072644"},{"key":"e_1_2_1_23_1","unstructured":"Gerard Tel. 1994. Introduction to Distributed Algorithms. Cambridge University Press New York.   Gerard Tel. 1994. Introduction to Distributed Algorithms. Cambridge University Press New York."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/601858.601861"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699440","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2699440","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:58Z","timestamp":1750227418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699440"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,3,2]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,3,2]]}},"alternative-id":["10.1145\/2699440"],"URL":"https:\/\/doi.org\/10.1145\/2699440","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2015,3,2]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}