How to elect a leader faster than a tournament Conference Paper

Author(s): Alistarh, Dan; Gelashvili, Rati; Vladu, Adrian V
Title: How to elect a leader faster than a tournament
Abstract: 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.
Keywords: lower bound; Randomized algorithms; Asynchronous; Leader election; Message complexity; Message-passing
Conference Title: PODC: Principles of Distributed Computing
Volume: 2015-July
Conference Dates: July 21 - 23, 2015
Conference Location: Donostia-San Sabastian; Spain
ISBN: 978-145033617-8
Publisher: ACM  
Date Published: 2015-07-21
Start Page: 365
End Page: 374
DOI: 10.1145/2767386.2767420
Notes: Support is gratefully acknowledged from the National Science Foundation under grants CCF-1217921, CCF-1301926, and IIS-1447786, the Department of Energy under grant ER26116/DE-SC0008923, and the Oracle and Intel corporations. The authors would like to thank Prof. Nir Shavit for ad- vice and encouragement during this work, and the anonymous reviewers for their very useful suggestions.
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work