Non-Blocking Algorithm¶

A concurrent shared-object procedure whose operation-progress guarantee does not depend on a paused thread releasing exclusive ownership.

Version: v1 · 2026-10-03 · History
Domain-specific #: 13465
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Concurrent Algorithms → Computer Science & Software Engineering
Aliases: Nonblocking Algorithm

Core Idea¶

A non-blocking algorithm specifies operations on a shared concurrent object such that a thread delayed or stopped inside an operation does not become an exclusive owner whom all other threads must await. Its name describes a progress property of the complete operation, not the mere absence of a mutex call or the fact that a processor provides an atomic instruction. Interleaved operations still need a correctness argument; the progress claim states what can complete when other participants are delayed or interfere.^[1]^[2]

The familiar strengths differ. Obstruction-free means an operation finishes after enough execution without interference, even if other threads remain paused in partial operations; it may fail to progress under continuing conflicts. Lock-free strengthens this to system-wide progress—some active operation finishes—even though one unlucky thread may starve. Wait-free gives each active operation completion within a bounded number of its own steps under the stated model. These are progress guarantees, not performance rankings or promises that every operation has low latency.^[1]

Structural Signature¶

Sig role-phrases:

Concurrent shared-state operation: two or more threads may attempt changes to the same queue, deque or other object. Without overlapping operations the special progress problem disappears.^[1]^[2]
Interference-safe transition: the algorithm maintains object correctness despite interleaving, using suitable atomic reads/writes or read-modify-write operations; compare-and-swap is common but not a universal defining primitive.^[1]^[2]
Declared progress condition: the proof or specification identifies solo, some-thread or each-thread completion, together with scheduling assumptions. A lock-free instruction embedded inside a larger blocking protocol does not suffice.^[1]
No stalled exclusive owner: a halted participant cannot hold a critical section whose release is required for all peers' operations to finish. This does not mean no retry, no backoff, or no temporary interference.^[1]^[2]

Helping, contention management, version counters, ABA prevention and reclamation are design techniques or hazards that may matter to a particular implementation; none is a mandatory slot in every non-blocking algorithm.^[1]^[2]

What It Is Not¶

A spinlock can use atomic compare-and-swap and still be blocking: if its winner pauses before releasing the flag, all others wait. Conversely, an obstruction-free algorithm is non-blocking although conflicting threads may repeatedly prevent one another from finishing. Do not silently equate the family with lock-freedom or wait-freedom.^[1]

It is not merely an atomic variable, nor simply a thread-safe collection. Correctness properties such as FIFO order or linearizability and progress properties such as lock-freedom answer distinct questions. A correct queue could block; an apparently fast queue could lose items under a race. Michael and Scott discuss both the queue operation and practical ABA/reclamation issues rather than treating an atomic instruction as proof of the whole design.^[2]

Scope of Application¶

Michael and Scott's 1996 linked FIFO queue uses head and tail pointers and compare-and-swap to make a non-blocking queue operation. Oracle's Java documentation explicitly describes ConcurrentLinkedQueue as a linked FIFO collection using an efficient non-blocking algorithm based on that paper; this is a library-level application of the shared-object pattern.^[2]^[3]

Herlihy, Luchangco and Moir's 2003 double-ended queues give a distinct strength of guarantee: their array implementations are obstruction-free. A thread that runs long enough alone can complete even if another thread has paused, but sustained collisions do not trigger a formal system-wide completion promise. The two examples share stalled-owner independence while differing in object structure and progress tier.^[1]

Clarity¶

State the operation, data structure, memory model and progress tier. Ask whether “lock-free” describes a primitive, one method, or the entire object API. For a queue, specify whether a successful enqueue/dequeue is the completion counted by the guarantee, and separately show that concurrent outcomes satisfy the abstract FIFO specification.^[2]

The meaning of wait-free is not “without operating-system waiting” in casual prose; it is a formal per-operation step bound. The meaning of lock-free is not “every caller succeeds promptly”; one caller may be repeatedly overtaken while the object as a whole advances. The meaning of obstruction-free depends on the isolation condition.^[1]

Manages Complexity¶

The abstraction organizes designs by the dependency that would let one paused actor stop everyone. It separates an algorithm's safety—valid states and results under interleaving—from its liveness/progress under a scheduler. This prevents a mistaken transfer from “uses CAS” to “cannot block,” while still allowing CAS, LL/SC, or other suitable primitives to be chosen for a concrete object.^[1]^[2]

It also exposes a design cost: stronger individual-progress guarantees can demand more complex synchronization, while weaker obstruction-freedom may leave contention resolution to a separate policy. Neither formal tier by itself predicts throughput on a particular machine.^[1]

Abstract Reasoning¶

For operation \(o\) on shared state \(S\), distinguish a safety invariant \(I(S)\) from a progress quantifier. Obstruction-freedom asks whether \(o\) finishes when it takes enough steps without conflicting steps by other threads. Lock-freedom asks whether an infinite execution with active operations can continue without any operation finishing; the answer must be no under the specified model. Wait-freedom bounds the steps for each participating operation. These quantifier differences explain why a lock-free queue can admit starvation while an obstruction-free deque can admit continuing contention without global completion.^[1]

An atomic transition can protect \(I(S)\) but does not prove a progress quantifier. Likewise, a method's retries may be acceptable under lock-freedom if repeated failed CAS attempts mean other methods successfully changed state; for obstruction-freedom, the proof instead uses eventual solo execution. The exact proof obligations must be checked for each implementation.^[1]^[2]

Knowledge Transfer¶

The linked FIFO queue and array deque transfer shared state / interleaving-safe update / progress tier / halted-peer test. Do not transfer the queue's head-tail pointers to a deque, or assume the deque's solo-completion guarantee upgrades to lock-freedom. In a language runtime, library documentation may identify the algorithmic lineage but still leave API-specific operations with different costs and atomicity boundaries; Oracle warns, for example, that ConcurrentLinkedQueue's bulk operations are not all atomic and size is not constant-time.^[2]^[1]^[3]

The generalizable question is: If a participating thread pauses after any step, can other active operations still complete under the claimed condition? The answer must come from the actual state machine and progress proof, not from a performance benchmark or the absence of a keyword.^[1]

Examples¶

Michael–Scott FIFO queue. Mapped back: shared object = linked FIFO queue; transitions = CAS on links and head/tail pointers; progress = lock-free system-wide completion; stalled-peer test = a preempted caller does not retain an exclusive queue lock that everyone else needs. The original paper also treats ABA and node reuse as concrete engineering issues rather than defining features of all non-blocking objects.^[2]

Herlihy–Luchangco–Moir deque. Mapped back: shared object = array-based double-ended queue; transitions = CAS with versioned array values; progress = obstruction-free completion when one operation eventually runs without interference; stalled-peer test = another thread's paused partial action does not require lock-owner release. Continuing conflicting calls can still prevent completion, unlike a lock-free guarantee.^[1]

Structural Tensions¶

Global progress versus individual fairness. Lock-freedom keeps the object moving but can leave one caller retrying indefinitely. Diagnostic: Does the application require some operation to finish, or a bound for every caller? A real-time deadline cannot be inferred from “lock-free.”^[1]

Simpler solo progress versus contention. Obstruction-freedom can simplify an implementation by proving solo completion, yet simultaneous conflicts may require backoff or contention management for useful throughput. Diagnostic: What happens when the contending threads never yield an isolation interval?^[1]

Atomic update versus lifetime management. A compare-and-swap may linearize a pointer change while memory reuse or ABA undermines safety. Diagnostic: What prevents an observed pointer from being freed, reused or mistaken for its earlier version before the update? The answer is implementation-specific.^[2]

Structural–Framed Character¶

Evaluative weight. The progress guarantee is a mathematical property under a declared concurrent model; whether its performance is desirable is a separate engineering judgment. A lock-free implementation can still have poor latency for a particular thread or workload.^[1]

Human-practice bound. Programmers choose object semantics, memory model and retry policy, but the progress claim is tested against possible execution histories, not conferred by the author's intention to avoid locks. Institutional origin. The vocabulary comes from concurrent-algorithm research and systems practice; a particular processor, language or library is not part of the definition.^[1]

Vocabulary travel. “Operation,” “progress” and “schedule” transfer literally among shared-memory queues, deques and other concurrent objects once their execution model is specified. “Non-blocking” in ordinary human workflow or network I/O can mean something else. Import versus recognition. In a new concurrent implementation, classify by its formal system- or thread-progress quantifier; outside concurrent computation, calling a process non-blocking imports the word by analogy rather than recognizing this identity.^[1]

Its character: mixed-structural—a formal progress property of algorithms, sharply bounded by concurrent object semantics and scheduling assumptions.

Structural Core vs. Domain Accent¶

Portable skeleton. Live Algorithm supplies the broader identity of a procedure whose steps and success conditions can be specified. The staged strict edge to Algorithm is defensible because both the queue and deque are algorithms; the additional progress quantifier, not a missing lock instruction, narrows the class.^[1]

Domain-bound mechanism. Here success is quantified over overlapping operations under a scheduler and a shared-memory object model. The Michael–Scott queue gives lock-free System progress; the cited deque design gives obstruction-free solo progress. CAS appears in both designs but is not a universal structural role. ABA, memory reclamation, contention policy and throughput are separate implementation or performance dimensions.^[2]^[1]

Why not prime. One can export the broad idea of avoiding stalled ownership to other domains, but that does not preserve the formal lock-free or obstruction-free guarantees. Without atomic state, interleavings and a named progress quantifier, a human workflow or sequential routine is only an analogy; the live Algorithm prime carries the portable procedure skeleton, while this identity remains a domain-specific concurrent specialization.

This entry is a kind of Algorithm.

The staged strict genus is live Algorithm: a non-blocking algorithm is a computational procedure with an additional concurrent progress constraint. Live Concurrency supplies the overlapping-execution setting. Live Synchronization in the encyclopedia concerns phase/frequency entrainment, so its name is a false friend for computer-science “non-blocking synchronization”; live Mutual Exclusion names the ownership discipline this family avoids, not its parent. No canonical edge has been applied.

Relationships to Other Abstractions¶

Current abstraction Non-Blocking Algorithm Domain-specific

Parents (1) — more general patterns this builds on

Non-Blocking Algorithm is a kind of Algorithm Prime

A non-blocking algorithm is an executable concurrent procedure with an additional independent-progress condition.

Hierarchy paths (2) — routes to 2 parentless roots

Non-Blocking Algorithm → Algorithm → Function (Mapping)

Show alternative path (1)

Neighborhood in Abstraction Space¶

Non-Blocking Algorithm sits in a sparse region of the domain-specific corpus (78^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2551 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Lock-free is a stronger member of the broad non-blocking family than obstruction-free. Wait-free is stronger again in its per-caller guarantee. Deadlock-free for a lock-based implementation may permit a paused lock owner to halt peers, so it does not imply non-blocking. Asynchronous I/O is another use of “non-blocking,” concerning a call's waiting behavior rather than progress of concurrent shared-object operations.^[1]

References¶

[1] Maurice Herlihy, Victor Luchangco and Mark Moir, “Obstruction-Free Synchronization: Double-Ended Queues as an Example,” Proceedings of the 23^rd IEEE International Conference on Distributed Computing Systems (2003), 522–529, Introduction and §§3–4. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y

[2] Maged M. Michael and Michael L. Scott, “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms,” Proceedings of the 15^th ACM Symposium on Principles of Distributed Computing (1996), 267–275, Introduction, §2 and Fig. 1. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n

[3] Oracle, Java Platform SE 8 ConcurrentLinkedQueue class documentation, class description. registry ↩a ↩b