General interview: What is the ABA problem in CAS, and how do you prevent it?

Prompt and use cases

CAS atomically writes a new value when a shared location still matches an expected value. ABA occurs when thread T1 reads A, pauses, thread T2 changes A to B and back to A, and T1 succeeds because it sees A again without knowing the intermediate change.

Lock-free stacks, queues, and optimistic updates can encounter it. Oracle’s AtomicReference.compareAndSet compares references, while AtomicStampedReference compares a reference and integer stamp together; C++ compare_exchange is a common primitive for lock-free structures. The core category is general: concurrency principles and tradeoffs, independent of Java or C++ syntax.

What the interviewer evaluates

• Whether you can give a precise timeline showing that “back to A” does not mean “unchanged.”
• Whether you understand that CAS checks the supplied representation, not the full history.
• Whether you distinguish ABA from data races, visibility, and object-lifetime bugs.
• Whether you compare version tags, immutable objects, hazard pointers/epochs, and locks at the right boundary.
• Whether you discuss overflow, cost, reclamation, and progress guarantees.

Clarifications before answering

• Does CAS compare a value, a reference, or a versioned composite state?
• Can shared objects be reclaimed or addresses reused? ABA and reclamation often must be designed together.
• Is the requirement lock-free progress or merely correctness? A lock may be simpler and easier to audit.
• Can a version stamp wrap? Define width, lifetime, or wraparound behavior.
• Does the operation update a scalar or a node and its links? The risk depends on the composite invariant.
• Which memory model applies? Atomicity alone does not publish every field or protect lifetime.

30-second answer framework

“ABA is when T1 reads A, T2 performs A→B→A, and T1 then succeeds with stale expected A. CAS proves that the current representation matches; it does not prove that no transition occurred. I would combine the reference with a monotonically changing version stamp, use safe reclamation so addresses are not reused while observed, or choose a lock. I first clarify object lifetime, progress requirements, and stamp overflow before selecting AtomicStampedReference, tagged pointers, or locking.”

Step-by-step deep answer

Step 1: Reconstruct the timeline with a lock-free stack.

The head is A -> B. T1 reads head = A and A.next, preparing to CAS the head to A.next. T1 pauses; T2 pops A, processes B, and pushes the same A or a node whose address is reused. The head representation is A again, so T1 may succeed with a next pointer from an old snapshot.

Step 2: Show why CAS atomicity is not the defect.

CAS is atomic. The expected representation is simply too small: a reference or scalar says nothing about how many transitions occurred or whether the node still represents the same logical state.

Step 3: Separate related concepts.

A data race is an unsynchronized access problem at the language level; ABA can occur even when the CAS is atomic and accesses are synchronized. Visibility determines what a thread can observe. ABA concerns equal current values with different histories. Reclamation determines whether an old pointer can still be dereferenced safely.

Step 4: Add a reference and version stamp.

state = (reference: A, stamp: 7)
T1 reads (A, 7)
T2 changes (A, 7) -> (B, 8) -> (A, 9)
T1 CAS expected (A, 7) -> (C, 8)  // fails

Java’s AtomicStampedReference.compareAndSet compares the reference and stamp together. C++ can use double-width atomics, tagged pointer bits, or a platform-supported composite CAS, but the target platform must actually provide the required atomicity.

Step 5: Handle lifetime and address reuse.

A stamp detects representation changes; it does not make reclamation safe. Non-GC languages may need hazard pointers, epoch-based reclamation, reference counting, or deferred free so a thread never dereferences released memory. GC languages still need to reason about logical reuse of references.

Step 6: Evaluate stamp overflow.

A finite stamp eventually wraps. If a thread holds an old snapshot long enough, a wrapped value may match again. Use a sufficiently wide version, bound snapshot lifetime, use generations that cannot be reused in the window, or choose stronger synchronization. “Add an int” is not an unconditional proof.

Step 7: Compare alternatives.

A lock keeps composite read, update, and lifetime inside one critical section and is often easiest to prove. Immutable data structures express new state with new objects. Transactions or database version columns provide analogous optimistic checks at persistence boundaries. Choose based on contention, latency, complexity, and auditability.

Step 8: Test concurrent correctness.

Build a controlled schedule that pauses T1, lets T2 perform A→B→A, and verifies that an unversioned CAS can succeed while a versioned CAS fails. Add contention, stamp-wrap boundaries, reclamation, and retry tests. A single-threaded unit test cannot establish a lock-free algorithm’s correctness.

High-quality sample answer

“ABA is a state transition hidden by value comparison. T1 reads stack head A and pauses; T2 pops A, performs A→B→A, and pushes A back. T1 sees A and succeeds, potentially writing a next pointer from its stale snapshot. CAS remains atomic; the expected representation lacked version information. I would make reference plus a monotonic stamp one atomic state—AtomicStampedReference in Java, or a verified double-width CAS/tagged pointer in C++—and pair it with hazard pointers or epoch reclamation outside a GC. If contention is low or proof and maintenance dominate, I would use a lock. I would validate with a forced A→B→A schedule and reclamation stress tests.”

Common mistakes

• Calling ABA a failure of CAS atomicity → misstates the primitive → explain the missing history.
• Comparing only node values → different versions can have equal values → compare reference plus version.
• Adding a stamp but ignoring reclamation → a released node can still be dereferenced → design lifetime protection.
• Equating data races with ABA → confuses memory-model and algorithm problems → define them separately.
• Ignoring stamp wraparound → long-running systems retain a match window → define width or lifetime bounds.
• Claiming an API solves every problem → atomic comparison does not guarantee business invariants → state composite and reclamation boundaries.
• Using non-portable pointer-bit tricks → alignment or atomic width may differ → verify the target platform.
• Testing only one thread → the triggering interleaving never occurs → add controlled pauses and stress.

Follow-up questions and responses

Follow-up 1: Why can CAS succeed after A changes to B and back to A?

Ordinary CAS compares the current expected representation. If that representation is only reference A or value A, equality is sufficient; the primitive does not record the intermediate B.

Follow-up 2: Does a version stamp always solve ABA?

It detects A→B→A while the version has not wrapped and the reference-plus-stamp update is atomic. Overflow, non-atomic composite updates, or released nodes require additional design.

Follow-up 3: How do AtomicReference and AtomicStampedReference differ?

AtomicReference atomically compares and updates the reference. AtomicStampedReference treats the reference and integer stamp as one state and compares both, adding allocation and stamp-management cost for change detection.

Follow-up 4: Why do immutable nodes help?

Immutable nodes do not mutate next or business fields in place; new state is represented by a new object, reducing stale-snapshot interference. Reclamation and logical reference reuse still need attention.

Follow-up 5: Does a hazard pointer solve ABA or reclamation?

It primarily prevents reclamation of a node a thread is reading. If an address can still be reused for a different logical node, versioning, tagging, or another ABA defense remains necessary.

Follow-up 6: Why not always use a lock?

A lock is usually easiest to prove and maintain, but it can block and add contention or priority inversion. Prefer it when simplicity dominates; accept lock-free complexity only for a clear progress or latency requirement.

Follow-up 7: How do you prove the repaired stack correct?

Define the composite head state, CAS linearization point, node lifetime, and invariants. Test A→B→A schedules, CAS retries, stamp boundaries, and reclamation stress, then check publication and acquisition ordering against the target memory model.