Compare-and-swap: equal bits can hide changed history
Trace CAS success and failure, distinguish weak spurious failure from interference, and expose ABA and lifetime hazards.
On this page
The question for today
What you’ll understand
- Trace a compare-exchange retry loop using the updated expected value.
- Construct an ABA history that defeats a naive pointer-only check.
- Distinguish version validation from the safe reclamation of a referenced object.
Compare-and-swap, usually exposed as compare-exchange in C++, conditionally changes one atomic value if it still matches an expected value. That makes it valuable for optimistic updates. Yet equal bits do not necessarily mean the world has stayed unchanged since a thread first inspected them. A node can disappear, memory can be reused, and a pointer can regain its old numeric address. Understanding those histories is essential before building a stack, free list, or lock-free queue.
Read the success and failure contracts separately
In the simple value model, compare-exchange checks the atomic object's value against expected. Success writes desired as a read-modify-write and reports success. Failure leaves the atomic unchanged and updates expected with the observed value, so a retry must recompute any desired value that depended on the old expected state. C++ comparison is specified in terms of value representation with details for particular types; avoid transferring the integer mental model blindly to padding, floating values, or arbitrary object layouts.
Weak compare-exchange may fail spuriously even when the compared values match, so loops must tolerate such failure. Strong compare-exchange avoids that kind of spurious failure but still fails when another update wins. The success path and failure load have separate ordering requirements. Failure is not a store and must not be given release or acquire-release ordering. Choose legal orderings for the targeted C++ version from the algorithm's publication and read requirements, rather than treating every failure as evidence of another completed operation.
ABA is a history problem
Consider a stack headed by node A followed by B. A thread reads head A and remembers next B, then pauses before changing head to B. Another thread removes A and B, changes the structure, and eventually puts A back with a different successor. A pointer-only CAS can now see head A again and succeed in restoring the stale B. The endpoint value matched, but the path between observations invalidated the first thread's assumptions. The stack's correctness depends on that history, not merely current pointer equality.
A tagged pointer or combined pointer-and-version value can detect intervening updates if the tag is changed appropriately and does not wrap during the relevant vulnerable interval. The pair must be compared atomically using a supported representation; two independent atomics do not give the same check. Tags do not by themselves make dereferencing a retired node safe. Safe reclamation schemes such as hazard pointers or epochs address object lifetime under their own protocols, and can also prevent particular reuse-based ABA histories.
Put validation before unsafe use
A retry loop does not excuse reading freed memory before the CAS. If next is loaded from a node that another thread can destroy immediately, the program may already be invalid even if the final CAS fails. Establish a lifetime protection protocol before dereferencing. Then validate that the protected pointer is still the one the algorithm intends to use. The order of protection, revalidation, dereference, logical removal, and eventual destruction is part of the algorithm, not housekeeping that can be added afterward.
The reliability lab offers a narrow lesson about summaries. Choose replica count five and unavailable count two, then predict whether the displayed majority remains available; increase unavailable count to three and compare. Equal counts in different moments cannot reveal which individual histories occurred, just as a matching pointer value cannot reconstruct intervening updates. This diagram computes majority availability only. It has no CAS, object identity, memory reuse, or ABA detector, and majority availability says nothing by itself about memory safety or a correct stack.
Work it through
Calculate a tag's vulnerable wrap interval
An illustrative combined pointer-and-tag design uses an eight-bit tag and increments it on every successful head update. A documented hard window bound permits at most 100 updates in any 0.1-second interval, and therefore at most 300 in 0.3 seconds. Can it exclude tag wrap while a reader pauses for 0.3 seconds?
An eight-bit tag has 256 states. Returning to the same tag requires 256 increments, while returning to the same pointer value may occur sooner or later depending on the history.
The hard window bound permits as many as 300 updates during the 0.3-second pause. Since 300 exceeds 256, these bounds do not exclude a complete tag cycle. An average update rate alone would be weaker evidence because bursts can violate a count inferred from its average.
For a 0.1-second pause the same bound permits at most 100 updates, which excludes tag wrap in that interval. Still require atomic pointer-and-tag comparison and a separate safe lifetime protocol; this arithmetic establishes only the bounded tag argument.
The 0.3-second pause is too long for this particular eight-bit no-wrap argument. Widening a tag without bounding reader delay gives more time before wrap, not an unconditional solution.
The living notebook
Explore the model
Interactive lab · reliability
A summary value omits history
Set n=5 and k=2 to predict majority availability, then raise k to three. The model counts available replicas only; it does not model CAS, tagged pointers, ABA, reclamation, or consistency.
- Available replicas
- 4 of 5
- Majority needed
- 3
- Majority available?
- Yes
A replica count and a majority threshold, without a consensus protocol. Playback highlights fixed replica states. Having a majority alone does not establish linearizability, durability or failure independence. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forAn endpoint summary cannot prove that an assumption remained valid throughout an intervening history.
Pause & reason
Check your understanding
Your turn
Try it yourself
A CAS loop loads counter value ten and computes desired eleven. CAS fails and updates expected to twelve. What must the retry recompute for an increment operation? Separately, can a pointer CAS validate a next field that was already read from freed memory?
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Follow the operation's mathematical intent, then ask when the lifetime violation occurs.
Compare with the solution
The increment retry computes desired thirteen from the newly observed twelve, rather than blindly retrying eleven and potentially reducing the counter. It must also tolerate any further failures according to its progress contract. For the pointer case, a later success or failure cannot retroactively make the earlier dereference safe. The algorithm needs a reclamation protocol that protects the node before reading next, plus revalidation and the required memory ordering. The value update and the lifetime guarantee solve different problems.
Keep the idea
Take it with you
- A failed compare-exchange updates expected; dependent desired state must be reconsidered.
- ABA concerns changed history hidden behind a repeated value.
- Version tags require atomic comparison and wrap assumptions, while safe dereference requires lifetime protection.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.