What is the ABA problem?

• ABA problem – a CAS succeeds incorrectly when a value changes from A to B and back to A while a thread is paused.
• Root cause – compareAndSet(expected, new) checks only the present value, not its history.
• Impact – corrupts lock-free structures (stacks, free-lists) where node identity matters.
• AtomicStampedReference – pairs a reference with an int stamp; CAS checks both reference and stamp.
• AtomicMarkableReference – lighter variant with a boolean mark instead of a counter.
• Java GC – reduces ABA vs. C, but does not eliminate it with object pooling or logical round-trips.

What is the ABA problem?

A CAS atomically says "if current equals expected, replace it." The flaw is that equality is checked only against the present value, not whether the value changed and came back.

AtomicReference<String> top = new AtomicReference<>("A");
String observed = top.get();           // observes A
// Thread paused; another thread: A → B → A
top.compareAndSet(observed, "C");      // SUCCEEDS incorrectly! A == A

Where does ABA cause real damage?

In lock-free stacks and free-lists. A thread reads top node A and records A's next pointer. While the thread is paused, A is popped, reused (its next pointer changed), and pushed back. The paused thread's CAS succeeds because it sees A at the top, but the next pointer is stale, corrupting the stack.

How does AtomicStampedReference fix it?

AtomicStampedReference pairs the reference with an int stamp. Every CAS checks both the reference and the stamp. Even if the reference returns to A, the stamp has advanced, so the CAS fails.

package com.bank.lockfree;

import java.util.concurrent.atomic.AtomicStampedReference;

public class StampedFreeList {

    private final AtomicStampedReference<Node> top =
        new AtomicStampedReference<>(null, 0);

    public void push(Node node) {
        int[] stampHolder = new int[1];
        Node current;
        int stamp;
        do {
            current = top.get(stampHolder);
            stamp = stampHolder[0];
            node.next = current;
        } while (!top.compareAndSet(current, node, stamp, stamp + 1));
    }

    public Node pop() {
        int[] stampHolder = new int[1];
        Node current;
        int stamp;
        do {
            current = top.get(stampHolder);
            stamp = stampHolder[0];
            if (current == null) return null;
        } while (!top.compareAndSet(current, current.next, stamp, stamp + 1));
        return current;
    }
}

How does a banking free-list use AtomicStampedReference?

At National Bank of India, settlement slips are pooled to reduce garbage collection pressure. A free-list hands out reusable slip objects and recycles them after use. Under high concurrency, plain CAS on the free-list head caused duplicate hand-outs because a slip was popped, used, and pushed back before a paused thread's CAS completed.

package com.bank.pool;

import java.math.BigDecimal;
import java.util.concurrent.atomic.AtomicStampedReference;

public class SettlementSlipPool {

    private final AtomicStampedReference<SettlementSlip> freeHead =
        new AtomicStampedReference<>(null, 0);

    public SettlementSlip acquire() {
        int[] stampHolder = new int[1];
        SettlementSlip head;
        int stamp;
        do {
            head = freeHead.get(stampHolder);
            stamp = stampHolder[0];
            if (head == null) return new SettlementSlip(); // pool empty, create new
        } while (!freeHead.compareAndSet(head, head.next, stamp, stamp + 1));
        head.reset();
        return head;
    }

    public void release(SettlementSlip slip) {
        int[] stampHolder = new int[1];
        SettlementSlip head;
        int stamp;
        do {
            head = freeHead.get(stampHolder);
            stamp = stampHolder[0];
            slip.next = head;
        } while (!freeHead.compareAndSet(head, slip, stamp, stamp + 1));
    }
}

How does AtomicStampedReference compare to AtomicMarkableReference?

| Feature | AtomicStampedReference | AtomicMarkableReference |
|---------|----------------------|-------------------------|
| Tag type | int (version counter) | boolean (mark) |
| ABA detection | Full history via stamp | One-bit flag only |
| Use case | Lock-free stacks, free-lists | Marking nodes as logically deleted |
| Overhead | 4 bytes for stamp | 1 bit for mark |

AtomicMarkableReference is useful for marking a node as logically deleted in a lock-free linked list. The mark bit prevents other threads from modifying a node that is being removed.

When is ABA harmless?

For a simple counter with AtomicInteger, ABA is usually harmless because you care about the final number, not the path. If a counter goes 5 → 6 → 5 and your CAS expects 5, the increment to 6 is correct regardless. ABA matters only when the identity or structure of the referenced object matters, not just its value.

How does Java's garbage collector reduce ABA?

In languages like C and C++, freed memory can be reallocated to a new object at the same address, making ABA very common. Java's GC prevents address reuse while references exist, so pointer-level ABA is rare. However, logical ABA still occurs when objects are recycled in pools or values undergo a round-trip.

What are common interview follow-up questions?

• How does garbage collection reduce ABA compared to C?
• When does logical ABA occur even without pointer recycling?
• How does the Disruptor avoid ABA entirely by using monotonically increasing sequence numbers?