License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2021.4
URN: urn:nbn:de:0030-drops-148063
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14806/
Alistarh, Dan ;
Gelashvili, Rati ;
Nadiradze, Giorgi
Lower Bounds for Shared-Memory Leader Election Under Bounded Write Contention
Abstract
This paper gives tight logarithmic lower bounds on the solo step complexity of leader election in an asynchronous shared-memory model with single-writer multi-reader (SWMR) registers, for both deterministic and randomized obstruction-free algorithms. The approach extends to lower bounds for deterministic and randomized obstruction-free algorithms using multi-writer registers under bounded write concurrency, showing a trade-off between the solo step complexity of a leader election algorithm, and the worst-case number of stalls incurred by a processor in an execution.
BibTeX - Entry
@InProceedings{alistarh_et_al:LIPIcs.DISC.2021.4,
author = {Alistarh, Dan and Gelashvili, Rati and Nadiradze, Giorgi},
title = {{Lower Bounds for Shared-Memory Leader Election Under Bounded Write Contention}},
booktitle = {35th International Symposium on Distributed Computing (DISC 2021)},
pages = {4:1--4:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-210-5},
ISSN = {1868-8969},
year = {2021},
volume = {209},
editor = {Gilbert, Seth},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14806},
URN = {urn:nbn:de:0030-drops-148063},
doi = {10.4230/LIPIcs.DISC.2021.4},
annote = {Keywords: Lower Bounds, Leader Election, Shared-Memory}
}
|
Keywords: |
|
Lower Bounds, Leader Election, Shared-Memory |
|
Collection: |
|
35th International Symposium on Distributed Computing (DISC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.10.2021 |
