Why does the ABA problem occur in lock-free CAS-based algorithms?

A plain compare-and-swap only checks whether a memory location's current value still equals the expected value; it has no way to know whether that value changed and then changed back in between the read and the CAS.

sequenceDiagram
  participant T1 as Thread 1
  participant Mem as Shared value
  participant T2 as Thread 2
  T1->>Mem: read value A
  T2->>Mem: change A to B
  T2->>Mem: change B back to A
  T1->>Mem: CAS expected A new C succeeds
  Note over T1,Mem: T1 assumes nothing changed, but B happened unnoticed

This matters most for lock-free data structures like linked stacks or queues built on AtomicReference: if a node object is popped and then a logically-equivalent but structurally different node is pushed back with the same reference value, a thread's CAS can succeed even though the intervening changes invalidate its assumptions about the structure it's modifying, corrupting the data structure.

Java addresses this with AtomicStampedReference and AtomicMarkableReference, which pair the reference with a version stamp (an int) or a boolean mark. The CAS then compares both the reference and the stamp, so even if the reference value cycles back to something equal to A, the stamp will have advanced, and the CAS correctly fails, revealing that an intermediate change occurred.