Introduction

Wait-free and lock-free algorithms are both non-blocking, but they do not promise the same thing. The difference is about progress guarantees: lock-free means the system as a whole keeps moving, while wait-free means every individual thread is guaranteed to finish its operation in a bounded number of steps.

The Progress Guarantees Matter More Than The Syntax

These terms are often explained as if they were implementation patterns, but they are really correctness guarantees under contention.

• 'blocking: a stalled thread can prevent others from making progress'
• 'lock-free: at least one thread completes an operation in a finite number of steps'
• 'wait-free: every thread completes its own operation in a finite number of steps'

That means every wait-free algorithm is also lock-free, but not every lock-free algorithm is wait-free.

A compare-and-swap loop is the usual starting point for lock-free code. If many threads collide, one thread wins and others retry. The overall system progresses, but a particular thread may starve.

A Lock-Free Counter Example

This counter uses an atomic compare-and-swap loop. It is lock-free because if several threads race, one of them will eventually succeed.

1#include <atomic>
2#include <iostream>
3#include <thread>
4#include <vector>
5
6std::atomic<int> counter{0};
7
8void increment_many_times(int n) {
9    for (int i = 0; i < n; ++i) {
10        int expected = counter.load(std::memory_order_relaxed);
11        while (!counter.compare_exchange_weak(
12            expected, expected + 1,
13            std::memory_order_release,
14            std::memory_order_relaxed)) {
15            // expected is updated and the loop retries
16        }
17    }
18}
19
20int main() {
21    std::vector<std::thread> threads;
22    for (int i = 0; i < 4; ++i) {
23        threads.emplace_back(increment_many_times, 10000);
24    }
25    for (auto &t : threads) {
26        t.join();
27    }
28    std::cout << counter.load() << "\n";
29}

Why is this not wait-free? Because one unlucky thread can keep losing the compare-and-swap race and retry forever in theory.

A Simple Wait-Free Illustration

True wait-free data structures are hard to design, but the concept is easier to see with per-thread ownership. If each thread writes only to its own slot, no retries are needed and each operation finishes in a fixed number of steps.

1#include <array>
2#include <iostream>
3#include <thread>
4
5constexpr int kThreads = 4;
6std::array<int, kThreads> slots{};
7
8void publish_value(int thread_id, int value) {
9    slots[thread_id] = value;
10}
11
12int main() {
13    std::thread t1(publish_value, 0, 10);
14    std::thread t2(publish_value, 1, 20);
15    std::thread t3(publish_value, 2, 30);
16    std::thread t4(publish_value, 3, 40);
17
18    t1.join();
19    t2.join();
20    t3.join();
21    t4.join();
22
23    int total = 0;
24    for (int v : slots) {
25        total += v;
26    }
27    std::cout << total << "\n";
28}

This example is deliberately simple. It illustrates the progress guarantee, not a general-purpose wait-free queue or stack. Each write completes immediately because no other thread can block or force a retry on that slot.

Real Data Structure Examples

Typical lock-free structures include:

• Treiber stack
• Michael and Scott queue
• many atomic counters and work-stealing building blocks

Typical wait-free structures are rarer because the guarantee is stronger and the algorithms are more complex. They often rely on helping mechanisms, bounded retries, versioning, or per-thread descriptors so that a stalled thread cannot delay everyone else indefinitely.

The cost of stronger guarantees is usually added complexity, more memory overhead, and harder proofs.

Why Developers Usually Start With Lock-Free

Lock-free algorithms are much more common in production because they often provide most of the performance benefit without the full cost of wait-freedom. For many systems, it is acceptable that a thread might retry under heavy contention as long as the whole structure keeps moving.

Wait-free design becomes more attractive when latency guarantees matter, such as hard real-time systems or code paths where starvation is unacceptable.

Memory Ordering Still Matters

Non-blocking does not mean "ignore the memory model." Atomic operations still need appropriate ordering semantics.

1std::atomic<int> ready{0};
2int data = 0;
3
4void producer() {
5    data = 42;
6    ready.store(1, std::memory_order_release);
7}
8
9void consumer() {
10    while (ready.load(std::memory_order_acquire) == 0) {
11    }
12    std::cout << data << "\n";
13}

Without matching acquire and release semantics, one thread may observe stale data even if the synchronization variable changed.

Common Pitfalls

The most common mistake is calling an algorithm wait-free just because it uses atomics instead of a mutex. Atomics alone do not provide wait-freedom.

Another mistake is ignoring starvation. A compare-and-swap retry loop may look fast in testing but still allow a thread to lose indefinitely under contention.

Developers also underestimate memory reclamation. Lock-free linked structures often need hazard pointers, epoch-based reclamation, or another safe reclamation strategy before they are actually correct.

Finally, examples that are wait-free only because each thread owns separate memory do not automatically generalize to shared queues, stacks, or maps.

Summary

• Lock-free means system-wide progress; wait-free means per-thread progress.
• A compare-and-swap retry loop is usually lock-free, not wait-free.
• Wait-free algorithms are stronger but harder to design and prove.
• Real non-blocking structures still need correct memory ordering.
• Safe memory reclamation is part of correctness, not an optional extra.