Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.19237 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909055378784256 |
|---|---|
| author | Hadzilacos, Vassos Thiessen, Myles Toueg, Sam |
| author_facet | Hadzilacos, Vassos Thiessen, Myles Toueg, Sam |
| contents | We introduce GCAS, a natural generalization of the well-known compare-and-swap (CAS) object. Intuitively, GCAS just replaces the fixed equality test of CAS with a parametrized comparator chosen from $\{<, =, >\}$. To showcase the utility of GCAS, we present two space-efficient wait-free universal constructions for systems where the number of participating processes is unknown and may be infinite (the infinite-arrival model). The first has space-complexity linear in the number of processes that have participated so far, while the second has space-complexity linear in the point contention but assumes bounded concurrency. To the best of our knowledge, these are the first wait-free universal constructions that achieve this space complexity in the infinite-arrival model. To achieve space complexity linear in the point contention, our second universal construction uses a novel memory recycling scheme that works in the infinite-arrival model with bounded concurrency. The ideas behind this recycling scheme could be of more general use. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_19237 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Generalized Compare-and-Swap and Space-Efficient Universal Constructions for the Infinite-Arrival Model Hadzilacos, Vassos Thiessen, Myles Toueg, Sam Distributed, Parallel, and Cluster Computing We introduce GCAS, a natural generalization of the well-known compare-and-swap (CAS) object. Intuitively, GCAS just replaces the fixed equality test of CAS with a parametrized comparator chosen from $\{<, =, >\}$. To showcase the utility of GCAS, we present two space-efficient wait-free universal constructions for systems where the number of participating processes is unknown and may be infinite (the infinite-arrival model). The first has space-complexity linear in the number of processes that have participated so far, while the second has space-complexity linear in the point contention but assumes bounded concurrency. To the best of our knowledge, these are the first wait-free universal constructions that achieve this space complexity in the infinite-arrival model. To achieve space complexity linear in the point contention, our second universal construction uses a novel memory recycling scheme that works in the infinite-arrival model with bounded concurrency. The ideas behind this recycling scheme could be of more general use. |
| title | Generalized Compare-and-Swap and Space-Efficient Universal Constructions for the Infinite-Arrival Model |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2605.19237 |