Almost Logarithmic-Time Space Optimal Leader Election in Population Protocols
- Submitting institution
-
The University of Liverpool
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 15782
- Type
- E - Conference contribution
- DOI
-
10.1145/3323165.3323178
- Title of conference / published proceedings
- The 31st ACM Symposium on Parallelism in Algorithms and Architectures
- First page
- 93
- Volume
- -
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- June
- Year of publication
- 2019
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
-
- Citation count
- 4
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- This paper studies the fundamental problem of leader election in population protocols, a model of Angluin et al (Distributed Computing 2006) that won the Dijkstra Prize in Distributed Computing in 2020. This solves an open problem from the survey of Elsaesser and Radzik (EATCS Bulletin 2018), and has led to follow-up work, for example, the paper of Berenbrink et al (STOC'20) that presents a fine-tuned variant of our leader election protocol.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -