What is the ABA problem in a CAS-based algorithm, and why can compare-and-swap miss it?
answer
- CAS compares value, not history
- A → B → A slips past compareAndSet
- Harmless for counters, harmful for reused references/nodes
- AtomicStampedReference = version stamp; AtomicMarkableReference = one bit
- Stamp must monotonically increase to defeat ABA
basics
~20 sABA 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 sCompare-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// 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 retrygo deeper
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.
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.
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.
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.