What is the ABA problem and how do you solve it?

The ABA problem is when a CAS succeeds even though the value changed and changed back: a thread reads A, another thread changes it to B and then back to A, and the first thread's CAS(expected=A, new=...) still wins — blind to the intervening mutation. You solve it by versioning the value, typically with AtomicStampedReference.

Why plain CAS is fooled

CAS compares values, not histories. If the value is the same as when you read it, CAS assumes nothing happened. For a counter that is harmless, but for a reference it is dangerous: the address may be identical while the object it points to — or the surrounding data structure — has been mutated, freed, or reused.

The classic case is a lock-free stack. Thread 1 reads top = A (with A.next = B) and prepares CAS(top, A, B) to pop A. Before it runs, Thread 2 pops A, pops B, then pushes A back. Now top = A again, but A.next points somewhere stale. Thread 1's CAS sees top == A, succeeds, and sets top to a node that has already been removed — corrupting the stack.

T1: read top = A  (plans CAS top: A -> A.next)
T2: pop A    -> top = B
T2: pop B    -> top = C
T2: push A   -> top = A   (A.next is now stale!)
T1: CAS(top, expected=A, new=A.next)  --> SUCCEEDS, corrupts stack

The fix: stamp the reference

Pair the value with a monotonically increasing version so A-at-stamp-1 is distinguishable from A-at-stamp-3. AtomicStampedReference does exactly this — CAS must match both the reference and the stamp:

AtomicStampedReference<Node> top = new AtomicStampedReference<>(a, 0);

int[] stampHolder = new int[1];
Node current = top.get(stampHolder);   // read value AND stamp
int stamp = stampHolder[0];
// ... compute newTop ...
boolean ok = top.compareAndSet(current, newTop, stamp, stamp + 1);
// fails if anyone bumped the stamp, even if the reference is the same A

If only presence/absence matters, AtomicMarkableReference carries a single boolean mark instead of a counter.