What is the ABA problem in lock-free programming, and how do you solve it?

The ABA problem occurs when Thread 1 reads a value A from memory, then before it acts on that value, Thread 2 changes the value from A to B and then back to A again. When Thread 1 finally performs its compare-and-swap expecting A, the CAS succeeds because the value is indeed A again -- but Thread 1 has no way of knowing the value was actually modified and restored in between, which it wrongly assumes never happened. In many simple cases this is harmless, but in lock-free data structures such as lock-free queues, it can silently corrupt internal state. The standard fix in Java is AtomicStampedReference<V>, which pairs the actual value with a monotonically increasing integer stamp; its compareAndSet checks both the value and the stamp together, so even if the value has cycled back to A, the stamp will have changed in the meantime, causing the CAS to correctly fail and forcing a retry.