lock-free progress

Imagine a busy kitchen where several cooks share one cutting board. The usual way to keep them from colliding is a rule: whoever holds the board has it, everyone else waits. That waiting is a lock. Now imagine a different design where nobody ever has to wait their turn — cooks make a quick attempt to grab a slot, and if they collide, at least one of them always succeeds and the work moves forward. Lock-free is the name for this second style, made precise. It is a progress guarantee about a whole group of threads, not about any single thread.

Precisely: an algorithm is lock-free if, whenever the program runs for long enough, at least one thread always makes progress — completes an operation — no matter how the operating system pauses, slows, or interleaves the other threads. The key consequence is that the system as a whole never gets stuck. If one thread is suspended forever right in the middle of its work, the others can still finish their own operations; they do not sit blocked waiting for that frozen thread to wake up and release something. This is exactly what a mutex CANNOT promise: if the thread holding a mutex is paused by the scheduler, everyone waiting on that mutex is stuck until it resumes.

Be careful about what lock-free does NOT mean. It does not mean faster — a well-tuned lock-based design can easily beat a lock-free one under low contention. It does not mean lockless code is automatically better. And crucially, it does not promise that any individual thread finishes; lock-free allows one unlucky thread to be starved forever, retrying and failing while its neighbours keep succeeding. The guarantee is only that SOMEONE always advances. That stronger per-thread promise is wait-freedom, a separate and harder property.