Lock-Free vs Wait-Free Guarantees
What You'll Learn
You'll understand the precise difference between lock-free, wait-free, and obstruction-free progress guarantees in concurrent programming.
Progress Guarantees Explained
When designing concurrent algorithms, we make different progress guarantees about how threads advance toward completion:
Lock-Free Guarantee
A lock-free algorithm guarantees that at least one thread in the system makes progress within a finite number of steps. The system as a whole never gets stuck, but individual threads might starve—repeatedly retrying while others succeed.
Analogy: A busy coffee shop where at least one customer always gets served, even if some unlucky customers keep getting cut in line.
Wait-Free Guarantee
A wait-free algorithm guarantees that every thread completes its operation within a bounded number of its own steps, regardless of what other threads do. No thread can be indefinitely delayed by others.
Analogy: A coffee shop with numbered tickets—every customer is guaranteed service in a predictable timeframe.
Obstruction-Free Guarantee
The weakest guarantee: a thread makes progress only if it runs in isolation (no contention). If other threads interfere, no guarantees exist.
Why It Matters
- Lock-free uses atomic operations like compare-and-swap in retry loops. Fast in practice, but theoretically allows starvation
- Wait-free often requires complex helping mechanisms where threads assist each other. Slower but provides fairness
- Most "lock-free" data structures you've seen (stacks, queues) are lock-free but not wait-free
The choice involves trading theoretical guarantees against practical performance and implementation complexity.
Key Takeaway: Lock-free guarantees system-wide progress (some thread succeeds), while wait-free guarantees per-thread progress (every thread succeeds); wait-free is stronger but harder to implement.