A Lazy Concurrent List-Based Set Algorithm
Steve Heller, Maurice P. Herlihy, Victor Luchangco, Mark J. Moir, William N. Scherer, Nir Shavit · Parallel Processing Letters · 2007
We present a novel “lazy” list-based implementation of a concurrent set object. It is based on an optimistic locking scheme for inserts and removes and includes a simple wait-free membership test. Our algorithm improves on the performance of all previous such algorithms.