Wait-freedom is described in the introduction. Quote:

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.

From the introduction:

> In this paper, we describe an algorithm to create a wait-free stack. A concurrent data structure is said to be wait-free if each operation is guaranteed to complete within a finite number of steps. In comparison, the data structure is said to be lock-free if at any point of time, at least one operation is guaranteed to complete in a finite number of steps. Lock-free programs will not have deadlocks but can have starvation, whereas wait-free programs are starvation free.