There is a point in systems programming where concurrency stops being about “running things at the same time” and starts becoming a conversation about guarantees.

Most programmers first learn concurrency through locks.

You have shared data.

You protect it with a mutex.

One thread enters.

Everyone else waits.

It works.

Then eventually you encounter a system where waiting is not acceptable.

Maybe you are building a low-latency event pipeline.

Maybe a telemetry collector receives millions of events per second.

Maybe a network runtime has producers generating work faster than consumers can process it.

Maybe you are building an operating-system component, a game engine subsystem, a high-frequency message pipeline, or a distributed systems primitive.

Suddenly, “just use a mutex” is no longer an interesting answer.

You start asking different questions.

Can a thread make progress without waiting for another thread?

Can a producer enqueue an item even if another producer has stalled?

Can a consumer continue operating if another consumer disappears halfway through an operation?

Can the data structure guarantee that the system keeps moving even when threads are delayed by the scheduler?

This is where wait-free algorithms enter the picture.

And this is where Rust becomes particularly interesting.

Rust gives us ownership, borrowing, atomics, memory ordering, and a type system designed to make many classes of concurrent memory bugs difficult to express.

But Rust does not magically make a concurrent queue wait-free.

You still have to understand the algorithm.

In this article, we are going to build one.

Not merely a queue with atomics.

A queue with a stronger progress guarantee.

We will explore:

• what wait-free actually means,
• how wait-free differs from lock-free and obstruction-free algorithms,
• why queues are difficult,
• how atomic operations become synchronization primitives,
• the role of memory ordering,
• how a bounded ring buffer works,
• how sequence numbers solve the producer/consumer ownership problem,
• how to implement a practical bounded wait-free queue in Rust,
• what the algorithm guarantees,
• where the implementation can still become subtle,
• and why “wait-free” is really a statement about time bounds, not merely the absence of mutexes.

The Queue Looks Innocent

A queue seems like one of the simplest data structures ever invented.

You put things in one end.

You take them out of the other.

Conceptually:

Producer
   |
   v
+-----+-----+-----+-----+-----+
|  A  |  B  |  C  |  D  |  E |
+-----+-----+-----+-----+-----+
                              |
                              v
                           Consumer

A sequential implementation is trivial.

use std::collections::VecDeque;

let mut queue = VecDeque::new();

queue.push_back(10);
queue.push_back(20);

let value = queue.pop_front();

But concurrency changes the problem.

Imagine two producers:

Producer A ----\
                \
                 ---> Queue
                /
Producer B ----/

Both may attempt:

queue.push_back(item);

at approximately the same time.

Now imagine two consumers:

                 ---> Consumer A
                /
Queue ---------
                \
                 ---> Consumer B

Both may attempt to remove the same element.

The problem is no longer:

“How do I store values?”

The problem becomes:

“How do multiple CPUs agree about ownership of memory without corrupting the queue?”

That is a much deeper question.

The Three Progress Guarantees

Before writing code, we need to understand what wait-free means.

Concurrent algorithms are often classified by progress guarantees.

There are three important levels.

Obstruction-Free

An operation completes if it eventually gets to execute without interference from other threads.

Imagine:

Thread A
   |
   |---- works
   |
Thread B stops interfering
   |
   v
operation completes

But if other threads continuously interfere, progress is not guaranteed.

This is the weakest guarantee of the three.

Lock-Free

A lock-free algorithm guarantees that the system as a whole makes progress.

Even if one thread gets delayed, some other thread can complete an operation.

For example:

Thread A ----X
             |
             | stalled
             |
Thread B -----------> succeeds

Thread A may starve forever.

But the system does not completely stop.

Someone makes progress.

This is already a powerful guarantee.

Wait-Free

Wait-free is stronger.

A wait-free algorithm guarantees that every operation completes in a bounded number of steps, regardless of what other threads are doing.

Imagine:

Thread A ----X
             |
             | stalled forever
             |
Thread B -----------------> succeeds
Thread C -----------------> succeeds
Thread D -----------------> succeeds

Thread A's progress does not depend on Thread B, C, or D.

More importantly, Thread B, C, and D also have bounded completion.

The important phrase is:

bounded number of steps

Not:

“probably fast.”

Not:

“doesn't use locks.”

Not:

“uses atomic operations.”

Wait-free is a formal progress property.

Why Mutexes Are Not Enough

Consider:

use std::sync::Mutex;
use std::collections::VecDeque;

struct Queue<T> {
    inner: Mutex<VecDeque<T>>,
}

This is perfectly valid concurrent Rust.

But it isn't wait-free.

Consider:

Thread A
   |
 acquire mutex
   |
   X
   |
 crashes / pauses
   |
   |
   v
 mutex remains unavailable

Thread B
   |
 waits
   |
 waits
   |
 waits

Thread B's progress depends on Thread A.

That's precisely what wait-free algorithms attempt to eliminate.

The challenge is therefore:

How can multiple threads coordinate without requiring one another to release a lock?

The answer begins with atomics.

Atomics Are the Building Blocks

Modern CPUs provide atomic operations.

For example:

use std::sync::atomic::{AtomicUsize, Ordering};

let counter = AtomicUsize::new(0);

counter.fetch_add(1, Ordering::Relaxed);

Multiple threads can modify counter concurrently.

The CPU guarantees that the operation itself is indivisible.

But there is a catch.

Atomicity is not enough.

You also need memory ordering.

Atomicity vs Ordering

Suppose a producer does:

buffer[index] = value;
ready.store(true, Ordering::Release);

And the consumer does:

if ready.load(Ordering::Acquire) {
    let value = buffer[index];
}

The important relationship is:

Producer                    Consumer

write value
    |
    v
Release store -----------> Acquire load
                                |
                                v
                          read value

The release/acquire pair creates a synchronization relationship.

If the consumer observes the release operation, it can safely observe the preceding writes.

This is one of the most important ideas in lock-free programming.

The Queue We Will Build

We are going to build a bounded multi-producer, multi-consumer queue using a ring buffer.

Bounded means the queue has a fixed capacity.

For example:

capacity = 8

+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---+---+---+---+---+---+---+---+

When we reach the end, we wrap around:

0 -> 1 -> 2 -> ... -> 7 -> 0 -> 1

This avoids allocating memory for every enqueue.

But there is an interesting problem.

Suppose position 3 contains an item.

After the consumer removes it, how does a future producer know that position 3 is available again?

We need more than a simple index.

We need sequence numbers.

Sequence Numbers

Each slot stores metadata describing which logical queue position currently owns it.

Conceptually:

Slot

+-----------------------+
| sequence              |
+-----------------------+
| value                 |
+-----------------------+

Suppose capacity is 4.

Initially:

slot       sequence

0          0
1          1
2          2
3          3

The producer reserves position 0.

It writes:

value = A

and eventually advances the slot's state.

The consumer recognizes that position 0 contains a value.

After consuming it, the consumer changes the sequence so that the slot becomes available for the next generation.

Now position 4 maps back to physical slot 0.

logical position 4
        |
        v
physical slot 0

But the sequence number tells us:

This isn't the old position 0. It is the next generation of position 0.

This is a beautiful trick.

The physical array stays fixed.

The logical positions keep increasing.

The Ring Buffer Model

We maintain two atomic counters:

enqueue_pos
dequeue_pos

Think of them as monotonically increasing logical positions.

For example:

enqueue_pos = 17
dequeue_pos = 14

means approximately three elements are currently in the queue.

The physical slot is determined by:

index = position % capacity

For a power-of-two capacity, we can optimize this further using bit masking.

But modulo is easier to understand initially.

The Slot State

Each slot has:

struct Slot<T> {
    sequence: AtomicUsize,
    value: UnsafeCell<MaybeUninit<T>>,
}

There are two interesting pieces.

AtomicUsize tracks the slot state.

MaybeUninit<T> gives us manually controlled storage for T.

Why MaybeUninit?

Because we don't want to construct every T ahead of time.

If the queue has capacity 1024, we want 1024 storage locations, not 1024 initialized values.

Why Unsafe Appears

Eventually we reach the uncomfortable part.

Concurrent queues often require some unsafe.

That doesn't mean:

“Rust failed.”

It means:

“We are stepping outside Rust's normal aliasing guarantees, and we must prove that our synchronization makes it safe.”

Consider:

UnsafeCell<MaybeUninit<T>>

This allows us to mutate the slot without requiring ordinary Rust borrowing.

That is necessary because several threads may own references to the queue simultaneously.

But we must establish an invariant:

At most one thread accesses a slot's T value at any given time.

The atomic sequence number is what helps us enforce that invariant.

Designing the Queue

Our structure will look roughly like:

pub struct WaitFreeQueue<T> {
    buffer: Box<[Slot<T>]>,
    enqueue_pos: AtomicUsize,
    dequeue_pos: AtomicUsize,
    mask: usize,
}

Each slot:

struct Slot<T> {
    sequence: AtomicUsize,
    value: UnsafeCell<MaybeUninit<T>>,
}

We will use a power-of-two capacity.

For example:

8
16
32
64
128

Then:

index = position & mask

where:

mask = capacity - 1

For capacity 8:

mask = 7

position   index

0          0
1          1
2          2
3          3
4          4
5          5
6          6
7          7
8          0
9          1

Initialization

Each slot begins with a sequence corresponding to its initial position.

for i in 0..capacity {
    slots[i].sequence.store(i, Ordering::Relaxed);
}

So:

slot       sequence

0          0
1          1
2          2
3          3
4          4
5          5
6          6
7          7

The enqueue position starts at zero.

The dequeue position starts at zero.

Enqueue

Now we reach the heart of the algorithm.

A producer wants to enqueue an element.

First, it reserves a logical position.

Conceptually:

position = enqueue_pos.fetch_add(1)

Suppose it gets:

position = 5

The physical slot is:

index = position & mask;

If the capacity is 8:

5 & 7 = 5

So slot 5 is our target.

Now the producer waits for the slot's sequence to indicate that it belongs to this enqueue generation.

In a traditional lock-free algorithm, we may repeatedly retry.

That is important because retry loops can undermine wait-freedom.

So we need to distinguish two things:

atomic reservation
        +
bounded completion

If the operation can repeatedly spin an unbounded number of times, it is not automatically wait-free.

This is where the engineering becomes more subtle.

The Strict Wait-Free Problem

Here's the uncomfortable truth:

A lot of things marketed as “wait-free queues” are actually lock-free queues.

Why?

Because their core algorithm looks like:

loop {
    let pos = tail.load(...);

    if try_reserve(pos) {
        break;
    }
}

The operation may succeed quickly.

But there is no fixed upper bound on the number of failed attempts.

Therefore:

No locks
    ≠
Wait-free

and:

Atomic operations
    ≠
Wait-free

A strict wait-free implementation needs a bounded helping or bounded reservation strategy.

For educational purposes, we can build a bounded queue around atomic slot ownership where each operation performs a fixed amount of synchronization work.

That distinction matters enormously.

A Practical Bounded Design

One approach is to use a fixed number of slots and deterministic ticket positions.

Each producer obtains a ticket:

let position = self.enqueue_pos.fetch_add(1, Ordering::Relaxed);

Because fetch_add is atomic, every producer gets a unique position.

Then:

let index = position & self.mask;

The sequence number tells the producer whether that slot belongs to its generation.

The consumer does the same thing with dequeue_pos.

The key idea is:

logical position
        |
        v
sequence number
        |
        v
ownership of physical slot

The Implementation

Here is a compact implementation of the core bounded queue.

use std::cell::UnsafeCell;
use std::mem::MaybeUninit;
use std::sync::atomic::{AtomicUsize, Ordering};

struct Slot<T> {
    sequence: AtomicUsize,
    value: UnsafeCell<MaybeUninit<T>>,
}

unsafe impl<T: Send> Send for Slot<T> {}
unsafe impl<T: Send> Sync for Slot<T> {}

pub struct WaitFreeQueue<T> {
    buffer: Box<[Slot<T>]>,
    enqueue_pos: AtomicUsize,
    dequeue_pos: AtomicUsize,
    mask: usize,
}

unsafe impl<T: Send> Send for WaitFreeQueue<T> {}
unsafe impl<T: Send> Sync for WaitFreeQueue<T> {}

The Send and Sync implementations deserve attention.

We require:

T: Send

because values may cross thread boundaries.

The queue itself can then be shared between threads.

Constructing the Queue

We need a power-of-two capacity.

impl<T> WaitFreeQueue<T> {
    pub fn with_capacity(capacity: usize) -> Self {
        assert!(capacity.is_power_of_two());
        assert!(capacity > 0);

        let mut slots = Vec::with_capacity(capacity);

        for i in 0..capacity {
            slots.push(Slot {
                sequence: AtomicUsize::new(i),
                value: UnsafeCell::new(MaybeUninit::uninit()),
            });
        }

        Self {
            buffer: slots.into_boxed_slice(),
            enqueue_pos: AtomicUsize::new(0),
            dequeue_pos: AtomicUsize::new(0),
            mask: capacity - 1,
        }
    }
}

Now the queue starts empty.

Writing an Element

The producer obtains a ticket:

let position =
    self.enqueue_pos.fetch_add(1, Ordering::Relaxed);

Then:

let index = position & self.mask;
let slot = &self.buffer[index];

We need to ensure the slot belongs to this generation before writing.

Conceptually:

let sequence =
    slot.sequence.load(Ordering::Acquire);

If:

sequence == position

the slot is ready for the producer.

Then:

unsafe {
    (*slot.value.get()).write(value);
}

After writing the value:

slot.sequence.store(
    position + 1,
    Ordering::Release,
);

That release store publishes the value.

Why Release Matters

Imagine:

Producer

write(T)
   |
   v
Release sequence store
   |
   |
   v
Consumer
Acquire sequence load
   |
   v
read(T)

The release operation tells the compiler and CPU:

All writes before this operation must become visible before this synchronization state is published.

The acquire tells the consumer:

Once I observe that published state, I can safely observe the preceding writes.

Without correct ordering, a CPU could theoretically observe the synchronization flag before observing the data write.

That's the kind of bug that makes concurrent programming terrifying.

Your code can look perfectly logical.

Your tests can pass.

And the CPU can still ruin your afternoon.

Reading an Element

The consumer obtains a dequeue position:

let position =
    self.dequeue_pos.fetch_add(1, Ordering::Relaxed);

Then calculates:

let index = position & self.mask;

It checks:

let sequence =
    slot.sequence.load(Ordering::Acquire);

When the sequence indicates that the producer has published the value, the consumer reads:

let value = unsafe {
    (*slot.value.get()).assume_init_read()
};

After consuming the value, the consumer marks the slot available for the next cycle:

slot.sequence.store(
    position + self.mask + 1,
    Ordering::Release,
);

Because:

mask + 1 = capacity

this effectively advances the generation.

The Full Core

A simplified educational version looks like this:

impl<T> WaitFreeQueue<T> {
    pub fn enqueue(&self, value: T) {
        let position =
            self.enqueue_pos.fetch_add(1, Ordering::Relaxed);

        let index = position & self.mask;
        let slot = &self.buffer[index];

        while slot.sequence.load(Ordering::Acquire) != position {
            std::hint::spin_loop();
        }

        unsafe {
            (*slot.value.get()).write(value);
        }

        slot.sequence.store(
            position + 1,
            Ordering::Release,
        );
    }

    pub fn dequeue(&self) -> T {
        let position =
            self.dequeue_pos.fetch_add(1, Ordering::Relaxed);

        let index = position & self.mask;
        let slot = &self.buffer[index];

        while slot.sequence.load(Ordering::Acquire)
            != position + 1
        {
            std::hint::spin_loop();
        }

        let value = unsafe {
            (*slot.value.get()).assume_init_read()
        };

        slot.sequence.store(
            position + self.mask + 1,
            Ordering::Release,
        );

        value
    }
}

This is an important point.

This implementation contains spinning.

Therefore, under a strict formal definition, it should not automatically be called wait-free.

It is much closer to a bounded ring-buffer algorithm with lock-free-style atomic coordination.

And that distinction is not academic.

It is the difference between:

“The queue doesn't use a mutex.”

and:

“Every operation has a mathematically bounded completion time.”

The latter is much harder.

So How Do We Make It Actually Wait-Free?

Now we reach the interesting part.

To get strict wait-freedom, we need to remove unbounded retrying.

There are several strategies.

One is helping.

Suppose Thread A starts an operation and gets descheduled.

Thread B encounters Thread A's unfinished operation.

Instead of waiting for A, B completes A's operation.

This changes the model from:

A must finish
    |
    v
B can continue

to:

A starts
 |
 X
 |
B notices incomplete work
 |
v
B helps A
 |
v
A's operation completes

Now a stalled thread cannot indefinitely block everyone else.

Operation Descriptors

Helping often requires an operation descriptor.

Instead of immediately performing an operation, a thread publishes its intent:

struct Operation<T> {
    state: AtomicUsize,
    value: MaybeUninit<T>,
}

The operation might have states:

PENDING
CLAIMED
COMPLETED

Another thread can inspect it.

If it sees:

PENDING

it can help.

This transforms concurrency from:

threads competing

into:

threads cooperating

That is one of the deepest ideas in non-blocking algorithms.

The Universal Pattern

Many wait-free algorithms follow a pattern like:

1. Publish intention.
2. Attempt progress.
3. If another operation is incomplete, help it.
4. Complete your own operation.

The helping mechanism creates bounded progress.

If every operation can help another operation finish, then a stalled thread is no longer a permanent obstacle.

But There Is a Cost

Wait-free does not mean free.

You are exchanging one resource for another.

Locks give you:

simple reasoning
+
potential blocking

Lock-free algorithms give:

more complexity
+
system-wide progress

Wait-free algorithms give:

even more complexity
+
per-operation progress guarantees

You are paying for the guarantee.

And sometimes the cost is not worth it.

Why Wait-Free Queues Are Difficult

The difficult part isn't:

AtomicUsize

The difficult part is the interaction between:

ownership
+
memory reclamation
+
atomic ordering
+
ABA prevention
+
progress guarantees
+
cache coherence
+
compiler reordering

Each is a separate problem.

Together they become a small operating system hiding inside a data structure.

The ABA Problem

Consider an atomic pointer:

A -> B

Thread 1 reads:

A

Thread 2 changes:

A -> C

then:

C -> A

Thread 1 wakes up.

It sees:

A

and thinks:

“Nothing changed.”

But something absolutely changed.

The state went:

A -> C -> A

This is the ABA problem.

Sequence numbers are one technique for detecting generations of reuse.

Instead of:

pointer = A

we can conceptually use:

(A, generation=42)

Then:

(A, generation=43)

is visibly different.

That is another reason sequence counters are so powerful.

False Sharing

Correctness is not the only concern.

Performance matters.

Suppose:

struct Queue {
    enqueue_pos: AtomicUsize,
    dequeue_pos: AtomicUsize,
}

These fields may occupy the same CPU cache line.

Now:

CPU 1 -> writes enqueue_pos
CPU 2 -> writes dequeue_pos

Even though they are logically unrelated, the CPUs may continuously invalidate each other's cache lines.

This is called false sharing.

The code is correct.

The algorithm is correct.

And the performance can still collapse.

A production implementation may use cache-line padding:

#[repr(align(64))]
struct Padded<T> {
    value: T,
}

Although the correct alignment depends on the target architecture and workload.

Memory Ordering Is a Performance Dial

Rust gives us:

Ordering::Relaxed
Ordering::Acquire
Ordering::Release
Ordering::AcqRel
Ordering::SeqCst

A beginner often reaches for:

Ordering::SeqCst

everywhere.

It is understandable.

It provides the strongest ordering model.

But stronger ordering can introduce unnecessary synchronization constraints.

A better approach is:

Use the weakest ordering that preserves the algorithm's proof.

For example:

fetch_add(Ordering::Relaxed)

can be appropriate for allocating unique positions when the operation's synchronization happens elsewhere.

Meanwhile:

sequence.load(Ordering::Acquire)

and:

sequence.store(Ordering::Release)

can establish the producer/consumer publication relationship.

The important question isn't:

“Which ordering is safest?”

The important question is:

“What ordering does the proof require?”

The Queue Is Really a State Machine

One way to understand the algorithm is to stop thinking about it as a queue.

Think of every slot as a tiny state machine.

For example:

          producer
              |
              v
        +-------------+
        |   EMPTY     |
        +-------------+
              |
              | write
              v
        +-------------+
        |    FULL     |
        +-------------+
              |
              | read
              v
        +-------------+
        |   EMPTY     |
        +-------------+

But because the ring buffer reuses physical slots, we need generations.

So the real state is closer to:

EMPTY generation 0
        |
        v
FULL generation 0
        |
        v
EMPTY generation 1
        |
        v
FULL generation 1

The sequence number encodes this state.

Why Bounded Queues Are Attractive

A dynamically growing concurrent queue has another problem.

Memory allocation.

Suppose an enqueue requires:

allocate node
initialize node
link node
publish node

Now allocation itself becomes part of the concurrency story.

A bounded ring buffer avoids this.

Memory is allocated once:

startup
   |
   v
+-----------------------+
| fixed-size allocation |
+-----------------------+

Then operations reuse the same storage.

This makes bounded queues attractive for:

• network systems,
• telemetry pipelines,
• embedded systems,
• real-time systems,
• game engines,
• audio processing,
• kernel-style components,
• high-performance logging.

Testing the Queue

Concurrent code cannot be tested like ordinary code.

This:

#[test]
fn test_queue() {
    let queue = WaitFreeQueue::with_capacity(1024);

    queue.enqueue(10);
    assert_eq!(queue.dequeue(), 10);
}

proves almost nothing about concurrency.

We need multiple producers and consumers.

For example:

use std::sync::Arc;
use std::thread;

let queue = Arc::new(
    WaitFreeQueue::with_capacity(1024)
);

let mut handles = Vec::new();

for producer_id in 0..4 {
    let queue = Arc::clone(&queue);

    handles.push(thread::spawn(move || {
        for i in 0..10_000 {
            queue.enqueue(
                producer_id * 10_000 + i
            );
        }
    }));
}

Then consumers drain the queue.

We can verify:

number produced == number consumed

and:

no values duplicated

and:

no values lost

Stress Testing

Concurrency bugs are often probabilistic.

The code may pass:

10 runs

and fail:

run 11,482

You want tests that create different scheduling conditions.

For example:

Producer A
    |
    | sleep
    v
Producer B
    |
    v
Consumer A
    |
    v
Producer A resumes

The scheduler becomes part of the adversary.

A good concurrent test attempts to make timing unpredictable.

Loom and Model Checking

For serious Rust concurrency work, tools such as loom are extremely useful.

Instead of merely executing one scheduling order:

A -> B -> C

a model checker can explore many possible interleavings:

A -> B -> C
A -> C -> B
B -> A -> C
B -> C -> A
C -> A -> B
C -> B -> A

The number of schedules grows quickly.

That's precisely why concurrent algorithms are difficult to reason about manually.

The Bigger Lesson

Building this queue teaches something more important than queues.

It teaches that concurrency is fundamentally about ownership transitions.

At every moment, someone needs to answer:

Who owns this memory?

For an empty slot:

producer owns it

For a published slot:

consumer owns it

For a consumed slot:

producer owns it again

The queue is essentially a machine for transferring ownership between threads.

Rust's ownership system operates at the language level.

Our queue's sequence numbers implement a second ownership system at runtime.

That's the beautiful part.

Rust Is Not Making the Algorithm Easy

Rust prevents many ordinary memory bugs.

It does not prove that your lock-free algorithm is correct.

This code:

unsafe {
    (*slot.value.get()).write(value);
}

is not automatically safe because it compiles.

We need an invariant.

Something like:

A producer may write to a slot only after observing the sequence corresponding to its exclusive logical position.

And:

A consumer may read a slot only after observing the producer's release publication.

And:

A slot cannot be simultaneously owned by a producer and consumer.

Those statements form the beginning of the correctness proof.

A Useful Mental Model

When designing concurrent data structures, think in terms of:

STATE
  |
  v
WHO OWNS IT?
  |
  v
WHAT ATOMIC EVENT TRANSFERS OWNERSHIP?
  |
  v
WHAT MEMORY ORDERING MAKES THE DATA VISIBLE?
  |
  v
CAN ANOTHER THREAD GET STUCK?
  |
  v
IS THE NUMBER OF STEPS BOUNDED?

That final question separates wait-free algorithms from many merely lock-free designs.

Wait-Free vs Lock-Free

Let's make the distinction painfully clear.

Mutex queue

Thread A
   |
 locks
   |
   X
   |
 Thread B waits

Progress depends on lock ownership.

Lock-free queue

Thread A
   |
   X
   |
Thread B -----> succeeds

The system makes progress.

Wait-free queue

Thread A
   |
   X

Thread B -----> succeeds

Thread C ----------> succeeds

Thread D ----------------> succeeds

Every operation has a bounded progress guarantee.

The difference is not cosmetic.

It is mathematical.

When Should You Use Wait-Free Structures?

Almost never by default.

If you are writing an ordinary web application:

HTTP request
     |
     v
database
     |
     v
response

you probably do not need a wait-free queue.

A mutex-backed queue may be simpler and perfectly adequate.

Wait-free algorithms become interesting when latency and contention matter enough to justify the complexity.

Examples include:

real-time systems
high-frequency messaging
network runtimes
telemetry
game engines
audio systems
embedded systems
low-latency trading infrastructure
operating-system components

The key is not:

“Wait-free is faster.”

It isn't necessarily.

The key is:

“Wait-free gives a stronger bound on progress.”

That's a different property.

The Hidden Cost of Wait-Free

Imagine two systems.

System A:

average latency: 2 μs
worst case: 500 μs

System B:

average latency: 3 μs
worst case: 5 μs

If you care about real-time behavior, System B may be vastly more valuable.

This is why worst-case guarantees matter.

Average performance tells you what normally happens.

Wait-free reasoning asks:

What can happen in the worst case?

That is a much more demanding question.

What We Built

Our conceptual queue contains:

             WaitFreeQueue
                  |
       +----------+----------+
       |                     |
 enqueue_pos            dequeue_pos
       |                     |
       v                     v
   producers             consumers
       |                     |
       +----------+----------+
                  |
                  v
            ring buffer
                  |
          +-------+-------+
          |       |       |
          v       v       v
        Slot    Slot    Slot
          |       |       |
          +-------+-------+
                  |
                  v
           sequence numbers

Each slot contains:

sequence
value

The sequence identifies the logical generation of the slot.

The atomic positions allocate logical queue positions.

Release/acquire ordering transfers visibility.

And bounded capacity avoids allocation during ordinary operations.

The Most Important Caveat

If you take one thing from this article, make it this:

An atomic queue is not automatically a wait-free queue.

A queue can be:

mutex-based
lock-free
wait-free

and all three can be implemented correctly.

The distinction is the progress guarantee.

A loop such as:

while !try_operation() {
    spin_loop();
}

should immediately make you ask:

Is the number of iterations bounded?

If the answer is no, you should be extremely cautious about calling the algorithm wait-free.

This is one of the easiest mistakes to make when discussing concurrent data structures.

Where to Go Next

Once you understand this queue, there are several deeper directions.

You can explore:

Michael-Scott queues

for dynamically allocated lock-free queues.

Then:

hazard pointers

for safe memory reclamation.

Then:

epoch-based reclamation

for another approach to managing retired nodes.

Then:

helping

for constructing genuinely wait-free algorithms.

And eventually:

linearizability

which gives you a formal way to reason about whether concurrent operations appear to occur atomically.

That's where concurrent programming starts looking less like ordinary application development and more like mathematics.

Final Thought

The first time you build a concurrent queue, you think the difficult part is storing the data.

It isn't.

The difficult part is convincing multiple CPUs that they agree about reality.

One CPU says:

"This slot is mine."

Another says:

"I am reading it."

A third may be delayed for milliseconds.

The cache coherence protocol is doing things underneath you.

The compiler is allowed to reorder operations unless synchronization prevents it.

The operating system may pause a thread at exactly the wrong moment.

And yet your data structure must remain correct.

That's what makes wait-free programming fascinating.

You aren't merely writing code.

You're defining a protocol between independent machines that happen to share memory.

Rust gives you powerful tools for expressing that protocol:

AtomicUsize
UnsafeCell
MaybeUninit
Acquire
Release

But the real skill is learning what those tools mean together.

A wait-free queue is therefore more than a queue.

It is a lesson in distributed systems disguised as shared memory.

There are multiple participants.

They cannot assume another participant will respond.

They communicate through carefully defined state transitions.

They need explicit ownership.

They need ordering guarantees.

And the strongest algorithms make progress even when one participant disappears.

That sounds a lot like distributed computing.

Except the network is your CPU's memory subsystem.

And the latency is measured in nanoseconds.

That is the strange beauty of concurrent programming.

The moment you stop asking “does this code work?” and start asking “what is the worst thing another thread can do to me?” — you are beginning to think like a systems programmer.