There are three levels of progress guarantees for non-blocking data structures. A concurrent object is:
- obstruction-free if a thread can perform an arbitrary operation on the object in a finite number of steps when it executes in isolation,
- lock-free if some thread performing an arbitrary operation on the object will complete in a finite number of steps, or
- wait-free if every thread can perform an arbitrary operation on the object in a finite number of steps.
Wait-freedom is the strongest progress guarantee; it rules out the possibility of starvation for all threads. Wait-free data structures are particularly desirable for mission critical applications that have real-time constraints, such as those used by cyber-physical systems.