a lock-free data structure
A lock-free data structure lets many threads read and modify it concurrently without using locks. Instead of saying 'wait your turn, I have the lock,' each thread optimistically does its work and then uses an atomic compare-and-swap to commit it, and if some other thread got there first, it simply retries with the new reality. The motivating worry is that a lock can become a bottleneck or a hazard: a thread that is suspended (or crashes) while holding a lock blocks everyone else indefinitely, and on a busy structure threads spend their time queueing rather than working. Lock-free designs sidestep that by never blocking on each other at all.
Lock-free has a precise technical meaning, not just 'no locks': it is a progress guarantee. A structure is lock-free if, whenever multiple threads operate on it, at least one of them always makes progress in a bounded number of steps — the system as a whole never stalls, even if some individual threads are repeatedly forced to retry. This rules out deadlock entirely (there is no lock to hold) and also rules out the situation where one stuck thread freezes everyone. The canonical building block is the compare-and-swap retry loop: read the current state, compute the new state you want, then CAS the change in; if the CAS fails because another thread changed the state meanwhile, loop and try again from the freshly observed state. A lock-free stack, for instance, pushes by CAS-ing the head pointer from the old top to the new node.
The honest reality is that lock-free code is hard and easy to get subtly wrong. The retry loop must be carefully designed, and it is vulnerable to the ABA problem, where a value changes from A to B and back to A so a naive CAS wrongly thinks nothing happened. Reclaiming memory safely (knowing when no thread can still be reading a node you want to free) is a notorious difficulty, solved with techniques like hazard pointers or epoch-based reclamation. Lock-free is not automatically faster than a good lock — under low contention a simple mutex often wins — and it does not guarantee any individual thread finishes (that stronger promise is wait-free). Use it where contention is genuinely high or where you cannot tolerate a thread being blocked by another holding a lock.
Lock-free push onto a stack: do { oldHead = top; newNode.next = oldHead; } while (!CAS(&top, oldHead, &newNode)). The loop re-reads top and retries whenever another thread pushed or popped first.
The compare-and-swap retry loop — the heartbeat of nearly every lock-free algorithm.
Lock-free is not 'wait-free' and not automatically fast. It guarantees the system makes progress, not that your particular thread does — an unlucky thread can retry many times. Under low contention a plain mutex is often simpler and faster.