Queues are fundamental concurrent data structures, but despite years of research, even the state-of-the-art queues have poor scalability. This poor scalability occurs because of contended atomic read-modify-write (RMW) operations.

This paper makes a first step towards designing a {\em scalable} linearizable queue. We leverage hardware transactional memory (HTM) to design TxCAS, a scalable compare-and-set (CAS) primitive—despite HTM being considered to be effective mainly in uncontended scenarios.

Leveraging TxCAS’s scalability requires a queue design that does not blindly retry failed CASs. We thus apply TxCAS to the {\em baskets queue}, which steers enqueuers whose CAS fails into dedicated {\em basket} data structures. Coupled with a new, scalable basket algorithm, we obtain SBQ, the scalable baskets queue. At high concurrency levels, SBQ outperforms the fastest queue today by up to $1.6\times$.