A Wait-Free Queue as Fast as Fetch-and-Add
📜 Abstract
We present a new method for constructing lock-free and wait-free concurrent data-structures that is based on multi-word synchronization, without increasing the time-complexity for access. In particular, we describe a practical and potentially optimal implementation of a concurrent wait-free queue which has both practical efficiency and theoretical guarantees with respect to wait-freedom. Experimental results show comparable efficiency against the fastest known lock-free implementations on realistic computer architectures. The overall results seem to suggest that the presented method could be useful as a general tool for constructing lock-free and wait-free data-structures.
✨ Summary
This paper introduces an innovative method for building concurrent wait-free data structures, focusing on a queue implementation. The authors propose a technique that uses multi-word synchronization, aiming to deliver both practical efficiency and theoretical guarantees for wait-freedom without escalating time complexity. Notably, their proposed queue competes effectively against state-of-the-art lock-free implementations on common computing architectures. However, despite the paper’s promising approach and experimental validation, it appears the work has not significantly influenced subsequent research or industry practices. Searches for further references or citations in industry or academia did not yield notable mentions of this specific paper. The concepts presented, however, align with ongoing interests in optimizing concurrent data structures and could quietly inform similar developments and improvements in wait-free and lock-free design ideas.