---
res:
bibo_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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Dan
foaf_name: Alistarh, Dan
foaf_surname: Alistarh
- foaf_Person:
foaf_givenName: Rati
foaf_name: Gelashvili, Rati
foaf_surname: Gelashvili
- foaf_Person:
foaf_givenName: Adrian
foaf_name: Vladu, Adrian V
foaf_surname: Vladu
bibo_doi: 10.1145/2767386.2767420
bibo_volume: 2015-July
dct_date: 2015^xs_gYear
dct_publisher: ACM@
dct_title: How to elect a leader faster than a tournament@
...