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.11
URN: urn:nbn:de:0030-drops-148131
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14813/
Bédin, Denis ;
Lépine, François ;
Mostéfaoui, Achour ;
Perez, Damien ;
Perrin, Matthieu
Wait-Free CAS-Based Algorithms: The Burden of the Past
Abstract
Herlihy proved that CAS is universal in the classical computing system model composed of an a priori known number of processes. This means that CAS can implement, together with reads and writes, any object with a sequential specification. For this, he proposed the first universal construction capable of emulating any data structure. It has recently been proved that CAS is still universal in the infinite arrival computing model, a model where any number of processes can be created on the fly (e.g. multi-threaded systems). In this paper, we prove that CAS does not allow to implement wait-free and linearizable visible objects in the infinite model with a space complexity bounded by the number of active processes (i.e. ones that have operations in progress on this object). This paper also shows that this lower bound is tight, in the sense that this dependency can be made as low as desired (e.g. logarithmic) by proposing a wait-free and linearizable universal construction, using the compare-and-swap operation, whose space complexity in the number of ever issued operations is defined by a parameter that can be linked to any unbounded function.
BibTeX - Entry
@InProceedings{bedin_et_al:LIPIcs.DISC.2021.11,
author = {B\'{e}din, Denis and L\'{e}pine, Fran\c{c}ois and Most\'{e}faoui, Achour and Perez, Damien and Perrin, Matthieu},
title = {{Wait-Free CAS-Based Algorithms: The Burden of the Past}},
booktitle = {35th International Symposium on Distributed Computing (DISC 2021)},
pages = {11:1--11:15},
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/14813},
URN = {urn:nbn:de:0030-drops-148131},
doi = {10.4230/LIPIcs.DISC.2021.11},
annote = {Keywords: Compare-And-Swap, Concurrent Object, Infinite arrival model, Linearizability, Memory complexity, Multi-Threaded Systems, Shared-Memory, Universality, Wait-freedom}
}
|
Keywords: |
|
Compare-And-Swap, Concurrent Object, Infinite arrival model, Linearizability, Memory complexity, Multi-Threaded Systems, Shared-Memory, Universality, Wait-freedom |
|
Collection: |
|
35th International Symposium on Distributed Computing (DISC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.10.2021 |
