Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

CSL Luncheon: Wait-Free Linked-Lists
event speaker icon
Shahar Timnat (CS, Technion)
event date icon
Thursday, 01.12.2011, 12:30
event location icon
Room 337-8 Taub Bld.
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.