Association for Computing Machinery
The linked-list data structure is fundamental and ubiquitous. Lock-free versions of the linked-list are well known. However, the existence of a practical wait-free linked-list has been open. In this paper, the authors designed such a linked-list. To achieve better performance, they have also extended this design using the fast-path-slow-path methodology. The resulting implementation achieves performance which is competitive with that of Harris's lock-free list, while still guaranteeing non-starvation via wait-freedom. They have also developed a proof for the correctness and the wait-freedom of their design.