Lock-free data structures

Tim Harris

Through careful design and implementation it's possible to build data structures that are safe for concurrent use without needing to manage locks or block threads. These "lock-free" data structures can increase performance by allowing extra concurrency and can improve robustness by avoiding problems such as priority inversion. However, many existing designs are extremely intricate and make unrealistic assumptions that render them effectively unusable.

In this talk I'll introduce the topic and present some of the work that we've been doing on building lock-free data structures that require only the primitives available on realistic processors. The resulting designs remain concise but intricate and may be worthwhile subjects for formal analysis.