Generalized Compare-and-Swap and Space-Efficient Universal Constructions for the Infinite-Arrival Model
This work addresses the problem of space-efficient universal constructions for concurrent systems with unknown and potentially infinite process participation, offering the first such solutions.
The paper introduces GCAS, a generalization of compare-and-swap, and presents two space-efficient wait-free universal constructions for the infinite-arrival model, achieving linear space complexity in the number of participating processes and point contention, respectively.
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.