Course contentsShow
← Computer Science
Lesson 2575 of 2,87257. Concurrency FundamentalsFree lesson

Lock-Free vs Wait-Free Guarantees

Distinguishing lock-free (system-wide progress) from wait-free (per-thread progress) and obstruction-free guarantees.

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.