[{"page":"365 - 374","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://doi.org/10.1145/2767386.2767420","open_access":"1"}],"date_updated":"2026-05-19T13:27:49Z","year":"2015","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","status":"public","author":[{"first_name":"Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X"},{"full_name":"Gelashvili, Rati","last_name":"Gelashvili","first_name":"Rati"},{"last_name":"Vladu","full_name":"Vladu, Adrian","first_name":"Adrian"}],"date_created":"2018-12-11T11:48:28Z","OA_place":"publisher","publisher":"Association for Computing Machinery","article_processing_charge":"No","title":"How to elect a leader faster than a tournament","oa_version":"Accepted Version","arxiv":1,"external_id":{"arxiv":["1411.1001"]},"fulldoi":"https://doi.org/10.1145/2767386.2767420","publication_status":"published","type":"conference","day":"21","doi":"10.1145/2767386.2767420","citation":{"ieee":"D.-A. Alistarh, R. Gelashvili, and A. Vladu, “How to elect a leader faster than a tournament,” in <i>Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing</i>, New York, NY, United States, 2015, pp. 365–374.","apa":"Alistarh, D.-A., Gelashvili, R., &#38; Vladu, A. (2015). How to elect a leader faster than a tournament. In <i>Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing</i> (pp. 365–374). New York, NY, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2767386.2767420\">https://doi.org/10.1145/2767386.2767420</a>","ama":"Alistarh D-A, Gelashvili R, Vladu A. How to elect a leader faster than a tournament. In: <i>Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2015:365-374. doi:<a href=\"https://doi.org/10.1145/2767386.2767420\">10.1145/2767386.2767420</a>","mla":"Alistarh, Dan-Adrian, et al. “How to Elect a Leader Faster than a Tournament.” <i>Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2015, pp. 365–74, doi:<a href=\"https://doi.org/10.1145/2767386.2767420\">10.1145/2767386.2767420</a>.","chicago":"Alistarh, Dan-Adrian, Rati Gelashvili, and Adrian Vladu. “How to Elect a Leader Faster than a Tournament.” In <i>Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing</i>, 365–74. Association for Computing Machinery, 2015. <a href=\"https://doi.org/10.1145/2767386.2767420\">https://doi.org/10.1145/2767386.2767420</a>.","short":"D.-A. Alistarh, R. Gelashvili, A. Vladu, in:, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2015, pp. 365–374.","ista":"Alistarh D-A, Gelashvili R, Vladu A. 2015. How to elect a leader faster than a tournament. Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 365–374."},"publication_identifier":{"isbn":["9781450336178"]},"scopus_import":"1","date_published":"2015-07-21T00:00:00Z","publist_id":"6875","publication":"Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing","abstract":[{"text":"The problem of electing a leader from among n contenders is one of the fundamental questions in distributed computing. In its simplest formulation, the task is as follows: given n processors, all participants must eventually return a win or lose indication, such that a single contender may win. Despite a considerable amount of work on leader election, the following question is still open: can we elect a leader in an asynchronous fault-prone system faster than just running a Θ(log n)-time tournament, against a strong adaptive adversary? In this paper, we answer this question in the affirmative, improving on a decades-old upper bound. We introduce two new algorithmic ideas to reduce the time complexity of electing a leader to O(log∗ n), using O(n2) point-to-point messages. A non-trivial application of our algorithm is a new upper bound for the tight renaming problem, assigning n items to the n participants in expected O(log2 n) time and O(n2) messages. We complement our results with lower bound of Ω(n2) messages for solving these two problems, closing the question of their message complexity.","lang":"eng"}],"acknowledgement":"Support is gratefully acknowledged from the National Science Foundation under grants CCF-1217921, CCF-1301926,\r\nand  IIS-1447786,  the  Department  of  Energy  under  grant\r\nER26116/DE-SC0008923,  and the  Oracle  and Intel  corporations.\r\nThe authors would like to thank Prof.  Nir Shavit for ad-\r\nvice and encouragement during this work,  and the anonymous reviewers for their very useful suggestions.","quality_controlled":"1","oa":1,"month":"07","_id":"783","extern":"1","OA_type":"free access","conference":{"name":"PODC: Principles of Distributed Computing","end_date":"2015-07-23","location":"New York, NY, United States","start_date":"2015-07-21"}}]