---
OA_place: publisher
OA_type: free access
_id: '783'
abstract:
- lang: eng
  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.'
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."
article_processing_charge: No
arxiv: 1
author:
- first_name: Dan-Adrian
  full_name: Alistarh, Dan-Adrian
  id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
  last_name: Alistarh
  orcid: 0000-0003-3650-940X
- first_name: Rati
  full_name: Gelashvili, Rati
  last_name: Gelashvili
- first_name: Adrian
  full_name: Vladu, Adrian
  last_name: Vladu
citation:
  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>'
  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>'
  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>.
  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.
  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.'
  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>.
  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.
conference:
  end_date: 2015-07-23
  location: New York, NY, United States
  name: 'PODC: Principles of Distributed Computing'
  start_date: 2015-07-21
date_created: 2018-12-11T11:48:28Z
date_published: 2015-07-21T00:00:00Z
date_updated: 2026-05-19T13:27:49Z
day: '21'
doi: 10.1145/2767386.2767420
extern: '1'
external_id:
  arxiv:
  - '1411.1001'
fulldoi: https://doi.org/10.1145/2767386.2767420
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1145/2767386.2767420
month: '07'
oa: 1
oa_version: Accepted Version
page: 365 - 374
publication: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing
publication_identifier:
  isbn:
  - '9781450336178'
publication_status: published
publisher: Association for Computing Machinery
publist_id: '6875'
quality_controlled: '1'
scopus_import: '1'
status: public
title: How to elect a leader faster than a tournament
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2015'
...