Lock-free is not wait-free

Progress belongs to an operation and a model

A lock-free algorithm guarantees system-wide progress under its execution model: continuing activity cannot be held indefinitely behind one paused participant. That does not guarantee that a particular participant finishes its operation. A wait-free algorithm provides a stronger individual guarantee, expressed in the participant's own steps rather than the relative speed of others. Herlihy's paper makes this distinction foundational. I would retain the model in the explanation because neither term, by itself, promises a fixed number of elapsed microseconds on an oversubscribed operating system.

A thread that receives no CPU cannot complete even a trivial bounded algorithm. Conversely, a thread can execute indefinitely in a lock-free retry loop while other threads repeatedly succeed. These are different failures of the user's deadline: scheduler deprivation and algorithmic starvation. A latency-sensitive interface may need to address both. Calling the underlying primitive lock-free is useful information, but it is only one component of the argument that the whole operation will return within an acceptable time under the deployment's actual conditions.

References: [1] Maurice Herlihy: Wait-Free Synchronization

A compare-and-exchange loop shows the difference

Consider an illustrative counter update implemented with a load followed by strong compare-and-exchange. Worker A reads zero. Worker B changes zero to one before A attempts its replacement, so A fails. A then reads one, but B changes it to two before A retries. Repeating this schedule lets B complete operations while A continually loses. The system is making progress, and A is receiving execution time, yet A has no bound on its own retries. That is the distinction a throughput graph can hide.

The pseudocode uses mathematical integers to avoid distracting overflow semantics and a strong comparison to exclude spurious failure. A real fixed-width implementation must specify overflow and the atomic primitive's guarantees. The successful comparison is a natural linearization point for this simple counter operation, but linearizability and progress remain separate properties. The value can behave like a correct sequential counter while one caller experiences unbounded delay. Correct results for completed operations do not establish that every invocation receives a result.

increment():
  old = atomic_load(counter)
  loop:
    if strong_compare_exchange(counter, old, old + 1):
      return old + 1
    old = atomic_load(counter)

# A can repeatedly lose the comparison while B completes updates.

A primitive's guarantee does not compose automatically

Rust documents that its available atomic types are lock-free, while their operations are not guaranteed to be wait-free. Even a stronger primitive would not make an arbitrary composition wait-free. A surrounding retry loop, allocator, reclamation path or callback can introduce an unbounded dependency. I would examine the complete public operation, including uncommon paths. A queue push that performs a lock-free pointer update after calling a blocking allocator has a different contract from a preallocated operation that never invokes that allocator.

The same concern applies to logging and instrumentation. An allegedly nonblocking path can acquire a lock through an error logger or lazily initialize shared state on its first use. Those dependencies may be acceptable, but they should constrain the claim. I would distinguish steady-state inner-loop behaviour from initialization, exhaustion and teardown. An implementation can intentionally provide different guarantees for each. The problem is presenting the strongest property of one instruction as though it applies to every action reachable through the API.

References: [2] Rust: atomic types and portability

Memory reclamation is part of progress

A linked structure needs to decide when removed nodes can be reclaimed. Freeing a node while another participant might still read it is unsafe, so techniques such as hazard pointers, epochs or managed memory add their own obligations. A stalled participant can delay reclamation in some designs even when other operations continue completing. The algorithm may retain its logical progress property while memory grows until an operational limit is reached. I would include bounded-memory behaviour in the review rather than treating reclamation as unrelated cleanup.

Pointer reuse also creates the familiar ABA hazard: a location changes from one address to another and back to the original bit pattern, causing a comparison to miss intervening changes. A version tag can help only under an explicit wraparound and lifetime argument. It is not a substitute for proving that dereferences remain valid. This is another reason a short compare-and-exchange loop is rarely the whole algorithm. Visibility, object identity, reclamation and progress interact, and each deserves a separate statement of what the caller may rely on.

Helping can strengthen progress at a cost

One broad strategy for individual progress is to publish an operation description that other participants can help complete. The details are algorithm-specific, but the trade is intuitive: instead of repeatedly racing only for personal success, threads cooperate in advancing pending operations. That can require additional metadata, bounded participant assumptions and more complicated reclamation. I would not infer wait-freedom merely because an implementation contains a help function. The guarantee depends on a proof that a participant's operation cannot be bypassed indefinitely within the stated model.

A stronger progress property can also perform more work in common cases. If the product mainly needs high aggregate throughput with moderate contention, a simpler lock-free or even locked structure may be preferable. If an operation runs in a context where waiting behind a paused owner is unacceptable, the stronger guarantee may justify substantial complexity. The right choice starts with the failure that must be excluded. Selecting the most impressive term without that requirement risks purchasing a difficult proof and maintenance burden for a property the application never needed.

Locks can be the better operational choice

A short mutex-protected critical section often provides a clearer correctness argument and avoids repeated failed updates under heavy contention. Depending on implementation and workload, blocked threads can release CPU for useful work instead of spinning. This does not make locks universally superior: owner preemption, priority inversion and convoying can matter. I would compare both approaches under the actual contention and scheduling conditions, measuring CPU consumption and latency distribution as well as throughput. A quiet single-thread benchmark removes the circumstances that make the choice interesting.

Fairness deserves separate attention. A lock may or may not promise a useful acquisition order, and a lock-free structure may have excellent average throughput with poor per-thread outcomes. Report a distribution of completions or waiting by participant when that matters. An aggregate million operations per second can conceal one unlucky participant making no progress. The appropriate metric depends on the caller's contract: a background aggregation worker and an interactive control path can reasonably prefer different balances of efficiency, predictability and implementation simplicity.

State the guarantee without turning it into a deadline

A useful concurrency design document names the operation, progress property, participant assumptions, allocation policy and reclamation mechanism. It then states what is not implied about elapsed time. Tests can delay a participant, force contention, exhaust capacity and interrupt teardown to expose accidental dependencies. They provide valuable evidence, but repeated successful runs cannot prove every scheduling possibility. For a novel algorithm, the progress argument needs the same seriousness as the safety argument. I would prefer an established implementation when the application does not justify developing that proof itself.

Finally, connect the property to the product. If a bounded queue returns full immediately, its enqueue attempt may terminate predictably while the caller still needs a policy for rejected work. If the caller retries forever, the composed operation loses that bound. Progress guarantees are easiest to misuse at these composition boundaries. Lock-free and wait-free are precise tools for discussing them. Their value comes from narrowing what a system promises, not from supplying a general synonym for fast, responsive or immune to scheduling problems.

This distinction also keeps performance claims honest. A change can improve measured tail latency without becoming wait-free, and a wait-free algorithm can miss a deadline because its finite step bound is large. The proof and the measurement answer complementary questions. I would preserve both instead of allowing either to stand in for the other.