2014/11/04 by Dan Alistarh, Rati Gelashvili, Alistarh, Dan +3 · 1 voice · 1 citation
Computer Science · Mathematics · #Adversary #Asynchronous communication #Binary logarithm #Combinatorics #Complement (music) #Computer network #Computer science #Computer security #Cryptography and Data Security #Discrete mathematics #Distributed systems and fault tolerance #Economics #Leader election #Mathematics #Omega #Optimization and Search Problems #Point (geometry) #Task (project management) #Theoretical computer science #Tournament #Upper and lower bounds #cs.DC
paper · pdf · doi:10.48550/arxiv.1411.1001
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2014/11/04 · arxiv created 2015/02/15 · arxiv updated 2015/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.