Java Concurrency Notes: ABA Problem
■ What is the ABA Problem?
CAS (Compare-And-Swap) checks only the value. If a value changes from A → B → A,
CAS may succeed incorrectly, thinking nothing changed, while in reality, the state was
modified.
■ Example Scenario (Lock-free Stack)
• Thread T1 reads top of stack = Node A, plans to CAS top from A → A.next.
• Thread T2 pops A, pops B, then pushes A back (so top points to A again).
• Thread T1 resumes and sees top = A, CAS succeeds.
• Problem: T1 popped an 'A' that was modified and reinserted, stack integrity is broken.
■ Why is this dangerous?
The value looks the same (A), but the state has changed. This can cause data corruption,
lost nodes, and broken invariants in lock-free data structures.
■ Analogy
You left your backpack (A) on a desk. Someone replaced it with another (B), then later put
your original backpack (A) back. When you return, you see A and assume nothing
changed — but inside, things might be missing.
■ Solutions
• Use AtomicStampedReference → attaches a version (stamp) with the value.
• Use AtomicMarkableReference → attaches a boolean mark to detect changes.
• Advanced techniques like hazard pointers or epoch-based reclamation (outside core
Java).
■ Summary
ABA Problem occurs when value changes A → B → A, and CAS cannot detect the
intermediate change. In Java, use AtomicStampedReference or
AtomicMarkableReference to avoid this issue.
