New GCAS primitive promises space-efficient concurrency for infinite threads

A team of distributed systems researchers led by Vassos Hadzilacos, Myles Thiessen, and Sam Toueg has published a paper introducing GCAS, a generalized version of the classic compare-and-swap (CAS) primitive. While CAS atomically compares an object to an expected value and swaps only on equality, GCAS supports parameterized comparators from the set {<, =, >}. This small change dramatically expands the expressiveness of concurrent data structures without sacrificing atomicity. The paper, now on arXiv, is the full version of a PODC 2026 paper and extends earlier work by the same authors.

The main contribution is two wait-free universal constructions tailored for the infinite-arrival model—where the number of participating processes is unbounded and unknown ahead of time. Wait-free universal constructions allow any concurrent object to be implemented from simpler primitives while guaranteeing that every thread completes in a finite number of steps, regardless of scheduling. The first construction achieves space complexity linear in the number of processes that have participated so far, a significant improvement over prior approaches that required space proportional to the maximum possible threads (potentially infinite). The second construction goes further: it achieves space complexity linear in the point contention—the maximum number of processes concurrently accessing a shared object—but assumes bounded concurrency. To enable this, the authors devised a novel memory recycling scheme that safely reuses memory in the infinite-arrival model. This recycling scheme may find broader use in other concurrent algorithms. These results represent the first wait-free universal constructions with such space efficiency in the infinite-arrival model, offering a path to more scalable distributed systems in environments like cloud computing or microservices where thread counts are unpredictable.