How to Learn Concurrent Algorithms: Linearizability, Compare-and-Swap, Lock-Free Progress and Memory Reclamation

Wait, What?

Two threads can each execute perfectly sensible code and still combine into a result that no sensible single-threaded program would ever produce.

Concurrent algorithms begin when correctness depends not only on what operations do, but on how operations from several threads interleave. The beginner sees two pieces of code. The professional sees a space of possible histories, visibility rules, atomic steps, progress guarantees and memory-lifetime hazards.

Quick Answer

Learn concurrent algorithms through the route interleavings → race conditions → atomicity → mutual exclusion → linearizability → compare-and-swap → lock-free and wait-free progress → concurrent queues and stacks → ABA problem → memory ordering → safe reclamation → adversarial scheduling → professional testing. Never judge a concurrent algorithm from one successful run. Judge it across the histories the scheduler is allowed to create.

1. Start With Interleavings, Not Threads

Suppose two threads both execute counter = counter + 1. A beginner may imagine that the result must increase by two. But the operation can decompose into read, add and write. If both threads read the same old value before either writes, one increment can disappear.

The first learning move is therefore to expand a compact line of code into the smaller actions that matter. This is similar to learning recursion by tracing the call stack: hidden structure becomes visible before abstraction is restored.

2. A Race Condition Is a Correctness Problem, Not Merely a Speed Problem

A race occurs when the outcome depends on timing or ordering between operations that are not safely coordinated. The danger is not simply that one execution is slower. Different schedules may produce different states, including states that violate the data structure’s specification.

Lost update: two writes overwrite one another.
Check-then-act race: a condition is true when checked but false when acted upon.
Read-modify-write race: an update is not atomic.
Publication race: another thread observes an object before construction is safely visible.

3. Atomicity Defines the Indivisible Step

An atomic operation appears indivisible with respect to competing operations. This does not mean it literally consumes zero time. It means other threads cannot observe it half-completed in the way the algorithm’s model forbids.

Professional reasoning starts by asking which actions are atomic in the language and hardware model being used. Assuming atomicity where none exists invalidates the proof.

4. Locks Make a Critical Section Exclusive

A mutex protects a critical section so that only one thread enters at a time. Locks can turn a difficult interleaving problem into a simpler sequential one inside the protected region. But they introduce their own design questions: lock ordering, contention, deadlock, starvation, priority inversion and the size of the critical section.

Do not learn concurrency as “locks are bad, lock-free is good.” Locks are often the clearest correct tool. The algorithmic question is which correctness and progress properties the application requires.

5. Linearizability Gives a Powerful Correctness Target

Herlihy and Wing’s classic definition of linearizability says that each operation on a concurrent object should appear to take effect at one instant between its invocation and response, while respecting real-time ordering. This lets programmers reason about a concurrent object as though operations occurred in a legal sequential order.

See Herlihy and Wing, Linearizability: A Correctness Condition for Concurrent Objects. Brown University’s CS1760 Multiprocessor Synchronization places linearizable concurrent structures alongside mutual exclusion, wait-free and lock-free synchronization.

6. Find the Linearization Point

When proving a concurrent stack or queue, look for the atomic event that commits the logical effect of the operation. A successful compare-and-swap may be that moment. Before it, the operation has not logically happened. After it, the operation must be visible in any valid sequential explanation.

This gives learners a concrete proof question: where, exactly, did this operation become true?

7. Compare-and-Swap Turns a Guess Into a Conditional Commit

Compare-and-swap, often exposed as compare-exchange, performs a conditional atomic update: “If this memory location still contains the value I observed, replace it with the new value; otherwise report failure.”

This supports an optimistic pattern:

read current state;
construct a candidate new state;
attempt an atomic conditional update;
if another thread changed the state first, retry from fresh information.

Current C/C++ atomic libraries expose compare-exchange and memory-order controls. See cppreference: Atomic operations library.

8. Lock-Free Does Not Mean Every Thread Always Makes Progress

Progress guarantees need precise language.

Obstruction-free: an operation completes if it eventually runs without interference.
Lock-free: the system as a whole keeps making progress; some individual operation may repeatedly lose races.
Wait-free: every operation completes within a bounded number of its own steps.

These are stronger and stronger guarantees, and they often cost more design complexity or resources.

9. Build a Lock-Free Stack by Reasoning About One Pointer

A classic Treiber-style stack can store a pointer to the current head. To push, construct a new node whose next pointer targets the observed head, then compare-and-swap the head to the new node. If another thread changed the head first, rebuild the candidate and retry.

The important lesson is not the code pattern. It is the invariant: the head always points to a valid top node, and a successful atomic head change commits exactly one push or pop.

10. A Concurrent Queue Requires More Than Two Independent Pointers

Queues often maintain head and tail state, so the proof must account for intermediate states. A tail may temporarily lag behind the newest node. An algorithm can remain correct if other threads are permitted to help advance it.

This introduces an advanced idea: helping. In some non-blocking algorithms, one thread may complete part of another thread’s pending structural update so the shared data structure continues progressing.

11. The ABA Problem Shows Why “It Looks the Same” May Be False Evidence

Suppose a thread reads pointer value A, pauses, and later sees A again. It may assume nothing changed. But another thread could have changed A → B → A in the meantime. The raw value is identical while the history is different.

Possible defences include tagged/versioned pointers, hazard pointers, epoch-based reclamation or algorithms whose invariants make ABA harmless. The important reasoning habit is to distinguish value equality from state-history equivalence.

12. Memory Reclamation Is Part of the Algorithm

A node removed from a lock-free structure cannot necessarily be freed immediately. Another thread may still hold a pointer to it from an earlier read. Reusing or freeing that memory too soon can produce use-after-free failures that are far outside the clean pseudocode proof.

Hazard pointers announce which nodes a thread may still access.
Epoch-based schemes delay reclamation until all relevant readers have moved beyond an epoch.
Reference counting tracks ownership but can add contention and other complications.

Professional concurrency therefore joins algorithm design with memory-lifetime design.

13. Memory Ordering Controls Visibility, Not Just Atomicity

Modern compilers and processors may reorder independent operations. Atomic variables often support several memory-order strengths. Sequentially consistent ordering is easier to reason about; weaker acquire/release or relaxed orderings can permit more optimisation but demand a more careful visibility proof.

Do not begin by memorising every memory-order enum. First learn the question: which writes must become visible before which reads?

14. Deadlock, Livelock and Starvation Are Different Failure States

Deadlock: threads wait in a cycle and no relevant operation can proceed.
Livelock: threads keep reacting but fail to complete useful work.
Starvation: the system progresses while one thread may be indefinitely denied progress.

Classifying the failure correctly determines the repair. A deadlock may need lock-order discipline; starvation may need fairness; livelock may need backoff or asymmetric retry behaviour.

15. Testing Must Search for Bad Histories

A concurrent algorithm can pass millions of ordinary tests and still contain a rare interleaving bug. Useful validation deliberately perturbs timing:

insert yields or sleeps at sensitive points;
run high-contention workloads;
vary thread counts and CPU affinity;
repeat operations under sanitizers and race detectors;
record operation histories and check whether a legal linearization exists;
test reclamation under delayed readers.

The broader discipline from How Professionals Evaluate Algorithms applies here with one extra demand: the scheduler becomes part of the adversarial test environment.

16. Common Learning Failure States

Assuming one successful execution proves correctness.
Calling several operations “atomic enough” without checking the language memory model.
Confusing thread safety with linearizability.
Calling a structure wait-free when only system-wide lock-free progress is guaranteed.
Ignoring node reclamation after a logically correct delete.
Using compare-and-swap without handling retries.
Reducing memory-order questions to performance tuning.
Testing only low-contention happy paths.

17. A Beginner-to-Professional Learning Ladder

Level 1: manually interleave two read-modify-write sequences.
Level 2: identify a race and repair it with a mutex.
Level 3: distinguish atomicity from mutual exclusion.
Level 4: linearize a short history of stack operations.
Level 5: trace a compare-and-swap retry loop.
Level 6: implement a simple lock-free stack under safe memory management assumptions.
Level 7: explain obstruction-free, lock-free and wait-free progress.
Level 8: detect ABA and propose a valid mitigation.
Level 9: reason about acquire/release visibility.
Level 10: validate a concurrent structure under hostile scheduling and reclamation stress.

18. Read and Reconstruct Before Writing

Advanced concurrent code is too compressed to be a good first encounter. Start from execution histories, diagrams and partially completed code. Research on Parsons problems shows that reconstructing ordered code can scaffold learners who are not yet ready to generate the full implementation from a blank page. See Hou, Ericson and Wang (ICER 2022).

PRIMM similarly emphasises Predict–Run–Investigate–Modify–Make, giving learners a route from code comprehension to independent construction. See Sentance, Waite and Kallia (SIGCSE 2019).

19. Immediate, Delayed and Transfer Checks

Immediate: show one schedule that loses an increment.
Atomicity: identify the linearization point of a successful update.
Progress: classify a guarantee as blocking, lock-free or wait-free.
ABA: construct an A → B → A history.
Reclamation: explain why logically removed does not mean safe to free.
Delayed: rebuild the correctness argument without the source code.
Transfer: decide whether a mutex, concurrent queue, lock-free counter or immutable snapshot best fits four different workloads.

20. AI Assistance Boundary

AI can generate adversarial interleavings, explain memory-order diagrams and suggest test histories. The learner should still be able to identify shared state, state the invariant, locate linearization points, classify progress guarantees and explain memory-lifetime safety independently.

Professional Direction

Advanced study includes Michael–Scott queues, elimination stacks, concurrent hash tables, read-copy-update, transactional memory, hazard pointers, epoch reclamation, flat combining, universal constructions, weak-memory verification and model checking. At professional level, the question is not “Can I make this code run without locks?” It is “Can I state the exact correctness, progress, memory and visibility guarantees—and defend them under every allowed interleaving?”

Algorithm-learning rule: in concurrency, one trace is an example; the algorithm is the set of all traces your assumptions permit.