ABA Problem

The ABA problem is a fundamental hazard in multithreaded computing that arises when a memory location is read, modified by another thread, and then modified back to its original value before the first thread can complete its update. A compare-and-swap operation on that location succeeds because the value matches, but the intermediate modification means the data structure may now be in an inconsistent or unsafe state.

The problem is named for the sequence of values observed: A, then B, then A again. It is particularly dangerous in lock-free data structures built with CAS, such as lock-free stacks and queues, where a node may be freed and reallocated, causing a thread to operate on stale or incorrect memory. Solutions include hazard pointers, read-copy-update (RCU), and tagged pointers that version memory locations.