Mathematics matters in lock-free queues because many threads can attempt to change a shared structure at nearly the same time, yet every completed operation must still fit a valid sequential story. The code cannot rely on a single global lock to choose the winner. Instead, it uses atomic comparison, carefully selected linearization points, retry loops and a memory-reclamation scheme that prevents recycled storage from masquerading as old state.
For students asking why mathematics is important in computing, lock-free programming connects logic, sets of possible histories, invariants, graph-shaped pointer structures, probability and expected cost. It also teaches humility. A short fragment of atomic code can have far more possible interleavings than lines on the page, and an algorithm that returns correct values in one test may still be wrong under a rare schedule.
Quick Reading Routes
- Students can begin with compare-and-swap, the ticket analogy and the two-thread enqueue example.
- Parents and teachers can use the card simulation and invariant checklist without writing unsafe code.
- Computing learners can focus on linearizability, progress conditions, the Michael–Scott queue and ABA.
- Practitioners can review memory ordering, helping, reclamation, backoff, measurement and verification limits.
Concurrency Creates Many Possible Histories
In a sequential program, operation A finishes before operation B begins. With two threads, individual steps can interleave. If each thread has three relevant steps, there may be many order-preserving merges of those steps.
The number of interleavings of m ordered steps from one thread and n from another is the binomial coefficient C(m+n,m). For three steps each, C(6,3)=20. Four threads and loops produce an explosion that ordinary testing cannot enumerate.
Interleavings preserve local order
Thread A’s second instruction cannot appear before its first, but instructions from thread B may fall between them. This partial-order view is more precise than saying “everything happens at once.”
Timing is not a proof
Adding a delay can make a bug appear or disappear. It changes the schedule but does not establish correctness for all permitted schedules. We need invariants and a formal way to interpret completed operations.
Why Locks Are Useful—and Why Some Algorithms Avoid Them
A mutex can make one thread enter a critical section while others wait. Locks are often the clearest correct choice. Lock-free does not mean “better than locks” in every workload.
Some systems seek non-blocking progress because a paused lock holder can delay everyone, priority inversion can matter, or a library cannot safely block in a context. A lock-free algorithm guarantees system-wide progress under its model: if threads keep taking steps, some operation completes. It does not guarantee that every particular thread completes promptly.
Lock-free is not wait-free
Wait-free means each operation completes within a bounded number of its own steps. Lock-free is weaker: one unlucky thread may retry repeatedly while others succeed. Obstruction-free is weaker again, generally guaranteeing progress only when a thread eventually runs without interference.
Freedom from locks is not freedom from coordination
Atomic variables, cache coherence, memory ordering and reclamation still coordinate threads. The cost moves rather than vanishes.
Compare-and-Swap as a Conditional State Transition
Compare-and-swap, often abbreviated CAS, takes an address, an expected value and a desired value. Atomically, it asks whether the current value equals expected. If yes, it stores desired and reports success. If no, it leaves the current value unchanged and reports failure, commonly updating the caller’s expected value.
A mathematical predicate
CAS succeeds when current=expected at the atomic comparison point. The state transition is therefore conditional:
- if x=e, set x:=d and return success;
- otherwise keep x unchanged and return failure.
No other thread can observe half of this transition.
Retry loop
A thread reads state s, computes candidate f(s), and attempts CAS(s,f(s)). Failure means the shared state changed; the thread reloads and recomputes. This is optimistic concurrency: proceed assuming no conflict, then validate the assumption at commit.
Spurious failure
Some APIs offer weak comparison operations that may fail even when values compare equal. They are intended for loops. The language specification, not intuition, determines exact behaviour. The current C++ working draft gathers atomic requirements in its atomic operations clauses.
A One-Variable Example
Suppose atomic x begins at 10. Threads A and B both read 10. A wants 11; B wants 12.
A performs CAS(expected=10,desired=11) and succeeds. B then performs CAS(expected=10,desired=12) and fails because x is now 11. B reloads, decides whether 12 is still the correct transformation and retries.
Only one winner
The equality test turns competing proposals into one committed state change. The failed thread did not partially modify x.
Recompute when meaning depends on state
For an increment, B should propose 12 after seeing 11. For an update based on more complex structure, it must rebuild the proposal from the new state. Blindly retrying an obsolete desired value can violate the algorithm’s intent.
Linearizability Gives a Sequential Meaning
Linearizability asks whether each concurrent operation can be assigned one instantaneous effect point between its invocation and response so that the resulting order obeys the object’s sequential specification and real-time precedence.
If operation A returns before operation B begins, A must appear before B. Operations whose intervals overlap may be ordered either way if the object’s rules permit it.
Maurice Herlihy and Jeannette Wing introduced the formal condition in their paper Linearizability: A Correctness Condition for Concurrent Objects. The definition is powerful because each object can be reasoned about locally and then composed with other linearizable objects.
Dequeue linearization point
Many algorithms have a particular atomic step that makes an operation logically take effect. A successful pointer CAS may linearize an enqueue. A dequeue may linearize when it advances the head or when it claims a slot, depending on the algorithm.
Helping complicates ownership
The thread that performs the linearizing step need not be the thread that began the operation. In helping algorithms, one thread completes a structural step on behalf of another. Correctness follows the history, not a story about personal ownership.
The Sequential Queue Contract
A first-in, first-out queue supports enqueue(v), which adds v at the rear, and dequeue(), which removes the earliest remaining value or reports empty.
The sequential invariant can be represented as a finite list. Enqueue appends; successful dequeue removes the first item. Concurrent implementation details may contain dummy nodes or lagging pointers, but the abstract queue must still match some legal list history.
A history example
Enqueue(A) completes, then enqueue(B) begins and completes, then dequeue returns A. Any linearization must keep those non-overlapping operations in that order. If two enqueues overlap, either may linearize first, but later dequeues must reflect the chosen order.
Empty is time-sensitive
A dequeue that overlaps an enqueue may legally return empty or the new item depending on its linearization point. A dequeue that begins after the enqueue has completed cannot pretend the queue was still empty.
A Linked Queue Shape
A common non-blocking queue uses linked nodes and a dummy node. Head points to a node before the first logical item; tail points at or near the last node. Each node has a next pointer.
The dummy node simplifies empty and single-item cases. When head and tail refer to the same node and its next is null, the abstract queue is empty.
Useful invariants
- Following next pointers from head never creates a cycle in the intended structure.
- Enqueued nodes become reachable in one forward chain.
- Tail never points before head in the logical chain.
- A dequeued value is returned at most once.
- A node is not reclaimed while another thread may still dereference it.
The last invariant belongs to memory reclamation and is just as important as pointer linking.
Enqueue in the Michael–Scott Style
The classic Michael–Scott non-blocking queue provides a widely studied design and public pseudocode: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms.
A simplified enqueue allocates a node with next=null, reads tail and tail.next, validates that tail remained stable, and then tries to CAS tail.next from null to the new node. That successful link makes the new value reachable and is the enqueue’s usual linearization point.
Tail can lag
After linking, the enqueuer tries to advance tail to the new node. If it pauses before doing so, another thread may observe tail.next non-null and help advance tail. The queue remains logically correct because reachability, not the advisory tail pointer alone, establishes membership.
Why two CAS operations
One CAS links the node; another improves the rear pointer. Combining both into one ordinary pointer CAS is not generally possible because they occupy distinct memory locations. The algorithm is designed so lag is safe.
Two Concurrent Enqueues
Suppose tail points to dummy D and D.next is null. Threads A and B prepare nodes A1 and B1.
Both read the same tail and see null. A wins CAS(D.next,null,A1). B’s CAS fails because D.next is now A1. A may advance tail, or B may notice the link and help.
B then rereads the current end, finds a null next pointer after A1 and links B1. The abstract order is A then B because A’s link CAS occurred first.
The loser still contributes
B’s failed attempt is not corruption. It is evidence that the state advanced. Helping tail and retrying moves the structure toward completion.
Expected retries
If k threads contend for one null link at once, at most one first attempt succeeds and up to k−1 fail. Real arrival times spread attempts, but contention raises wasted CAS work and coherence traffic.
Dequeue and the Dummy Node
A simplified dequeue reads head, tail and head.next, then validates that head remained unchanged.
If head equals tail and next is null, the queue is empty. If head equals tail but next is non-null, tail is lagging; the thread helps advance it and retries. Otherwise next identifies the first logical value. A CAS advances head from the old dummy to next.
Returning the value
The algorithm must read the value before another thread can reclaim or reuse the node. After successful head advancement, the old dummy is retired, and next becomes the new dummy. Exact ordering and reclamation rules are essential.
Linearization point
For this form, successful head CAS commonly linearizes the dequeue. Competing dequeuers may read the same first node, but only one advances head from the observed value. The loser retries and cannot return the same item.
The ABA Problem
CAS compares bit patterns, not histories. A thread can read value A, pause, and later see A again. CAS succeeds even if the location changed A→B→A in between.
If identity and intervening changes matter, equality of the current bits is insufficient. This is the ABA problem.
A free-list story
Thread T1 reads head pointer A and next pointer B from a free list, then pauses. T2 pops A, pops B, and pushes A back. Head is A again, but A.next may now refer elsewhere. T1’s CAS from A to stale B can succeed and damage the list.
The mathematics of lost history
The mapping from histories to current pointer value is many-to-one. A single value cannot reveal whether zero or several transitions occurred. Add a version counter and compare the pair (pointer,version); A with version 7 differs from A with version 9.
Tags can wrap
A finite version field eventually wraps. Its width must make harmful reuse impossible within the maximum period a stale observer can survive, or the algorithm needs another safety mechanism. “Use a tag” is not a complete proof.
Memory Reclamation Is Part of Correctness
Removing a node from the abstract queue does not mean no thread holds a raw pointer to it. Freeing immediately can cause use-after-free. Reusing the address can intensify ABA.
Hazard pointers
A thread publishes the node it may dereference. A remover retires nodes and reclaims only those absent from all hazard sets after appropriate checks. Scanning P threads’ hazard slots gives a cost related to P and the number of retired nodes batched per scan.
Epoch-based reclamation
Threads announce participation in epochs. A node retired in one epoch is reclaimed after every relevant thread has passed a safe boundary. This amortises checks but a stalled participant can delay reclamation and increase memory use.
Reference counting
References are counted so reclamation occurs at zero. Atomic reference changes can be expensive, cycles require care, and acquiring a reference safely from a raw pointer is itself subtle.
Garbage collection
In a managed runtime, tracing collection can prevent premature reuse, but the queue still needs correct atomic publication and memory ordering. Garbage collection solves lifetime, not the whole algorithm.
Memory Ordering and Publication
Linking a node publishes data written during its construction. Another thread that observes the link must also observe the initialised fields according to the language memory model.
Release operations can make earlier writes visible to an acquiring reader that synchronizes through the published pointer. Relaxed operations may be sufficient for some advisory fields but not for transferring ownership of ordinary data.
Sequential consistency is easier, not free
The strongest standard ordering often simplifies reasoning but can restrict hardware or compiler reordering more than necessary. Weaker orders may improve performance on some platforms, yet every weakening creates proof obligations.
Compiler and hardware are both involved
Source order is not automatically execution order. The programming-language model constrains compiler transformations and maps to hardware instructions. Correct explanations should name the level being discussed.
Progress Reasoning
Lock-free progress proofs often show that a failed CAS implies another thread changed the state. Repeated personal failure therefore accompanies global success.
System progress
If a thread’s enqueue CAS fails because the link is no longer null, some enqueuer linked a node. If head CAS fails, another dequeuer advanced head. Under fair enough execution assumptions, infinitely many failures imply infinitely many completed state changes.
Starvation remains possible
One thread can repeatedly lose. Backoff, elimination, combining or scheduler policy may improve practical fairness, but those are separate properties from lock-freedom.
Preemption
A preempted thread should not hold a lock needed by everyone. It may still publish a hazard pointer or occupy an epoch, delaying reclamation. Non-blocking progress and resource progress are related but not identical.
Contention and Expected Work
Let λ be attempted operations per second and p the probability an attempt collides and retries. If each attempt independently succeeds with probability 1−p, a geometric model gives expected attempts 1/(1−p).
At p=0.1, expected attempts are about 1.11. At p=0.5, they are 2. At p=0.9, they are 10. Independence is a simplification—collisions often cluster—but the curve shows why performance can collapse nonlinearly.
CAS cost includes coherence
Atomic read-modify-write often needs exclusive cache-line ownership. Many contenders can bounce the line between cores. A lock-free algorithm may guarantee progress while throughput falls from communication.
Backoff
After failure, waiting a randomized or increasing interval can reduce synchronized retries. Too much backoff wastes capacity and adds latency. Tune with workload evidence.
Capacity and Bounded Queues
A bounded ring queue replaces node allocation with fixed slots. Producer and consumer positions grow conceptually and map to slots by modulo capacity.
Sequence numbers can distinguish generations of a reused slot. If capacity is C, position p maps to p mod C, while a per-slot sequence indicates whether the slot belongs to the expected turn.
Wraparound
Finite counters wrap. Correctness requires modular comparisons that remain unambiguous within the maximum distance between active positions. Treating an unsigned counter as an infinite integer without proof is dangerous.
Full and empty
Head equals tail can mean empty, but modulo indexes alone cannot distinguish empty from a complete wrap. Monotonic positions, sequence numbers or an extra bit resolve the ambiguity.
Measuring a Queue
Throughput alone can conceal starvation and latency spikes. Record operations per second, median latency, high percentiles, retry counts, allocation rate and memory retained for reclamation.
Workload dimensions
- producer-to-consumer ratio;
- queue occupancy;
- item size and processing time;
- thread placement and NUMA topology;
- burstiness;
- duration long enough to include reclamation;
- oversubscription and preemption.
Compare suitable baselines
Compare against a well-engineered blocking queue and, if relevant, a single-thread queue. The simplest correct design may win at low contention. A result from one machine is not a universal ranking.
Verification Techniques
Code review should begin with the sequential contract, invariants and linearization points, not syntax.
Stress tests vary schedules and repeat operations. Linearizability checkers compare recorded invocation/response histories with the sequential specification. Model checkers explore reduced state spaces. Sanitizers can find some races and lifetime errors.
Bounded exploration is still bounded
Exhaustively checking two threads and a tiny queue builds confidence but does not automatically prove arbitrary size, counter wraparound or allocator behaviour. State the explored bounds.
Reclamation deserves its own tests
Delay threads after publishing hazards, hold epochs open, force address reuse and run long enough for counters to wrap where feasible. Rare lifetime schedules are often the point.
Misconceptions to Avoid
“Lock-free means no waiting”
Threads can spin and retry. The guarantee concerns global progress, not zero delay.
“One successful CAS proves the whole operation”
Only if the algorithm identifies it as the correct linearization point and all supporting invariants and memory-order rules hold.
“ABA means CAS is broken”
CAS correctly compares values. The algorithm asked a weaker question than it needed: equality without history.
“Garbage collection makes concurrent structures easy”
It can solve premature reclamation, but atomic publication, ordering, linearizability and progress remain.
“A faster benchmark means a better queue”
Correctness, tail latency, fairness, memory growth, portability and maintainability also matter.
Which Mathematics Matters Most?
Combinatorics counts interleavings. Logic states invariants. Partial orders distinguish real-time precedence from overlap. Linearizability maps a concurrent history to a legal sequential order. Modular arithmetic handles ring positions. Probability estimates retries. Graphs describe linked reachability. Amortised analysis spreads reclamation scans across operations.
The deeper benefit is transfer. The same habits apply to databases, distributed systems and collaborative software: propose a change, validate the observed version, identify the commit point and preserve objects until no observer can use them.
A Student Learning Path
Stage 1: Interleave paper steps
Write three ordered actions for thread A and three for B. List several of the 20 legal merges without changing local order.
Stage 2: Simulate CAS
Use one numbered card as shared state. Two students write expected and desired values. Only the proposal matching the current card can replace it.
Stage 3: Define the queue contract
Test short sequential histories. Decide exactly when empty is legal and which item a dequeue must return.
Stage 4: Mark linearization points
On pseudocode, circle the atomic step that commits each operation. Explain why earlier and later steps are preparation or cleanup.
Stage 5: Add reclamation
Track which students still hold a node card. Do not recycle it until the chosen hazard or epoch rule says it is safe.
Guidance for Parents and Teachers
Avoid beginning with production lock-free code. Start with histories and a physical queue of cards. Let two learners overlap operations and ask for a valid sequential explanation.
Separate three questions: Is the returned answer correct? Does some operation keep completing? Is removed memory safe to reuse? Students often collapse these into one idea.
Celebrate counterexamples. Finding a six-step schedule that breaks an attractive algorithm is mathematical success. It shows the learner has moved from example-following to invariant testing.
Use the topic to revisit combinations, functions, modular arithmetic and expected value. Advanced learners can read published pseudocode and compare it with a language library instead of implementing memory-unsafe experiments alone.
Did You Know?
A queue’s tail pointer can be temporarily wrong without the queue being wrong. If newly linked nodes remain reachable from head, another thread can help tail catch up.
An operation may be completed by a different thread from the one that began it. Helping turns apparent interference into progress.
The same address can refer to different lifetimes. Pointer equality alone cannot prove object identity across reclamation and reuse.
Frequently Asked Questions
Is lock-free always faster than a mutex?
No. At low contention a mutex-based queue may be simpler and faster. Under high contention, retry traffic can be costly.
Can a lock-free algorithm deadlock?
By definition it should maintain system-wide progress under its assumptions, but surrounding code can deadlock, memory allocation can block and a faulty implementation can violate the guarantee.
What is the easiest linearization point?
There is no universal choice. It is the atomic event that makes the operation’s abstract effect unavoidable. Identify it from the proof.
Why use a dummy node?
It unifies empty and non-empty pointer manipulation, reducing special cases. The first logical item sits after the dummy.
Does CAS prevent data races on every field?
No. It atomically updates its target. Other fields need correct publication, atomicity or exclusive ownership.
How is ABA different from a normal conflict?
A normal CAS conflict changes the compared value and causes failure. ABA hides intervening change by restoring the same visible value.
Can I implement this for a school project?
Prefer a safe simulation or a trusted library. Production non-blocking memory management is advanced and easy to get subtly wrong.
What is the most transferable lesson?
Define the abstract contract, mark the commit event and prove invariants across every permitted interleaving.
Useful Next Reading
- Read Why Mathematics? | Message Queues, Arrival Rates, Backlogs and Delivery Guarantees for queueing at distributed-system scale.
- Compare with Why Mathematics? | Database Transactions, Atomicity, Isolation and Concurrency for another form of atomic commitment.
- Revisit Why Mathematics? | Cache Coherence, Cache Lines, False Sharing and Invalidation Traffic after publication to connect CAS retries with ownership traffic.
- Use the Mathematics Learning Hub for broader school-level mathematics routes.
Practice Lab: Reasoning About Four Histories
History 1: Non-overlapping operations
Enqueue(A) is invoked and returns. Only afterwards is dequeue invoked, and it returns empty. No placement of linearization points can satisfy the queue contract because real-time precedence forces enqueue before dequeue. This is a short counterexample: the implementation is not linearizable, regardless of internal timing. Students should learn to reject an impossible history before inspecting code.
History 2: Overlap permits choice
Dequeue begins, then enqueue(A) begins and completes, then dequeue returns empty. The intervals overlap because dequeue was already active when enqueue started. A legal linearization can place dequeue just before enqueue, so empty is allowed. If the same dequeue returned A, placing enqueue first would also be legal. Linearizability preserves completed-before-invoked order, not the wall-clock order of every internal step.
History 3: Two consumers
The queue contains A. Dequeues D1 and D2 overlap, and both return A. No legal sequential FIFO history removes the same item twice. Even if both threads read the node before either CAS, only the successful head-advance operation may claim it. A failed contender must retry. This illustrates why the return value must be tied to the committing transition.
History 4: Helping
Enqueuer E links node B after tail but pauses before advancing tail. Dequeuer D observes the non-null next pointer, advances tail and continues. E later wakes and finds tail already moved. The abstract enqueue can still have linearized at E’s link CAS. D’s maintenance step does not steal the value; it repairs an advisory pointer. Students should mark logical membership separately from optimisation metadata.
A Reclamation Calculation
Assume 16 threads, two hazard-pointer slots per thread and a retired list scanned after every 64 removals. One scan checks up to 32 published hazards against 64 retired nodes. A naive nested check makes 2,048 pointer comparisons per batch, or about 32 comparisons per removal. Sorting hazards or using a set changes constants. Increasing the batch to 256 spreads one scan over more removals but retains more memory. This is amortised analysis attached directly to a safety rule.
Now consider a stalled thread that keeps one hazard pointer for ten seconds while removers retire one million nodes per second. If every retired node might be the protected one and the scheme cannot separate generations, memory can grow sharply. Practical designs retire in batches, identify unprotected nodes and ensure stalled participants do not prevent unrelated reclamation forever. The progress theorem for queue operations does not automatically bound retained memory.
Choosing Between Designs
Use a lock-based queue when its critical section is short, blocking is acceptable and clarity matters most. Use a bounded ring when capacity is known and allocation must be controlled. Consider a mature lock-free implementation when pausing a holder is unacceptable or measurements show contention that the algorithm genuinely reduces. In every case, prefer a trusted library to a fresh pointer algorithm.
The decision table should include correctness proof, progress guarantee, maximum memory, fairness, peak throughput, tail latency, portability and maintenance skill. “No mutex” is only one column. This wider comparison keeps mathematics connected to engineering judgment rather than turning lock-freedom into a badge.
Final Perspective
One final proof habit is to separate safety from liveness. Safety says something bad never happens: no duplicated dequeue, no broken link, no dereference after reclamation. Liveness says something good eventually happens: some operation completes, a retired node is eventually reclaimed or a waiting producer eventually obtains capacity. A trace can satisfy one and violate the other.
Write the assumptions beside the guarantee. Lock-free progress may assume threads continue taking steps and atomic operations eventually return. Reclamation progress may assume threads leave read-side sections. Bounded queues may reject or block when full. Schedulers, allocators and page faults sit outside a narrow algorithm proof but affect the deployed system.
For a final exercise, compare three implementations on the same history: one mutex queue, one linked lock-free queue and one bounded ring. Mark where each commits, how it handles full or empty state, what happens if a thread pauses and when storage can be reused. The point is not to crown a winner. It is to see that each design pays for correctness with a different combination of serialization, metadata, retries and capacity constraints.
This perspective also protects students from unsafe imitation. Atomic syntax can look compact while the proof is large. Using a maintained library is not avoiding mathematics; it is respecting how much mathematics and testing the abstraction contains.
A Compact Review Exercise
Take a history with two overlapping enqueues and two dequeues. Draw invocation and response intervals on a timeline. List every sequential order consistent with real-time precedence, then eliminate orders that violate FIFO returns. If one order survives, the history is linearizable; if none survive, it is not. For larger histories, exhaustive enumeration becomes expensive, motivating specialised checkers and reductions.
Next label each implementation event as read, local computation, atomic transition or reclamation action. Only a justified atomic transition can serve as the operation’s commit point. A destructor or memory free that occurs later cannot retroactively decide which value the dequeue returned. This classification keeps abstract history separate from storage cleanup.
Lock-free queues turn concurrency from a blur of timing into a mathematical object. Histories become partial orders. Successful atomic transitions become linearization points. Invariants protect the linked shape. Versioning and reclamation preserve identity across time. Expected retries explain performance under contention.
The optimistic lesson is that difficult concurrency can be reasoned about. We do not need to guess which thread was “really first.” We specify the legal sequential behaviour, record real-time constraints and prove that every concurrent execution can be placed within them. Mathematics supplies the language that makes that proof possible.