Disclaimer: I haven't implemented this yet, this is based on skimming the paper and what I know about lock-free structures.
Your run-of-the-mill lock-free code basically operates under the premise of "keep trying until something sticks." For example, with only CompareAndSwap you can implement lock-free bit-field operations as:
do {
oldValue = Read(variable);
newValue = oldValue | 0x01;
} while ((CAS(variable, oldValue, newValue) & 0x01) == 0);
You can see that we have to keep looping until the new value (which includes the flag) "sticks." The race is allowed to occur between the Read() and the CAS(), where CAS() is used to determine if a race occurred. CAS will check the current value of the address and update it only if it matches (as an atomic operation on the CPU). The worst case here is O(∞) - if another thread always wins, this loop will never exit. The run-of-the-mill lock-free stack code looks quite similar to this (you're basically updating the head until it sticks). This means that in certain circumstances, lock-free code can actually be slower. I have run into this myself[1]: that code uses locks because I couldn't figure out a faster lock-free implementation (that code is 30x faster than my best lock-free effort).
There are two operations on a stack: Push() and Pop(). Classically, these both compete to write the head (write-contention). The advantage with this algorithm is that only Push() competes to write the head so you're decreasing the probability of proving O(∞) with each Push(). Additionally, Pop() seems to be O(N) (where N = number of items in the stack) where-as classically that's also O(∞).
TL;DR Unless I'm misunderstanding wait-free (having never heard of that technical term before), it means eliminating a theoretically unbounded loop.
If you'd like to learn more I consider Jeff Preshing[2] as the authority figure on lock-free data structures. His articles are clear and could explain how these structures work to "ostensibly anyone." CPPCon also has at least one talk of his.
[1]: https://github.com/jcdickinson/AzXmpp/blob/master/src/AzXmpp...
[2]: http://preshing.com/