Lock-Free and Wait-Free Progress Guarantees¶

Lock-free algorithms guarantee that some thread always makes progress (even if others stall); wait-free algorithms guarantee every thread makes progress within bounded steps. Both avoid deadlock by construction but are harder to design and verify than lock-based code.

Tension Addressed¶

Simplicity vs. Scalability, Safety vs. Liveness

Recognizable As¶

Algorithms using CAS loops without locks, data structures advertised as "lock-free" or "wait-free," code paths that can't block on external conditions. Often found in performance-critical paths like concurrent queues.

Canonical Sources¶

Herlihy, "Wait-Free Synchronization" (1991); Michael & Scott, "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms" (1996)

Transfers To¶

Real-time systems (bounded response), high-frequency trading, operating system kernels