The ABA Problem

The ABA Problem

The ABA problem is a subtle bug in compare and swap algorithms. CAS succeeds when the memory location still holds the expected value. But a value can change from A to B and back to A while a thread is paused. The thread then sees A, assumes nothing changed, and its CAS succeeds even though the world moved underneath it.

This is dangerous in pointer based structures. Imagine a lock free stack:

• Thread one reads the top pointer pointing to node A and plans to pop it.
• Thread one stalls. Other threads pop A, pop B, free A, then push a recycled node back at the same address A.
• Thread one resumes, sees the top still equals A, and its CAS succeeds, but A now points to a stale or freed successor.

The structure is corrupted because identity was confused with equality. The address matched, yet the meaning changed.

Common fixes:

• Tagged pointers Pair the pointer with a version counter so each change increments the tag. CAS compares pointer and tag together, so an A to B to A round trip still differs in the tag.
• Hazard pointers Mark nodes in use so they are not reclaimed until safe.
• Double width CAS Atomically swap pointer plus counter as one unit.

Key idea

The ABA problem fools CAS when a value cycles back to its original, so algorithms add version tags or hazard pointers to detect the hidden change.