A compare-and-swap operation answers a narrow question: does a memory location contain the expected bit pattern at the instant of the atomic operation? If it does, the replacement can proceed. The operation does not establish that the location remained unchanged between an earlier read and the later comparison.
That distinction creates the ABA problem. A thread observes value A, pauses, and later performs a compare-and-swap expecting A. During the pause, other work changes the location from A to B and then back to A. The comparison succeeds because the current representation matches the expected representation, even though the shared state passed through a transition that may invalidate assumptions attached to the first observation.
ABA is therefore not a defect in compare-and-swap. It is a mismatch between the history an algorithm needs and the equality that its atomic primitive actually checks.
Equality does not encode continuity
Consider a stack represented by an atomic pointer to its head node. A pop operation can read the head and its successor before attempting to replace the head:
observed = head
next = observed.next
CAS(head, observed, next)Suppose the initial chain is:
head
|
v
A -> B -> CThread T1 reads A as observed and B as next, then pauses. Thread T2 removes A, removes B, and later places A at the head again. The visible pointer can once more equal A, but the chain no longer has to be the chain T1 inspected.
When T1 resumes, CAS(head, A, B) can succeed if the head pointer is again exactly A. The successful comparison says nothing about whether B is still the successor associated with that occurrence of A.
The dangerous assumption is not pointer comparison itself. It is treating pointer equality as evidence that the surrounding logical state has retained the same identity.
Reuse makes the ambiguity sharper
Address reuse can make ABA particularly subtle in pointer-based structures. If storage for a removed node becomes available for allocation, a later object can occupy the same address. A raw pointer comparison can then report equality even though the object at that address belongs to a different allocation lifetime.
This introduces two related but distinct concerns.
The first is logical ABA: a shared atomic value returns to an earlier representation after meaningful intermediate transitions. This can occur even if no memory is freed.
The second is safe memory reclamation: a thread may still hold a pointer to an object that another thread has removed and reclaimed. Dereferencing such a pointer can violate the language or runtime’s memory-safety rules before any compare-and-swap result becomes relevant.
A lock-free design has to account for both when both are possible. Preventing storage reuse while a reader might access a node can solve a reclamation hazard without automatically proving that every logical ABA sequence is harmless. Conversely, adding a version to a pointer can expose intervening changes while still requiring a reclamation scheme for safe dereference.
Tagged state adds history to the comparison
One common response is to compare more than the pointer. The atomic state can pair the pointer with a counter:
(pointer = A, tag = 41)Each successful structural change advances the tag. Removing nodes and later restoring pointer A can then produce:
(pointer = A, tag = 44)The pointer component matches the earlier observation, but the combined state does not. A compare-and-swap expecting (A, 41) fails.
The useful property comes from expanding the identity being compared. The algorithm no longer asks only whether the pointer equals A; it asks whether both pointer and generation marker match the observation.
A finite counter is not an infinite history. If the tag wraps and the complete encoded state returns to an earlier bit pattern while an old observation remains live, ABA can reappear. Whether that is reachable depends on counter width, update rate, and the maximum lifetime of outstanding observations. Treating wraparound as impossible requires an explicit bound or another argument, not merely a large integer type.
The representation also has to fit an atomic operation supported by the target environment. Some platforms provide double-width compare-and-swap; other implementations pack a tag into unused pointer bits when alignment and address rules permit it. Those choices depend on concrete machine and language constraints.
Reclamation schemes change the set of possible histories
Hazard pointers approach the problem from object lifetime rather than by extending pointer identity. A thread publishes the object it may dereference. A remover can unlink that object, but reclamation is deferred while another thread advertises a hazard for it.
The publication protocol requires care. A reader generally has to publish the candidate pointer and then confirm that the shared location still contains the candidate. Otherwise removal can occur between the initial load and hazard publication.
Epoch-based reclamation uses a broader lifetime boundary. Threads announce participation in an epoch or read-side critical region, and removed objects are retained until no participant that could have observed them remains active. This delays reuse without requiring one hazard record per protected pointer.
Both models constrain address reuse. That matters because an address cannot represent a new allocation while its old storage is still protected from reclamation. Yet their effect on logical ABA depends on the data structure. If the same live node can be removed and reinserted while another operation retains an observation, preventing deallocation alone does not distinguish the two appearances of that node.
The correct argument is structure-specific: identify the transitions that can occur during an outstanding observation, then establish whether those transitions can restore a comparison value while invalidating associated state.
Garbage collection removes one hazard, not the entire pattern
Managed memory can eliminate a class of use-after-free errors because an object reachable from a thread is not reclaimed as unreachable storage. That does not make the ABA pattern impossible.
A data structure can remove object A, mutate other links, and reinsert the same object A. An atomic reference can again equal the earlier reference. If an operation relies on more than reference identity, the intermediate transitions can still matter.
Garbage collection therefore changes the reclamation argument. It does not change the semantics of compare-and-swap: equality at the atomic instant remains equality at that instant.
Not every A-to-B-to-A sequence is a bug
ABA matters only when the intermediate transition destroys an invariant assumed by the pending operation. Some algorithms are insensitive to the history between observation and compare-and-swap. If all state relevant to correctness is captured by the compared value, returning to the same value can be acceptable.
This is an important boundary. Detecting every repeated value is not a general goal. The engineering question is whether a successful atomic update can commit work derived from information that ceased to be valid during an unseen transition.
For the stack sketch, the cached successor next creates such a dependency. T1’s proposed update was computed from the relation A.next == B observed earlier. Comparing only head == A does not revalidate that relation.
An alternative algorithm may arrange its state so the compare-and-swap covers all information needed for the transition, or it may re-read dependent state after gaining a suitable form of ownership. In either case, the proof obligation becomes more precise: the atomic comparison must guard every mutable fact whose earlier value is required for the proposed update.
Memory ordering addresses a different dimension
It is tempting to associate ABA with weak memory ordering because both appear in lock-free code. They are separate issues.
Acquire and release semantics can constrain which writes become visible around an atomic synchronization event. Sequentially consistent atomics can provide a single total order for the relevant atomic operations. None of those ordering guarantees turns a compare-and-swap into a historical comparison.
Under sequential consistency, the sequence A -> B -> A can be perfectly well ordered and fully visible in the abstract execution. A later compare-and-swap expecting A can still succeed. Stronger ordering can make observations easier to reason about, but it does not attach a generation number to a repeated value.
A correct design therefore needs separate arguments for ordering and identity. One establishes which effects an operation can observe; the other establishes whether the compared state contains enough information to reject an invalidated observation.
The real boundary is the observation’s identity
The most useful way to examine ABA is to start from the pending operation’s observation. That observation often contains more meaning than the atomic word used at commit time: a pointer plus assumptions about links, an index plus assumptions about a slot generation, or a handle plus assumptions about the resource currently occupying it.
Compare-and-swap can protect that observation only to the extent that its expected value represents the same identity. When the representation can cycle back while the associated meaning changes, a successful comparison is weaker than the algorithm requires.
Tagged state, constrained reuse, reclamation protocols, and redesigned state representations all address this gap from different directions. Their common purpose is not to make compare-and-swap stronger. It is to make the state presented to compare-and-swap carry enough identity for a successful result to mean what the algorithm needs it to mean.