Course contentsShow
← Computer Science
Lesson 2568 of 2,87257. Concurrency FundamentalsFree lesson

The ABA Problem

Understanding the ABA problem in lock-free structures where a value changes from A to B and back to A, breaking assumptions.

The ABA Problem

What you'll learn: You'll understand how lock-free algorithms can be tricked when a memory location changes from A to B and back to A, appearing unchanged even though critical updates occurred.

The Illusion of Stability

In lock-free programming using compare-and-swap (CAS), you read a value, perform some computation, then use CAS to update only if the original value is still there. The ABA problem occurs when:

  1. Thread 1 reads value A from a memory location
  2. Thread 2 changes A → B → A (back to original)
  3. Thread 1's CAS succeeds because it still sees A, but the "world has changed" in ways Thread 1 doesn't realize

Why This Breaks Assumptions

Imagine a lock-free stack where the top node has value A. Thread 1 reads this pointer, planning to pop it. Meanwhile, Thread 2 pops A, pops B, then pushes A back on top. When Thread 1's CAS fires, it sees A is still the top (matching its saved copy), so it proceeds—but the stack's internal structure may have changed completely. Nodes that Thread 1 assumed were still connected might have been freed and reallocated elsewhere.

The Real Danger

The problem isn't just that A returned—it's that CAS can't detect that other meaningful changes happened in between. Your algorithm assumed "if the value matches, nothing important changed," but that assumption is now violated. This can lead to memory corruption, use-after-free bugs, or broken data structure invariants.

Solutions Preview

Common mitigations include tagged pointers (adding version numbers) or using garbage collection strategies that prevent premature reuse of memory locations—but understanding why ABA is a problem comes first.

Key Takeaway: The ABA problem reveals that simple value equality in lock-free algorithms isn't enough—you need mechanisms to detect when a location has been modified and restored, not just whether its current value matches your expectation.