Concurrent algorithms are classified by their progress guarantee: blocking, obstruction-free, lock-free and wait-free. Define each of these terms precisely and explain what practical difference the guarantee makes when a thread is preempted, paused or delayed.

middlemust knowfreq 50%

answer

Blocking: one stall stops everyone
Obstruction-free: progress if run alone → livelock possible
Lock-free: some thread progresses → starvation possible
Wait-free: every thread bounded in its own steps
Guarantee is about scheduling, not speed

basics

~20 s

Blocking: one stalled thread can stop everyone. Obstruction-free: a thread completes if it eventually runs without interference. Lock-free: some thread always completes in a bounded number of system steps, so the system as a whole progresses. Wait-free: every thread completes within a bounded number of its own steps.

solid answer

~50 s

They are scheduler-independence guarantees, not speed claims.

Blocking — progress depends on other threads. If the thread holding a mutex is preempted, paged out or killed, everyone waiting is stuck indefinitely.
Obstruction-free — a thread finishes if it runs long enough in isolation. Concurrent threads may abort each other's attempts forever, so livelock is possible; usually paired with backoff.
Lock-free — after any finite number of steps, some thread has completed an operation. The system never stalls, but an individual thread can starve, retrying while others succeed.
Wait-free — every thread finishes its operation within a bound on its own steps, independent of what other threads do. Strongest, and the only one that bounds per-thread latency.

Each is strictly stronger than the previous. The distinction matters exactly where arbitrary delays are possible: preemption, page faults, priority inversion, garbage-collection pauses, or a thread being killed. Nothing here says lock-free is faster — under contention it often is not.

They are scheduler-independence guarantees, not speed claims. - **Blocking** — progress depends on other threads. If the thread holding a mutex is preempted, paged out or killed, everyone waiting is stuck indefinitely. - **Obstruction-free** — a thread finishes if it runs long enough in isolation. Concurrent threads may abort each other's attempts forever, so livelock is possible; usually paired with backoff. - **Lock-free** — after any finite number of steps, *some* thread has completed an operation. The system never stalls, but an individual thread can starve, retrying while others succeed. - **Wait-free** — every thread finishes its operation within a bound on *its own* steps, independent of what other threads do. Strongest, and the only one that bounds per-thread latency. Each is strictly stronger than the previous. The distinction matters exactly where arbitrary delays are possible: preemption, page faults, priority inversion, garbage-collection pauses, or a thread being killed. Nothing here says lock-free is faster — under contention it often is not.

code

text · 6 lines

text

repeat:
    old = read(shared)
    new = f(old)
    if compare_and_set(shared, old, new): return   // success
    // failure means someone else succeeded -> system progressed
// one specific thread may lose every race forever -> not wait-free

go deeper

for a junior

Be able to state the four names in order of strength and say that blocking algorithms can stall everyone if one thread stops.

for a middle

Define each precisely, distinguish system-wide progress (lock-free) from per-thread bounds (wait-free), and know that a retry loop is lock-free.

for a senior

Connect the guarantees to real delay sources — preemption, page faults, priority inversion, runtime pauses — and explain why non-blocking does not imply faster.

for a principal

Choose the weakest guarantee that meets the latency and fault requirements, and justify the complexity cost of anything stronger against measured tail latency.

What is actually being guaranteed

A progress guarantee answers one question: what must be true about the scheduler for my operation to finish? It is a statement about liveness under adversarial scheduling, and it is orthogonal to both performance and correctness (safety). An algorithm can be lock-free and slow; it can be blocking and fast; it can be wait-free and wrong.

The standard hierarchy, from weakest to strongest:

Blocking. Progress depends on other threads continuing to run. Any mutex-based algorithm is blocking: if the lock holder is descheduled at the worst moment, every waiter stalls for as long as that thread is off the CPU — potentially forever if it crashes or is killed while holding the lock. Related failure modes are deadlock (a cycle of waits), priority inversion (a low-priority holder is preempted while a high-priority thread waits) and convoying.

Obstruction-free. A thread completes its operation in a bounded number of its own steps provided it eventually executes in isolation — no other thread interferes for long enough. This rules out deadlock but not livelock: two threads can repeatedly abort each other and neither finishes, while the system does no useful work. It is the weakest non-blocking condition and is normally made practical with randomised exponential backoff or a contention manager. Some software transactional memory designs sit here.

Lock-free. In any execution, after a finite number of total steps, some thread completes an operation. The system as a whole always makes progress, whatever the scheduler does to any individual thread. Deadlock and livelock are both impossible. What is not guaranteed is fairness: a specific unlucky thread can fail its retry loop indefinitely while others succeed, so lock-free bounds throughput-style progress, not per-thread latency. The canonical shape is a retry loop — read a snapshot, compute a new value, atomically install it if nothing changed, otherwise retry — which is lock-free precisely because a failed attempt implies that some other attempt succeeded.

Wait-free. Every thread completes its operation within a bound on the number of steps it itself takes, regardless of the speed, stalling or failure of other threads. This is the only class that bounds worst-case per-thread latency, so it is what hard real-time and interrupt-context code want. Refinements exist: bounded wait-free fixes a constant bound, and population-oblivious wait-free means the bound does not depend on the number of threads. Wait-freedom is usually achieved by helping: before completing its own operation, a thread finishes any operation it finds in progress by another thread, typically by publishing an operation descriptor other threads can pick up. Universal constructions show any sequential object can be made wait-free given a sufficiently strong primitive, but the constant factors are usually poor, which is why wait-free structures are rare in general-purpose code and common in specialised ones (single-producer queues, some counters and buffers).

Common confusions worth naming

"No locks in the code" does not mean lock-free. A spin loop waiting for a flag another thread must set is a lock wearing different clothes: if that thread is preempted, no one progresses. Likewise a retry loop that can only succeed after some other specific thread acts is blocking. The classification is about the guarantee, not about which keywords appear.

Lock-free is not "faster". Under low contention, a well-implemented mutex is very cheap, and modern implementations spin briefly before parking. Under high contention, lock-free retry loops waste work and still serialise on the hardware ownership of the contended memory. The reasons to choose non-blocking algorithms are tolerance of preemption and failure, bounded tail latency, and usability from contexts where blocking is forbidden — not raw throughput.

The guarantees are strictly nested. Wait-free implies lock-free implies obstruction-free. So describing an algorithm as lock-free is an upper claim on what it does not promise as much as a claim about what it does.

How to use this in an interview

Give the four definitions crisply, emphasise that the difference only shows up when a thread is arbitrarily delayed, and give one concrete scenario — a thread preempted mid-operation, or a page fault, or a thread killed — showing how each class behaves. Then state the practical position: choose the weakest guarantee that meets the requirement, since stronger guarantees cost complexity and constant factors.

## What is actually being guaranteed A progress guarantee answers one question: *what must be true about the scheduler for my operation to finish?* It is a statement about liveness under adversarial scheduling, and it is orthogonal to both performance and correctness (safety). An algorithm can be lock-free and slow; it can be blocking and fast; it can be wait-free and wrong. The standard hierarchy, from weakest to strongest: **Blocking.** Progress depends on other threads continuing to run. Any mutex-based algorithm is blocking: if the lock holder is descheduled at the worst moment, every waiter stalls for as long as that thread is off the CPU — potentially forever if it crashes or is killed while holding the lock. Related failure modes are deadlock (a cycle of waits), priority inversion (a low-priority holder is preempted while a high-priority thread waits) and convoying. **Obstruction-free.** A thread completes its operation in a bounded number of its own steps *provided it eventually executes in isolation* — no other thread interferes for long enough. This rules out deadlock but not **livelock**: two threads can repeatedly abort each other and neither finishes, while the system does no useful work. It is the weakest non-blocking condition and is normally made practical with randomised exponential backoff or a contention manager. Some software transactional memory designs sit here. **Lock-free.** In any execution, after a finite number of total steps, *some* thread completes an operation. The system as a whole always makes progress, whatever the scheduler does to any individual thread. Deadlock and livelock are both impossible. What is *not* guaranteed is fairness: a specific unlucky thread can fail its retry loop indefinitely while others succeed, so lock-free bounds throughput-style progress, not per-thread latency. The canonical shape is a retry loop — read a snapshot, compute a new value, atomically install it if nothing changed, otherwise retry — which is lock-free precisely because a failed attempt implies that some other attempt succeeded. **Wait-free.** Every thread completes its operation within a bound on the number of steps it itself takes, regardless of the speed, stalling or failure of other threads. This is the only class that bounds worst-case per-thread latency, so it is what hard real-time and interrupt-context code want. Refinements exist: *bounded* wait-free fixes a constant bound, and *population-oblivious* wait-free means the bound does not depend on the number of threads. Wait-freedom is usually achieved by **helping**: before completing its own operation, a thread finishes any operation it finds in progress by another thread, typically by publishing an operation descriptor other threads can pick up. Universal constructions show any sequential object can be made wait-free given a sufficiently strong primitive, but the constant factors are usually poor, which is why wait-free structures are rare in general-purpose code and common in specialised ones (single-producer queues, some counters and buffers). ## Common confusions worth naming **"No locks in the code" does not mean lock-free.** A spin loop waiting for a flag another thread must set is a lock wearing different clothes: if that thread is preempted, no one progresses. Likewise a retry loop that can only succeed after some other specific thread acts is blocking. The classification is about the guarantee, not about which keywords appear. **Lock-free is not "faster".** Under low contention, a well-implemented mutex is very cheap, and modern implementations spin briefly before parking. Under high contention, lock-free retry loops waste work and still serialise on the hardware ownership of the contended memory. The reasons to choose non-blocking algorithms are tolerance of preemption and failure, bounded tail latency, and usability from contexts where blocking is forbidden — not raw throughput. **The guarantees are strictly nested.** Wait-free implies lock-free implies obstruction-free. So describing an algorithm as lock-free is an upper claim on what it does *not* promise as much as a claim about what it does. ## How to use this in an interview Give the four definitions crisply, emphasise that the difference only shows up when a thread is arbitrarily delayed, and give one concrete scenario — a thread preempted mid-operation, or a page fault, or a thread killed — showing how each class behaves. Then state the practical position: choose the weakest guarantee that meets the requirement, since stronger guarantees cost complexity and constant factors.

Give a concrete way a lock-free algorithm can starve one thread, and say why the algorithm is still called lock-free.
In a compare-and-set retry loop, a slow thread can have its snapshot invalidated by faster threads on every attempt and never commit. It is still lock-free because each of its failures is caused by another thread succeeding, so the system as a whole keeps completing operations. Lock-freedom is a system-wide progress property; per-thread bounds require wait-freedom.
If wait-free is the strongest guarantee, why is most production code not wait-free?
Wait-freedom usually requires helping schemes in which threads announce operations in descriptors and complete each other's work, which adds memory traffic, allocation and substantial complexity. The constant factors are typically worse than a lock-free or lock-based version, and the extra guarantee only pays off when per-thread worst-case latency genuinely matters, such as real-time deadlines or code that cannot block. Most systems are better served by the simplest structure that meets their latency target.

A single-lane bridge with a gate key is blocking — lose the keyholder and traffic stops. A roundabout is lock-free: someone is always getting through, though one unlucky driver may circle for a while. A ticketed queue where every arrival is served within a fixed number of turns is wait-free.

saying these in an interview costs you the question

Equating lock-free with faster, or with simply not calling a lock API
Claiming lock-free means no thread can starve
Saying wait-free and lock-free are the same thing
Believing a spin-wait on another thread's flag is non-blocking
Treating the progress guarantee as a correctness property rather than a liveness one

Concurrent algorithms are classified by their progress guarantee: blocking, obstruction-free, lock-free and wait-free. Define each of these terms precisely and explain what practical difference the guarantee makes when a thread is preempted, paused or delayed.

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

What is actually being guaranteed

Common confusions worth naming

How to use this in an interview

▾common follow-ups2 questions

▾analogy~20 s

▾red flags5 flags

§ context

▾related questions7 questions

▾related topics4 topics

What is actually being guaranteed

Common confusions worth naming

How to use this in an interview

answer

go deeper

context