The Taub Faculty of Computer Science Events and Talks

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. A wait-free data-structure is a structure in which each thread is guaranteed to finish each method in a bounded number of steps, regardless of contention and of the scheduling in the system. We describe a practical wait-free linked-list based on the lock-free linked-list algorithm of Harris. We have also extended this design to work in the fast-path-slow-path methodology in order to achieve a wait-free linked-list that performs comparably to the lock-free linked list. We have implemented this algorithm and measured its performance. It turns out that our implementation achieves performance that is competitive with that of Harris, while still guaranteeing non-starvation via wait-freedom.