A strong answer
A Treiber stack is one CAS loop on one word: push links the new node to the current head and CASes head forward, pop reads head, reads that node's next, and CASes head down to it. Against a mutex it buys a progress guarantee, not speed. If my CAS fails, another thread changed head, so somebody advanced, and no thread can freeze the structure by stalling between reading head and writing it. Worth naming precisely: lock-free means some thread always completes, wait-free means every call completes within its own bounded steps, and a Treiber stack is lock-free without being wait-free, since one thread can lose its CAS indefinitely while the system still moves.
The first way to get it wrong is publication ordering. The store into the new node's next field has to happen before the CAS that makes the node reachable, or a second thread can observe the new head while the link it depends on is still stale and follow garbage. So the publishing CAS releases, the reader's load of head acquires, and a relaxed CAS is a bug even though a CAS is atomic. Atomicity answers whether the swap happens exactly once; ordering answers whether other threads are guaranteed to see the writes that must come before it. C++ and Rust hide this behind a sequentially consistent default; anything weaker must be written deliberately.
The second way is ABA, which has two halves that get collapsed. The CAS compares addresses, so a node that is popped, freed and reallocated at the same address lets a stale CAS succeed on a structure that changed underneath it: thread one reads head A and A.next B, stalls, several pops happen elsewhere, a fresh node lands at A's old address, and the CAS installs B where B no longer belongs. That half is address reuse. The other half survives a collector, because the same node object can be popped and pushed again: head reads A again, A's next now points somewhere else, the CAS still succeeds, the node that was pushed again vanishes from the stack, and a node that was already popped comes back, all with no error reported anywhere.
The halves meet in reclamation, and this is where candidates lose points: a popped node cannot be freed while another thread may still be holding a pointer into it, so an unmanaged implementation needs hazard pointers, epochs or an arena, while a collector removes only the address-reuse half of ABA and leaves the logical half. The usual fix for what remains is a tagged pointer: a version counter in the spare bits of the address, or a double-width CAS such as cmpxchg16b, which is the shape of Java's AtomicStampedReference. It costs a wider atomic operation and a stamp that eventually wraps around. The honest close is that a mutex over the same stack is often as fast in practice and always easier to reason about, so lock-free earns its place when a stalled thread must not stop everyone else, not when someone wants fewer instructions.
What the interviewer is listening for
- The progress vocabulary, and that lock-free is a claim about stalls, not a claim about speed.
- Ordering: release when publishing the node, acquire when reading head, and the difference between atomicity and visibility.
- ABA in both halves, including the version that still works when memory is never freed.
- Reclamation as a precondition: no free while a reader can hold the pointer, which is why the design reaches outside the stack itself.
Common mistakes
- Claiming lock-free means faster, or treating a failed CAS as the structure failing.
- Reducing ABA to a freed and reused address, then concluding a collector makes ABA impossible.
- Assuming an atomic CAS carries ordering with it, so relaxed operations or a volatile field are enough.
- Freeing the popped node straight after a successful CAS, which becomes a use-after-free the moment another thread stalls holding it.