What is the ABA problem in CAS-based code, and how do you guard against it in Java?

## Recap: what CAS actually verifies `compareAndSet(expected, newValue)` performs an atomic *compare-then-conditional-write*: it writes `newValue` **only if** the cell currently equals `expected`. Crucially, it checks **equality of the value right now**, not the *history* of the cell. It cannot tell the difference between "the value never changed" and "the value changed several times but happens to equal `expected` again now." ## The ABA scenario Name the value transitions by letters: 1. Thread T1 reads the shared cell and sees **A**. It intends to do `CAS(A, …)` shortly. 2. Before T1's CAS, thread T2 changes the cell **A → B**, then changes it **B → A** again. 3. T1 now runs `CAS(A, …)`. The cell currently holds **A**, so the CAS **succeeds** — even though the world moved through B and back. T1 believes "nothing changed since my read," which is **false**. That is the **ABA problem**: same value, different history. ## Why it's often harmless — and when it isn't For a counter that only ever **increases** (or otherwise never revisits a prior value), ABA can't occur: the value can't come back to a number it already passed. So `AtomicInteger`/`AtomicLong` counters are fine. ABA bites **lock-free data structures that recycle objects**. Classic example: a lock-free Treiber stack. ```text Stack: head -> A -> C T1: pop() reads head = A, plans CAS(head, A, A.next == C) T1 is descheduled here. T2: pop A (head -> C) T2: pop C (head -> empty) T2: push A (head -> A -> empty) // A reused, but A.next is now stale T1 resumes: CAS(head, A, C) succeeds because head == A again, but C was already removed -> head now points at a freed/stale node. Corruption. ``` The reference `A` *equals* the expected `A`, but its meaning (its `next`) changed. CAS can't see that. ## The fix: a version stamp The cure is to make every modification observable even when the value returns to a prior one — attach a **monotonically increasing version counter (stamp)** to the value and CAS the **(value, stamp)** pair together. Any A→B→A round trip bumps the stamp twice, so the stamp differs from what T1 read, and T1's combined CAS fails. Java provides this as **`AtomicStampedReference<V>`**: ```java AtomicStampedReference<Node> head = new AtomicStampedReference<>(a, 0); int[] stampHolder = new int[1]; Node current = head.get(stampHolder); // read value AND stamp int stamp = stampHolder[0]; // ... compute newValue ... boolean ok = head.compareAndSet( current, newValue, // expected vs new reference stamp, stamp + 1); // expected vs new stamp (bump it) ``` `compareAndSet` succeeds only if **both** the reference **and** the stamp still match. Because each successful update increments the stamp, the A→B→A cycle leaves a stamp that no longer equals T1's expected stamp, so the stale CAS fails and T1 retries with fresh state. ## `AtomicMarkableReference` When you don't need a full counter — only a single boolean flag travelling atomically with the reference (e.g. "this node is logically deleted") — use **`AtomicMarkableReference<V>`**, which carries one `boolean` *mark* instead of an `int` stamp. It's used in lock-free list deletion algorithms (mark-then-unlink). Note: a single boolean can still ABA on the mark itself; the stamp (counter) is the stronger guard. ## Practical guidance - Most application code never meets ABA because it isn't writing lock-free recycling structures — prefer the JDK's concurrent collections, which already handle it. - If you *are* building lock-free structures with node reuse, assume ABA is possible and use a stamped reference (or avoid reuse, e.g. allocate fresh immutable nodes / let GC prevent reuse of live addresses). - ABA is fundamentally about *identity vs history*: CAS guards identity-now, the stamp restores a notion of history.