CAS only sees equality
Compare and swap decides only whether a value equals the expected snapshot. It cannot tell whether the value stayed the same the whole time or changed and changed back. The ABA problem is when a location goes from A to B and back to A between a thread read and its CAS. The CAS sees A, matches, and succeeds, even though the world changed underneath it.
A concrete failure
Consider a lock free stack pop. A thread reads the top node A and plans to CAS the head from A to A next. Before it does, another thread pops A, pops B, then pushes A back. The head is A again, so the CAS succeeds, but A next now points into reclaimed or reused memory. The stack is corrupted even though every individual CAS looked valid.
The fixes
- Tagged pointers pack a version counter beside the pointer, so each change bumps the tag and A with tag 1 differs from A with tag 3
- Double width CAS atomically swaps pointer plus counter together
- Hazard pointers or epoch reclamation prevent the freed node from being reused too soon
Key idea
ABA fools CAS because equality hides intervening changes, fixed with version tags, wide CAS, or safe reclamation.