How AtomicStampedReference Solves the ABA Problem in Java Concurrency

What is the ABA problem

Anyone familiar with Java will know CAS (compareAndSwap). In Java the Unsafe class provides native methods that directly manipulate memory, including the implementation of compareAndSwap.

public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);

Here var1 is the current object, var2 is the offset of a field within that object, var4 is the expected value at that offset, and var5 is the new value to swap in. The operation succeeds only if the current value matches the expected one, making it an atomic operation that underpins many thread‑safe implementations in Java.

Example with AtomicInteger whose initial value is 5 and two threads try to set it to 10:

public static void main(String[] args) {
    final AtomicInteger count = new AtomicInteger(5);
    for (int i = 0; i < 2; i++) {
        Thread thread = new Thread(() -> {
            try { Thread.sleep(10); } catch (Exception ignore) {}
            boolean re = count.compareAndSet(5, 10);
            System.out.println(Thread.currentThread().getName() + " compareAndSet " + re);
        });
        thread.start();
    }
}

Only one thread succeeds, as expected.

If another thread later tries to change the value from 10 back to 5, the output can be surprising:

public static void main(String[] args) {
    final AtomicInteger count = new AtomicInteger(5);
    for (int i = 0; i < 2; i++) {
        Thread thread = new Thread(() -> {
            try { Thread.sleep(10); } catch (Exception ignore) {}
            boolean re = count.compareAndSet(5, 10);
            System.out.println(Thread.currentThread().getName() + " compareAndSet " + re);
        });
        thread.start();
    }
    Thread thread = new Thread(() -> {
        try { Thread.sleep(10); } catch (Exception ignore) {}
        boolean re = count.compareAndSet(10, 5);
        System.out.println(Thread.currentThread().getName() + " compareAndSet " + re);
    });
    thread.start();
}

Typical results (shown in the following images) illustrate that sometimes both threads succeed in setting 5→10, which is the classic ABA problem: the value appears unchanged to a thread that reads it, but it has actually been modified and restored, leading to incorrect assumptions.

Thus the ABA problem arises when a CAS operation cannot detect that a value was changed and restored between reads.

How AtomicStampedReference solves the ABA problem

The solution is simple: after each compareAndSwap, increment a version stamp. Subsequent compareAndSwap operations compare both the data and the stamp, so a change in the stamp prevents a stale compare from succeeding.

public static void main(String[] args) {
    final AtomicStampedReference<Integer> count = new AtomicStampedReference<>(5, 1);
    for (int i = 0; i < 2; i++) {
        Thread thread = new Thread(() -> {
            try { Thread.sleep(10); } catch (Exception ignore) {}
            boolean re = count.compareAndSet(5, 10, 1, 2);
            System.out.println(Thread.currentThread().getName() + "[recharge] compareAndSet " + re);
        });
        thread.start();
    }
    Thread thread = new Thread(() -> {
        try { Thread.sleep(10); } catch (Exception ignore) {}
        boolean re = count.compareAndSet(10, 5, count.getStamp(), count.getStamp() + 1);
        System.out.println(Thread.currentThread().getName() + "[consume] compareAndSet " + re);
    });
    thread.start();
}

Internally, AtomicStampedReference maintains a Pair object (reference + stamp) marked volatile for visibility:

private static class Pair<T> {
    final T reference;
    final int stamp;
    private Pair(T reference, int stamp) {
        this.reference = reference;
        this.stamp = stamp;
    }
}

The compareAndSet method works as follows:

public boolean compareAndSet(V expectedReference,
                             V newReference,
                             int expectedStamp,
                             int newStamp) {
    Pair<V> current = pair;
    return expectedReference == current.reference &&
           expectedStamp == current.stamp &&
           ((newReference == current.reference && newStamp == current.stamp) ||
            casPair(current, Pair.of(newReference, newStamp)));
}

First, it checks whether the supplied reference and stamp match the current Pair. If either differs, the operation fails.

If both match, it returns true without updating.

Otherwise it attempts to update the Pair via casPair, which uses UNSAFE.compareAndSwapObject on the volatile field. casPair performs the low‑level compare‑and‑swap on the combined object.

private boolean casPair(Pair<V> cmp, Pair<V> val) {
    return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
}

In short, AtomicStampedReference solves the ABA problem by coupling the data with a monotonically increasing stamp, ensuring that even if the value returns to its original state, the differing stamp prevents a stale CAS from succeeding. Java also provides AtomicMarkableReference, which uses a boolean flag instead of a numeric stamp, offering a similar but less granular solution.