You finally got your lock-free stack working with compare-and-swap. The CAS succeeds, the pointer matches, life is good. Then production starts losing nodes. Welcome to the ABA problem: the value at an address was A, changed to B, then changed back to A — and your CAS happily proceeds as if nothing happened.

CAS only checks that the current value equals the expected value. It cannot tell you whether the value stayed equal the whole time. That gap is where the bugs live.

The classic lock-free stack bug. Thread 1 reads top = A, where A.next = B. It plans to pop A by CAS-ing top from A to B. Before the CAS fires:

• Thread 2 pops A (top is now B)
• Thread 2 pops B (top is now C)
• Thread 2 pushes A back (top is now A again, but A.next is now whatever the allocator handed back — possibly garbage, or C)

Thread 1's CAS succeeds: top was A, still A. It sets top to B. But B was freed and reused. You just corrupted the stack and leaked or double-freed memory.

Real-world example. The Linux kernel hit this in early lock-free list code. Java's AtomicReference ships with AtomicStampedReference specifically because every serious lock-free library learns this lesson. The .NET concurrent collections use hazard pointers and version stamps for the same reason.

The fixes:

• Tagged pointers (versioned CAS). Pack a counter alongside the pointer. Every modification bumps the counter. CAS now compares (pointer, version), so A→B→A becomes A/1 → B/2 → A/3, and the stale CAS fails. Needs double-width CAS (CMPXCHG16B on x86-64).
• Hazard pointers. Each thread publishes which pointers it's currently using. Memory can't be reclaimed until no hazard pointer references it. More complex but no double-width requirement.
• Epoch-based reclamation. Defer freeing until all threads have passed a quiescent point. Used in crossbeam (Rust) and the Linux RCU subsystem.
• Just use a mutex. Seriously. Most code doesn't need lock-free anything.

Rule of thumb: A 64-bit version counter incremented per operation overflows in ~292 years at 1 billion ops/sec. A 32-bit counter overflows in ~4 seconds at that rate — and ABA-on-the-version becomes possible. Use 64 bits or accept the wraparound risk.

If you're writing lock-free data structures and haven't accounted for ABA, you don't have a lock-free data structure — you have a time bomb that ships green on your laptop and detonates under contention.