Non-Blocking Algorithm¶
A concurrent shared-object procedure whose operation-progress guarantee does not depend on a paused thread releasing exclusive ownership.
Core Idea¶
A non-blocking algorithm operates on shared concurrent state without making all other active callers depend on one paused thread releasing an exclusive lock. The guarantee belongs to the whole operation, not merely to an atomic instruction. Obstruction-free guarantees completion after enough solo execution; lock-free guarantees some active operation completes; wait-free guarantees each active operation bounded-step progress under the stated model.[^ref-d9e1c22f9338]
Scope of Application¶
Michael and Scott's linked FIFO queue is a lock-free case using compare-and-swap; Oracle documents a library queue based on it. Herlihy, Luchangco and Moir's array-based deque is an obstruction-free case: a paused peer does not own a lock, but sustained conflicts need not yield system-wide progress. These are unlike progress tiers, not evidence that all non-blocking objects use CAS or helping.[ref-7118dfc945b7][ref-0885461ab620][^ref-d9e1c22f9338]
Clarity¶
Name the object operation, state-transition correctness, memory model and precise progress tier. A CAS-based spinlock is still blocking if its owner can pause while others wait. Lock-free does not imply fairness for each thread; obstruction-free does not imply progress under continuous contention. ABA and safe reclamation may matter in a specific pointer-based design but are not universal definitional roles.[ref-d9e1c22f9338][ref-7118dfc945b7]
Manages Complexity¶
The identity separates safety under interleaving from liveness under delay. It also separates formal progress from measured throughput: a stronger guarantee is not automatically faster. Comparing a linked queue with an array deque reveals the common stopped-owner test while preserving different structures and guarantees.[ref-d9e1c22f9338][ref-7118dfc945b7]
Abstract Reasoning¶
Let an operation update shared state while other threads may interleave or halt. Ask whether a halted participant retains exclusive ownership required by every peer. Then quantify progress: one operation after isolation, some operation despite ongoing activity, or each operation within its own step bound. That quantifier—not the brand of atomic primitive—classifies the non-blocking strength.[^ref-d9e1c22f9338]
Knowledge Transfer¶
Transfer shared object / interleaving-safe transition / progress condition / stalled-peer test from the FIFO queue to the deque. Do not transfer a lock-free claim to the obstruction-free implementation or infer per-operation latency from a system-wide guarantee. The staged strict parent is live prime Algorithm; no canonical graph edge has been applied.[ref-7118dfc945b7][ref-d9e1c22f9338]
[^ref-d9e1c22f9338]: Maurice Herlihy, Victor Luchangco and Mark Moir, “Obstruction-Free Synchronization: Double-Ended Queues as an Example,” ICDCS (2003), 522–529, Introduction and §§3–4. [^ref-7118dfc945b7]: Maged M. Michael and Michael L. Scott, “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms,” PODC (1996), 267–275, Introduction, §2 and Fig. 1. [^ref-0885461ab620]: Oracle, Java Platform SE 8 ConcurrentLinkedQueue documentation, class description.
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)
Neighborhood in Abstraction Space¶
Non-Blocking Algorithm sits in a sparse region of the domain-specific corpus (78th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2551 abstractions)
Nearest neighbors
- Release Consistency — 0.84
- Queue (FIFO Abstract Data Type) — 0.83
- Lockstep (computing) — 0.83
- Proof of correctness — 0.82
- Dynamic Problem — 0.82
Computed from structural-signature embeddings · 2026-10-08