Understanding the ABA Problem in CAS and Solving It with AtomicStampedReference

The article introduces the ABA problem that arises when a value is changed from A to B and back to A during a CAS operation, making the original thread believe the value has not been modified.

Illustration with Building Blocks

A visual analogy uses a series of shape replacements (triangle → star → pentagon → … → triangle) to demonstrate how intermediate changes can be hidden from the original thread.

Java Code Demonstration

First, a simple BuildingBlock class is defined:

/**
 * Building block class
 */
class BuildingBlock {
    String shape;
    public BuildingBlock(String shape) {
        this.shape = shape;
    }
    @Override
    public String toString() {
        return "BuildingBlock{shape='" + shape + "'}";
    }
}

Three instances are created:

static BuildingBlock A = new BuildingBlock("三角形"); // triangle
static BuildingBlock B = new BuildingBlock("四边形"); // quadrilateral
static BuildingBlock D = new BuildingBlock("五边形"); // pentagon

An AtomicReference<BuildingBlock> holds the initial value:

static AtomicReference
atomicReference = new AtomicReference<>(A);

Thread “乙” performs the ABA sequence:

new Thread(() -> {
    atomicReference.compareAndSet(A, B); // A → B
    atomicReference.compareAndSet(B, A); // B → A
}, "乙").start();

Thread “甲” later tries to replace A with D after a short delay, assuming the value is unchanged:

new Thread(() -> {
    try { TimeUnit.SECONDS.sleep(1); } catch (InterruptedException e) { e.printStackTrace(); }
    System.out.println(atomicReference.compareAndSet(A, D) + "\t" + atomicReference.get());
}, "甲").start();

The output shows true and the new shape, confirming that the ABA problem allowed the replacement.

Consequences of ABA

Real‑world scenarios such as inventory deduction or water‑consumption tracking can suffer from hidden intermediate changes, leading to incorrect results.

Solution with Versioned Atomic References

Using AtomicStampedReference adds a version stamp to each update, preventing ABA because the stamp must also match.

Key method signature:

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

Example usage:

AtomicStampedReference
atomicStampedReference =
    new AtomicStampedReference<>(A, 1);

// Thread “乙” performs ABA with stamp updates
int stamp = atomicStampedReference.getStamp();
atomicStampedReference.compareAndSet(A, B, stamp, stamp + 1);
atomicStampedReference.compareAndSet(B, A, stamp + 1, stamp + 2);

// Thread “甲” attempts to replace A with D using the original stamp
boolean result = atomicStampedReference.compareAndSet(A, D, 1, 2);
System.out.println("Success? " + result + " Current stamp: " +
    atomicStampedReference.getStamp());

Because the stamp has changed (now 3), the compare‑and‑set fails, effectively preventing the ABA issue.

Conclusion

The article explains why ABA occurs, demonstrates its impact with code and real‑world analogies, and recommends using versioned atomic references like AtomicStampedReference to detect and avoid hidden intermediate modifications.