Why give up the lock at all?
By now a mutex feels like a solved problem: wrap the shared data, lock on the way in, unlock on the way out, and the memory ordering you met last rung makes everything between safe. It is correct, it is fast enough almost always, and it should remain your default. So why would anyone want a data structure that never locks? The answer is not "locks are slow" — an uncontended mutex is cheap. The answer is what a lock does to other threads when its holder stops running.
Picture thread A taking the lock, then getting preempted by the scheduler the instant after — a context switch yanks the CPU away and hands it to something else for ten milliseconds. Every other thread that needs that lock is now stuck, not because they are doing work, but because they are waiting on a sleeping thread. Worse cases exist: A is at lower priority and never gets scheduled while a busy high-priority thread spins for the same lock (priority inversion), or A crashes mid-critical-section and the lock is never released at all. With a lock, the progress of the whole system is hostage to the one thread holding it.
A non-blocking algorithm refuses this hostage situation. The guarantee is structural: the suspension, or even the death, of any one thread cannot stop the others from making progress. There is no critical section that, if abandoned, freezes everyone. That single property — system progress does not depend on any one thread continuing to run — is what the words non-blocking, lock-free, and wait-free all describe, at three increasing strengths. The rest of this rung is about how to actually build such things; this guide is about reading the labels honestly.
Three guarantees, from weakest to strongest
The labels form a precise hierarchy, and the only way to keep them straight is to ask, for each, "under what condition is some thread, or every thread, guaranteed to finish?" Start at the bottom. Obstruction-free is the weakest: a thread is guaranteed to finish its operation if it runs alone for long enough — that is, if all other threads are paused. That sounds almost useless, and on its own it is weak, because if two threads keep interfering they can repeatedly knock each other back and neither finishes. But it rules out true deadlock, and it is a useful stepping stone.
Step up to lock-free, the most important rung in practice. The guarantee: out of all the threads contending, at least one of them always makes progress in a bounded number of steps — the system as a whole never gets stuck, even though individual threads may be unlucky and have to retry. The mental image is a swarm at a doorway: collisions happen, people get pushed back, but the crowd as a whole keeps flowing through, because every collision means someone got through to cause it. No thread can ever wait forever on another, yet a specific unlucky thread might be starved while others stream past it.
At the top is wait-free, the strongest and the rarest. The guarantee: every thread finishes its operation in a bounded number of its own steps, no matter what the others do. Nobody is ever starved; there is a hard ceiling on how long any single operation can take. This is what hard real-time systems crave, because it gives a worst-case bound you can actually compute. The catch — and it is a big one — is that wait-free algorithms are dramatically harder to design and usually carry more overhead, because guaranteeing the slowest thread a bound often means faster threads must stop and help it, a trick called the helping technique that you will see later in this rung.
guarantee who is guaranteed to finish? rules out ---------------- ---------------------------------- ------------------- blocking (mutex) nobody, if lock-holder is suspended nothing structural obstruction-free a thread that runs ALONE long enough deadlock lock-free AT LEAST ONE thread, always deadlock + livelock-of-system wait-free EVERY thread, in bounded own steps deadlock + livelock + starvation strength: blocking < obstruction-free < lock-free < wait-free
What these guarantees do NOT promise
Note also the sharp word "lock-free." It does not merely mean "I did not call pthread_mutex_lock()." An algorithm can avoid the mutex API and still be blocking — for example a hand-rolled spinlock built from an atomic flag is still a lock: if its holder is suspended, everyone spinning is stuck, which is exactly the hostage situation we set out to escape. "Lock-free" is defined by the progress property, not by which library functions you avoided. The test is always: if I freeze any one thread at any point, can the rest still finish? If the answer is no, it is blocking, whatever the code looks like.
And these guarantees say nothing about correctness on their own. A lock-free structure can be lock-free and still return wrong answers if its operations are not properly ordered against each other. Progress and correctness are two separate axes: progress tells you someone finishes, correctness tells you they finish with the right result. That second axis has its own precise name, and it is the other half of this guide.
The other axis: linearizability
When a single thread runs a stack, "correct" is obvious: a push then a pop returns what you pushed. With many threads whose operations overlap in time, even saying what correct means is hard. If thread A's push and thread B's pop are running simultaneously, in what order did they "really" happen? Linearizability is the gold-standard answer. It says: each operation appears to take effect instantaneously at some single moment between when you called it and when it returned — its linearization point — and the whole concurrent run looks identical to some sequential run that respects those instants. In short: it behaves as if there were one true order, even though operations physically overlapped.
Why does the instant have to fall between call and return? Because that is the window during which the operation was actually live. If a push returns at time t, then by t the value is definitely in the stack — any pop that starts after t must be able to see it. Linearizability forbids the absurdities: you cannot pop a value that was never pushed, you cannot pop the same value twice, and once an operation has returned, the world must agree it happened. This is why it is the contract we want for concurrent data structures — it lets you reason about the structure as if it were a simple sequential object, the same gift the sequential-consistency notebook gave you one rung ago, now applied per-object.
Here is the crucial separation to lock into your head: progress and linearizability are independent. A structure can be lock-free but not linearizable (fast progress, wrong answers), or linearizable but blocking (a plain mutex-guarded stack is perfectly linearizable — the linearization point is just inside the critical section). The lock-free data structures you will build in this rung aim to be both at once, and that combination is precisely what makes them hard. Most of the difficulty, and most of the famous bugs, live in pinning down a correct linearization point that survives every possible interleaving.
The engine underneath, and the road ahead
How can a thread update a shared structure with no lock and still be correct? The whole trick rests on one hardware primitive: an atomic read-modify-write that does not tear. The workhorse is compare-and-swap (CAS): in one indivisible step it reads a location, checks it still equals an expected value, and only then writes the new value, reporting whether it succeeded. The pattern is read the current state, compute the new state, then CAS it in — and if CAS fails because someone else changed the location first, loop and try again. That loop is the CAS retry loop, and it is the beating heart of nearly every lock-free algorithm. Some chips, like ARM, instead offer load-linked / store-conditional, a close cousin you will meet in the next guide.
With this vocabulary you can now read the rest of the rung as a single arc. The next guide drills into CAS itself and its most infamous trap, the ABA problem, where a value changes A then back to A and a naive CAS cannot tell anything happened. Then we build real structures — a lock-free stack, a queue, a single-producer single-consumer ring buffer — and discover a problem locks hid from us entirely: once you remove a node without a lock, *when is it safe to free()*? Another thread may still be reading it. That reclamation problem is why hazard pointers, epochs, and RCU exist, and it is where the last two guides go. Hold tight to the two axes — progress and linearizability — and the whole climb stays oriented.