Designing lock-free data structures

If at least one thread is guaranteed to make progress, then we say it's a lock-free function. Compared to lock-based functions, where one thread can block another and they both might wait for some condition before making progress, a lock-free state ensures progress is made by at least one of the threads. We say that algorithms and data structures using data synchronization primitives are blocking, that is, a thread is suspended until another thread performs an action. That means the thread can't make progress until the block is removed (typically, unlocking a mutex). Our interest lies in data structures and algorithms that don't use blocking functions. We call some of them lock-free, although we should make a distinction between the types of non-blocking algorithms and data structures.

...