Strong Linearizability without Compare&Swap: The Case of Bags
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915700078018560 |
|---|---|
| author | Ellen, Faith Sela, Gal |
| author_facet | Ellen, Faith Sela, Gal |
| contents | Because strongly-linearizable objects provide stronger guarantees than linearizability, they serve as valuable building blocks for the design of concurrent data structures. Yet, many objects that have linearizable implementations from base objects weaker than compare&swap objects do not have strongly-linearizable implementations from the same base objects. We focus on one such object: the bag, a multiset from which processes can take unspecified elements.
We present the first lock-free, strongly-linearizable implementation of a bag from interfering objects (specifically, registers, and test&set objects). This may be surprising, since there are provably no such implementations of stacks or queues.
Since a bag can contain arbitrarily many elements, an unbounded amount of space must be used to implement it. Hence, it makes sense to also consider a bag with a bound on its capacity. However, like stacks and queues, a bag with capacity $b$ shared by more than $2b$ processes has no lock-free, strongly-linearizable implementation from interfering objects. If we further restrict a bounded bag so that only one process can insert into it, we are able to obtain a lock-free, strongly-linearizable implementation from $O(b + n)$ interfering objects, where $n$ is the number of processes.
Our goal is to understand the circumstances under which strongly-linearizable implementations of bags exist and, more generally, to understand the power of interfering objects. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19365 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Strong Linearizability without Compare&Swap: The Case of Bags Ellen, Faith Sela, Gal Distributed, Parallel, and Cluster Computing Data Structures and Algorithms Because strongly-linearizable objects provide stronger guarantees than linearizability, they serve as valuable building blocks for the design of concurrent data structures. Yet, many objects that have linearizable implementations from base objects weaker than compare&swap objects do not have strongly-linearizable implementations from the same base objects. We focus on one such object: the bag, a multiset from which processes can take unspecified elements. We present the first lock-free, strongly-linearizable implementation of a bag from interfering objects (specifically, registers, and test&set objects). This may be surprising, since there are provably no such implementations of stacks or queues. Since a bag can contain arbitrarily many elements, an unbounded amount of space must be used to implement it. Hence, it makes sense to also consider a bag with a bound on its capacity. However, like stacks and queues, a bag with capacity $b$ shared by more than $2b$ processes has no lock-free, strongly-linearizable implementation from interfering objects. If we further restrict a bounded bag so that only one process can insert into it, we are able to obtain a lock-free, strongly-linearizable implementation from $O(b + n)$ interfering objects, where $n$ is the number of processes. Our goal is to understand the circumstances under which strongly-linearizable implementations of bags exist and, more generally, to understand the power of interfering objects. |
| title | Strong Linearizability without Compare&Swap: The Case of Bags |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2411.19365 |