A wait-free data structure is lock-free and guarantees that every accessing thread completes an operation within a bounded number of steps, regardless of other threads’ behavior. section 7.1.3
Retrying compare-exchange
A compare-exchange loop with no bound on retries is not wait-free: clashes may force one thread to retry repeatedly while others progress. Wait-free designs require each operation to finish in a single pass, without one thread’s steps causing another operation to fail. section 7.1.3 section 7.1.2
Guaranteeing progress for every thread can make algorithms considerably more complex. Lock-free designs can enable concurrency and tolerate a thread dying mid-operation, but require careful handling of invariants, atomic modifications, and memory ordering. section 7.1.3 section 7.1.4
