skip to content

What is the ABA problem in a CAS-based algorithm, and why can compare-and-swap miss it?

level: middleimportance: must knowfreq 62%

answer

  1. CAS compares value, not history
  2. A → B → A slips past compareAndSet
  3. Harmless for counters, harmful for reused references/nodes
  4. AtomicStampedReference = version stamp; AtomicMarkableReference = one bit
  5. Stamp must monotonically increase to defeat ABA

basics

~20 s

ABA is when a value goes A then B then back to A between a thread's read and its compare-and-swap. The CAS only checks the current value equals A, sees A, and succeeds, never noticing the change in between.

solid answer

~50 s

Compare-and-swap (CAS) updates a variable only if it still holds the value the thread last read. The ABA problem is that CAS compares values, not history: if another thread changes the value from A to B and back to A in the gap between your read and your CAS, the CAS still sees A and succeeds, as though nothing happened. For a plain counter that is harmless because A means the same thing. It becomes dangerous when the value is a reference or a node whose surrounding structure changed, for example a lock-free stack where the popped 'A' node was reused or its successor was altered. The fix is to make each successful change observable by pairing the value with a monotonically increasing version stamp (AtomicStampedReference) or a boolean mark (AtomicMarkableReference), so CAS compares (value, stamp) and detects the intervening change.

code

java · 15 lines
java
// Defeating ABA with AtomicStampedReference
AtomicStampedReference<String> ref =
    new AtomicStampedReference<>("A", 0);

int[] stampHolder = new int[1];
String current = ref.get(stampHolder); // reads value + stamp atomically
int stamp = stampHolder[0];            // e.g. value="A", stamp=0

// Meanwhile another thread does A->B->A, bumping the stamp twice:
// ref.compareAndSet("A", "B", 0, 1);
// ref.compareAndSet("B", "A", 1, 2);  // value back to "A", stamp now 2

// Our CAS expects ("A", 0): value matches but stamp doesn't -> fails.
boolean ok = ref.compareAndSet(current, "C", stamp, stamp + 1);
System.out.println(ok); // false -> ABA detected, we must re-read and retry

go deeper

for a junior

Can state the literal A→B→A scenario and that compareAndSet only checks the current value, so it succeeds even though the value changed and changed back.

for a middle

Explains why ABA is harmless for counters but harmful for reused references, and names AtomicStampedReference/AtomicMarkableReference as the fix that compares a version stamp alongside the value.

for a senior

Walks through a concrete lock-free stack corruption, explains GC's partial mitigation vs logical ABA, and reasons about the stamp needing to monotonically increase and the cost of the boxed (ref, stamp) pair.

for a principal

Frames ABA as 'CAS compares value not identity-over-time,' discusses versioned/tagged pointers, double-width CAS in non-GC languages, hazard pointers/epoch reclamation as alternatives to stamping, and when to design the algorithm so ABA is provably benign instead of paying for stamps.

## Background: CAS **Compare-and-swap (CAS)** is a hardware-supported atomic instruction. It takes three things: a memory location, an *expected* value, and a *new* value. Atomically (as one indivisible step) it checks whether the location currently holds the expected value; if so it writes the new value and reports success; otherwise it leaves the location alone and reports failure. In Java this is exposed as `AtomicInteger.compareAndSet(expected, new)`, `AtomicReference.compareAndSet(...)`, and similar. Lock-free algorithms use CAS in a **read-modify-CAS retry loop**: read the current value, compute a new value from it, then CAS. If the CAS fails (someone else changed it), loop and try again. This avoids locks while staying correct — *as long as a failed CAS reliably tells you 'something changed.'* ## The flaw: CAS compares values, not history CAS only asks 'is the current value still equal to what I expected?' It has no memory of what happened *in between* your read and your CAS. Consider: 1. Thread 1 reads the value: it is **A**. 2. Thread 1 is paused (scheduler, GC, page fault — anything). 3. Thread 2 changes the value **A → B**, then later **B → A**. 4. Thread 1 resumes and does `compareAndSet(A, newValue)`. The current value *is* A, so the **CAS succeeds** — even though the value was modified twice while Thread 1 slept. This is the **ABA problem**: the value returned to A, so CAS cannot distinguish 'never changed' from 'changed and changed back.' ## When ABA is harmless vs harmful For a **plain numeric counter**, ABA is usually fine: the value *is* the state, and an A is an A. The classic incrementing counter has no ABA bug. ABA bites when the value is a **reference** (or pointer) and the *meaning* behind that reference changed even though the reference equals its old value. The textbook case is a **lock-free stack (Treiber stack)** built on a `head` reference: - Thread 1 reads `head = A`, plans to pop A by CAS-ing `head` from A to A.next. - Thread 2 pops A, pops A.next (B), then pushes A back. Now `head = A` again, but A.next may now point somewhere different, or A may have been recycled into a different object. - Thread 1's `compareAndSet(A, oldAnext)` succeeds and sets head to a stale/dangling successor, corrupting the stack. The danger is amplified by **memory reuse** (object pools, or manual memory management in C/C++ where the same address is freed and reallocated). Java's garbage collector mitigates one form: as long as Thread 1 holds a reference to A, A cannot be collected and reused as a *different* object — so naive node-recycling ABA is less common in pure-Java GC'd code. But ABA can still occur logically whenever a reference cycles back to a prior value with different surrounding state. ## The fix: stamps and marks The cure is to make every change observable by attaching extra information that **monotonically advances** (or toggles), so 'changed back' is still detectable: - **`AtomicStampedReference<V>`** pairs a reference with an `int` **stamp** (a version number). Every update bumps the stamp. CAS now compares *both* (reference, stamp): `compareAndSet(expectedRef, newRef, expectedStamp, newStamp)`. Even if the reference returns to A, the stamp has advanced past the value Thread 1 read, so its CAS fails and it retries. You read both atomically via `get(int[] stampHolder)`. - **`AtomicMarkableReference<V>`** pairs a reference with a single `boolean` **mark**. It does not give a full version history — it answers 'has this been marked?' (e.g. logically deleted). It is enough for algorithms that only need one bit of extra state (like marking a node for deletion in a lock-free linked list), but a one-bit mark can itself toggle back, so it does not fully solve ABA the way a strictly increasing stamp does. The general principle behind both is the **versioned/tagged pointer** (or 'ABA tag'): store a counter alongside the value and increment it on every write, so identical values at different times carry different tags. ## Cost and alternatives A stamp doubles the logically-atomic word. Under the hood Java boxes the (reference, stamp) pair into a small immutable holder object that is itself swapped atomically, which adds a tiny allocation per update. Alternatives include using immutable values so a returned 'A' truly is the same state, designing algorithms where ABA is provably harmless, or (on the JVM) leaning on GC to prevent address reuse. Languages without GC often use a wider double-width CAS (DCAS / 128-bit CAS) to store pointer+counter together.

  • Does Java's garbage collector eliminate the ABA problem?
    No, it only mitigates one variant. Because you hold a reference to node A it can't be collected and reused as a different object, so naive memory-reuse ABA is rarer than in C/C++. But logical ABA still happens: a reference can cycle back to a prior value (e.g. node re-pushed onto a stack) with different surrounding state, so you still need a stamp.
  • Why is ABA usually not a problem for an AtomicInteger counter?
    Because for a counter the value IS the entire state and carries no hidden meaning — an A now is semantically identical to an A earlier, so succeeding on A is correct. ABA only matters when equal values at different times imply different surrounding state, typically with references into a mutable structure.

A hotel room key check: the desk only verifies the key opens room 204. If a guest checks out and a new guest checks into 204 with an identical key, the front desk can't tell them apart. A version sticker that increments on every check-in (the stamp) reveals the change even though the room number is unchanged.

saying these in an interview costs you the question

  • Claiming CAS compares the whole history or 'sequence of changes' — it only compares the current value to the expected value.
  • Saying Java's GC makes ABA impossible — it reduces memory-reuse ABA but not logical ABA.
  • Thinking ABA affects every CAS use, including simple counters — it generally doesn't for value-only state.
  • Confusing AtomicMarkableReference (one boolean) with AtomicStampedReference (a full version counter); only a monotonic stamp fully defeats ABA.

context

resolving links…