{"title":"Wait-Free Algorithms","description":"","content":"# Wait-Free Algorithms\n\nYour lock-free queue handles millions of messages per day. It is fast, it is efficient, and it never deadlocks. Then one day, during a load spike, one thread gets unlucky. Every time it attempts a CAS, another thread beats it. It spins and retries, spins and retries, for what feels like an eternity. Other threads complete their operations just fine. The system makes progress. But this one thread, serving a customer request, is effectively starving. In a lock-free world, this is acceptable. In a wait-free world, it is not.\n\nWait-free algorithms provide the strongest progress guarantee in concurrent programming: every operation completes in a bounded number of steps, regardless of the behavior of other threads. No thread can starve, no matter how much contention exists. This chapter explores what wait-free means, how helping mechanisms enable it, and when the added complexity is worth the cost.\n\n---\n\n## What are Wait-Free Algorithms?\n\nThink of a government office with numbered tickets. Each person takes a number, and the system guarantees everyone will be served in finite time. Even if some transactions take longer, you know your turn is coming. Wait-free algorithms work similarly: they guarantee every operation completes in a bounded number of steps.\n\nThe key distinction from lock-free is the bound. Lock-free guarantees system-wide progress (at least one thread completes), but an individual thread could theoretically spin forever if it keeps losing CAS races. Wait-free guarantees per-thread progress: every thread completes within a known number of steps.\n\n\n```mermaid\nflowchart TD\n subgraph \"Lock-Free\"\n LF1[Thread A: retry]:::yellow\n LF2[Thread B: retry]:::yellow\n LF3[Thread C: succeeds]:::green\n NOTE1[\"At least one succeeds,
others may retry indefinitely\"]:::secondary\n end\n\n subgraph \"Wait-Free\"\n WF1[Thread A: completes
in ≤N steps]:::green\n WF2[Thread B: completes
in ≤N steps]:::green\n WF3[Thread C: completes
in ≤N steps]:::green\n NOTE2[\"ALL complete in
bounded steps\"]:::secondary\n end\n\n classDef yellow fill:#ffd43b,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n```\n\n\nThe diagram shows the fundamental difference. In lock-free, Thread A and B might retry many times while C succeeds. In wait-free, all three threads complete within N steps (where N is a known bound). This bounded completion guarantee is what makes wait-free special.\n\nFormal definition: An algorithm is **wait-free** if every operation by every thread completes in a bounded number of its own steps, regardless of the relative speeds, failures, or delays of other threads.\n\n---\n\n## Progress Guarantees Hierarchy\n\nConcurrent algorithms fall into a hierarchy of progress guarantees:\n\n\n```mermaid\ngraph TD\n BLOCK[Blocking
Locks, Mutexes]:::red --> OBST[Obstruction-Free]:::orange\n OBST --> LOCK[Lock-Free]:::yellow\n LOCK --> WAIT[Wait-Free]:::green\n\n classDef red fill:#ff8787,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef yellow fill:#ffd43b,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nEach level provides stronger guarantees than the one below:\n\n\n| Guarantee | Definition | Example | Starvation? |\n|-----------|------------|---------|-------------|\n| Blocking | Thread can wait indefinitely for another | Mutex, Semaphore | Yes |\n| Obstruction-Free | Thread completes if run in isolation | Some STM implementations | Yes (with contention) |\n| Lock-Free | At least one thread always progresses | CAS loops, Treiber stack | Possible (rare) |\n| Wait-Free | Every thread completes in bounded steps | Wait-free counter, helping queues | No |\n\n\n### Blocking\n\nWith blocking algorithms, a thread can be delayed indefinitely waiting for another thread. If the lock holder crashes, sleeps, or is preempted, waiters are stuck. Deadlock is possible if lock ordering is violated.\n\n### Obstruction-Free\n\nObstruction-free algorithms guarantee progress if a thread runs in isolation (no other threads interfering). Under contention, threads might livelock, repeatedly interfering with each other without anyone making progress. This is a weak guarantee, but easier to implement than lock-free.\n\n### Lock-Free\n\nLock-free algorithms guarantee system-wide progress. At least one thread completes in a finite number of steps. Other threads might retry indefinitely, but the system as a whole keeps moving. Deadlock is impossible, but individual thread starvation is theoretically possible.\n\n### Wait-Free\n\nWait-free is the gold standard. Every thread completes in bounded steps. No starvation, no indefinite delays. The bound is typically O(N) where N is the number of threads, though some algorithms achieve O(1).\n\n:::info Interview Insight A classic interview question is: \"What's the difference between lock-free and wait-free?\" The key is the per-thread vs system-wide progress guarantee. Lock-free says someone always wins. Wait-free says everyone wins in bounded time. Be ready to explain why wait-free is harder to achieve and give examples of each. :::\n\n---\n\n## Why Wait-Free Matters\n\n### Real-Time Systems\n\nIn hard real-time systems, missing a deadline is a failure. Lock-free algorithms cannot guarantee deadlines because a thread might retry indefinitely. Wait-free algorithms provide the bounded completion time needed for real-time guarantees.\n\nExamples:\n\n- Avionics systems\n- Medical devices\n- Industrial control systems\n- High-frequency trading (where every microsecond matters)\n\n### Fairness\n\nWait-free algorithms are inherently fair. No thread can monopolize resources while others starve. This matters in multi-tenant systems where one customer's workload should not indefinitely delay another's.\n\n### Worst-Case Analysis\n\nLock-free performance is hard to analyze. The worst case (a thread retrying forever) is unbounded. Wait-free algorithms have analyzable worst-case behavior, making them suitable for systems that need performance guarantees.\n\n### The Trade-off\n\nWait-free comes at a cost:\n\n\n| Aspect | Lock-Free | Wait-Free |\n|--------|-----------|-----------|\n| Average performance | Often faster | Often slower |\n| Worst-case performance | Unbounded | Bounded |\n| Implementation complexity | Moderate | High |\n| Memory overhead | Low | Higher |\n| Real-world adoption | Common | Rare |\n\n\nMost systems choose lock-free because starvation is rare in practice, and the performance overhead of wait-free is not worth it. Wait-free is reserved for systems with hard real-time requirements or formal correctness proofs.\n\n---\n\n## The Helping Mechanism\n\nThe key technique that enables wait-free algorithms is **helping**: fast threads help slow threads complete their operations.\n\n### The Core Idea\n\nIn lock-free algorithms, threads compete. If Thread A loses a CAS, it retries while Thread B succeeds. In wait-free algorithms, threads cooperate. Before doing its own work, a thread checks if any other thread needs help completing an operation.\n\n\n```mermaid\nflowchart TD\n START[Thread starts operation]:::primary --> ANNOUNCE[Announce operation
in shared state]:::orange\n ANNOUNCE --> CHECK{Other threads
need help?}\n CHECK -->|Yes| HELP[Help complete
pending operations]:::purple\n CHECK -->|No| OWN[Perform own
operation]:::secondary\n HELP --> OWN\n OWN --> DONE[Complete
and return]:::green\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe diagram shows the helping pattern. A thread first announces its intention. Then it scans for other threads that need help. It helps them complete before (or while) doing its own work. This ensures that even if a thread is slow, other threads will complete its operation.\n\n### How Helping Works\n\n1. **Announce:** Before starting an operation, thread writes its intent to a shared announcement array\n2. **Scan:** Thread scans the announcement array for pending operations\n3. **Help:** Thread attempts to complete pending operations (which might already be done)\n4. **Execute:** Thread performs its own operation\n5. **Complete:** Thread marks its announcement as done\n\n\n```mermaid\nsequenceDiagram\n participant T1 as Thread 1 (slow)\n participant Announce as Announcement Array\n participant T2 as Thread 2 (fast)\n participant DS as Data Structure\n\n T1->>Announce: Announce \"increment slot 0\"\n Note over T1: Gets preempted...\n\n T2->>Announce: Announce \"increment slot 1\"\n T2->>Announce: Scan for pending ops\n Note over T2: Sees T1 pending\n\n T2->>DS: Help: increment slot 0 for T1\n T2->>Announce: Mark T1 as helped\n T2->>DS: Perform own: increment slot 1\n T2->>Announce: Mark T2 as done\n\n Note over T1: Resumes\n\n T1->>Announce: Check if done\n Note over T1: Already completed by T2!\n T1->>Announce: Clean up and return\n```\n\n\nThe sequence diagram shows helping in action. Thread 1 announces its operation but gets preempted. Thread 2 arrives, sees T1's pending operation, helps complete it, then does its own work. When T1 resumes, it finds its operation already completed and just returns.\n\n### Why Helping Guarantees Progress\n\nConsider N threads. Thread 1 announces an operation. Before any thread can complete its own operation, it must help all pending operations. In the worst case, N-1 threads each help Thread 1 before doing their own work. But within N operations (one per thread), Thread 1's operation is guaranteed to complete.\n\nThis gives us the bound: each operation completes in O(N) steps, where N is the number of threads.\n\n---\n\n## Wait-Free Counter\n\nThe simplest wait-free data structure is a counter where each thread has a dedicated slot.\n\n### Array-Based Approach\n\nInstead of one shared counter (which requires CAS loops), each thread gets its own counter slot:\n\n\n```mermaid\nflowchart LR\n subgraph \"Wait-Free Counter\"\n SLOT0[Slot 0
Thread 0]:::primary\n SLOT1[Slot 1
Thread 1]:::primary\n SLOT2[Slot 2
Thread 2]:::primary\n SLOT3[Slot 3
Thread 3]:::primary\n end\n\n INCREMENT[Increment:
Just update your slot]:::green\n READ[Read:
Sum all slots]:::orange\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n```\n\n\n- **Increment:** O(1) wait-free. Just update your own slot. No contention possible.\n- **Read:** O(N) where N is the number of threads. Sum all slots.\n\nThis is wait-free because no thread ever needs to retry an operation. Each thread has exclusive access to its own slot.\n\n### Implementation\n\nimport Tabs from '@theme/Tabs'; import TabItem from '@theme/TabItem';\n\n \n\n\n```java\nimport java.util.concurrent.atomic.AtomicLongArray;\n\npublic class WaitFreeCounter {\n private final AtomicLongArray slots;\n private final int numThreads;\n\n // Thread-local slot index\n private final ThreadLocal threadIndex = new ThreadLocal() {\n private int nextIndex = 0;\n\n @Override\n protected synchronized Integer initialValue() {\n return nextIndex++;\n }\n };\n\n public WaitFreeCounter(int numThreads) {\n this.numThreads = numThreads;\n this.slots = new AtomicLongArray(numThreads);\n }\n\n /**\n * Wait-free increment: O(1), no contention possible.\n */\n public void increment() {\n int index = threadIndex.get();\n // Atomic update to own slot - no CAS loop needed\n slots.getAndIncrement(index);\n }\n\n /**\n * Wait-free decrement: O(1), no contention possible.\n */\n public void decrement() {\n int index = threadIndex.get();\n slots.getAndDecrement(index);\n }\n\n /**\n * Wait-free read: O(N) where N is number of threads.\n * Reads a consistent snapshot by summing all slots.\n */\n public long get() {\n long sum = 0;\n for (int i = 0; i < numThreads; i++) {\n sum += slots.get(i);\n }\n return sum;\n }\n\n /**\n * Add arbitrary value to counter.\n */\n public void add(long delta) {\n int index = threadIndex.get();\n slots.getAndAdd(index, delta);\n }\n}\n```\n\n\nThe implementation is beautifully simple. Each thread has its own slot, so increment is just an atomic update with no possibility of contention. Reading requires summing all slots, which takes O(N) time but is still wait-free since each slot read is atomic and independent.\n\n \n\n\n```python\nimport threading\nfrom typing import List\n\nclass WaitFreeCounter:\n \"\"\"\n Wait-free counter using per-thread slots.\n Each thread has exclusive access to its slot.\n \"\"\"\n def __init__(self, num_threads: int):\n self.num_threads = num_threads\n self.slots: List[int] = [0] * num_threads\n self.locks = [threading.Lock() for _ in range(num_threads)]\n self._thread_indices: dict = {}\n self._index_lock = threading.Lock()\n self._next_index = 0\n\n def _get_thread_index(self) -> int:\n \"\"\"Get or assign thread index.\"\"\"\n thread_id = threading.current_thread().ident\n if thread_id not in self._thread_indices:\n with self._index_lock:\n if thread_id not in self._thread_indices:\n self._thread_indices[thread_id] = self._next_index\n self._next_index += 1\n return self._thread_indices[thread_id]\n\n def increment(self) -> None:\n \"\"\"Wait-free increment: O(1), no contention.\"\"\"\n index = self._get_thread_index()\n # No lock needed for own slot access (single writer)\n self.slots[index] += 1\n\n def decrement(self) -> None:\n \"\"\"Wait-free decrement: O(1), no contention.\"\"\"\n index = self._get_thread_index()\n self.slots[index] -= 1\n\n def get(self) -> int:\n \"\"\"Wait-free read: O(N), sums all slots.\"\"\"\n return sum(self.slots)\n\n def add(self, delta: int) -> None:\n \"\"\"Add arbitrary value.\"\"\"\n index = self._get_thread_index()\n self.slots[index] += delta\n```\n\n\n \n\n\n```cpp\n#include \n#include \n#include \n\nclass WaitFreeCounter {\n std::vector> slots;\n int numThreads;\n\n // Simple thread-local index (in practice, use thread_local)\n static thread_local int threadIndex;\n static std::atomic nextIndex;\n\npublic:\n explicit WaitFreeCounter(int numThreads)\n : numThreads(numThreads), slots(numThreads) {\n for (int i = 0; i < numThreads; i++) {\n slots[i].store(0, std::memory_order_relaxed);\n }\n }\n\n int getThreadIndex() {\n if (threadIndex == -1) {\n threadIndex = nextIndex.fetch_add(1, std::memory_order_relaxed);\n }\n return threadIndex;\n }\n\n /**\n * Wait-free increment: O(1), no contention possible.\n */\n void increment() {\n int index = getThreadIndex();\n slots[index].fetch_add(1, std::memory_order_relaxed);\n }\n\n /**\n * Wait-free decrement: O(1), no contention possible.\n */\n void decrement() {\n int index = getThreadIndex();\n slots[index].fetch_sub(1, std::memory_order_relaxed);\n }\n\n /**\n * Wait-free read: O(N) where N is number of threads.\n */\n long get() const {\n long sum = 0;\n for (int i = 0; i < numThreads; i++) {\n sum += slots[i].load(std::memory_order_relaxed);\n }\n return sum;\n }\n\n void add(long delta) {\n int index = getThreadIndex();\n slots[index].fetch_add(delta, std::memory_order_relaxed);\n }\n};\n\n// Static member definitions\nthread_local int WaitFreeCounter::threadIndex = -1;\nstd::atomic WaitFreeCounter::nextIndex{0};\n```\n\n\nThe C++ version uses relaxed memory ordering since the counter slots are independent. Each thread only writes to its own slot, and reads sum all slots atomically.\n\n \n\n\n```csharp\nusing System;\nusing System.Threading;\n\npublic class WaitFreeCounter\n{\n private readonly long[] _slots;\n private readonly int _numThreads;\n\n // Thread-local slot index\n private static int _nextIndex = 0;\n [ThreadStatic] private static int _threadIndex;\n [ThreadStatic] private static bool _indexInitialized;\n\n public WaitFreeCounter(int numThreads)\n {\n _numThreads = numThreads;\n _slots = new long[numThreads];\n }\n\n private int GetThreadIndex()\n {\n if (!_indexInitialized)\n {\n _threadIndex = Interlocked.Increment(ref _nextIndex) - 1;\n _indexInitialized = true;\n }\n return _threadIndex;\n }\n\n ///

\n /// Wait-free increment: O(1), no contention possible.\n ///

\n public void Increment()\n {\n int index = GetThreadIndex();\n // Atomic update to own slot - no CAS loop needed\n Interlocked.Increment(ref _slots[index]);\n }\n\n ///

\n /// Wait-free decrement: O(1), no contention possible.\n ///

\n public void Decrement()\n {\n int index = GetThreadIndex();\n Interlocked.Decrement(ref _slots[index]);\n }\n\n ///

\n /// Wait-free read: O(N) where N is number of threads.\n /// Reads a consistent snapshot by summing all slots.\n ///

\n public long Get()\n {\n long sum = 0;\n for (int i = 0; i < _numThreads; i++)\n {\n sum += Interlocked.Read(ref _slots[i]);\n }\n return sum;\n }\n\n ///

\n /// Add arbitrary value to counter.\n ///

\n public void Add(long delta)\n {\n int index = GetThreadIndex();\n Interlocked.Add(ref _slots[index], delta);\n }\n}\n```\n\n\n**Key Points:**\n\n- Line 11: `[ThreadStatic]` provides thread-local storage for the slot index\n- Line 24: Thread index assignment is atomic and happens once per thread\n- Line 37: `Interlocked.Increment` on own slot has no contention\n- Line 57: `Interlocked.Read` ensures atomic 64-bit read on 32-bit systems\n\n \n\nGo provides excellent primitives for wait-free counters through its `sync/atomic` package. The key insight is that Go's atomic operations on properly aligned values are guaranteed to complete in bounded steps, making them ideal for wait-free designs.\n\n\n```go\npackage main\n\nimport (\n\t\"sync\"\n\t\"sync/atomic\"\n)\n\n// WaitFreeCounter uses per-goroutine slots for wait-free increment\ntype WaitFreeCounter struct {\n\tslots []int64\n\tnumSlots int\n\tslotIndex int64\n\tindexLock sync.Mutex\n\tindices sync.Map // maps goroutine ID to slot index\n}\n\n// NewWaitFreeCounter creates a counter with the given number of slots\nfunc NewWaitFreeCounter(numSlots int) *WaitFreeCounter {\n\treturn &WaitFreeCounter{\n\t\tslots: make([]int64, numSlots),\n\t\tnumSlots: numSlots,\n\t}\n}\n\n// getSlotIndex returns or assigns a slot index for the current goroutine\nfunc (c *WaitFreeCounter) getSlotIndex() int {\n\t// Use goroutine-local approach via a simple atomic counter\n\t// In production, consider using runtime.GoID() with go linkname\n\tc.indexLock.Lock()\n\tdefer c.indexLock.Unlock()\n\tidx := int(atomic.AddInt64(&c.slotIndex, 1) - 1)\n\treturn idx % c.numSlots\n}\n\n// Increment performs a wait-free increment: O(1), no contention possible\nfunc (c *WaitFreeCounter) Increment(slotIdx int) {\n\tatomic.AddInt64(&c.slots[slotIdx], 1)\n}\n\n// Decrement performs a wait-free decrement: O(1), no contention possible\nfunc (c *WaitFreeCounter) Decrement(slotIdx int) {\n\tatomic.AddInt64(&c.slots[slotIdx], -1)\n}\n\n// Get returns the sum of all slots: O(N) where N is number of slots\n// This is still wait-free as each atomic load completes in bounded steps\nfunc (c *WaitFreeCounter) Get() int64 {\n\tvar sum int64\n\tfor i := 0; i < c.numSlots; i++ {\n\t\tsum += atomic.LoadInt64(&c.slots[i])\n\t}\n\treturn sum\n}\n\n// Add adds an arbitrary value to the counter\nfunc (c *WaitFreeCounter) Add(slotIdx int, delta int64) {\n\tatomic.AddInt64(&c.slots[slotIdx], delta)\n}\n```\n\n\n**Key Points:**\n\n- Go's `atomic.AddInt64` and `atomic.LoadInt64` are bounded operations, they complete without CAS retry loops\n- Each goroutine writes only to its assigned slot, eliminating contention\n- The read operation sums all slots atomically, which is O(N) but still wait-free\n- Go's memory model guarantees that atomic operations provide sequential consistency\n\n \n\n### Complete Example\n\n \n\n\n```java\nimport java.util.ArrayList;\nimport java.util.List;\n\npublic class WaitFreeCounterDemo {\n public static void main(String[] args) throws InterruptedException {\n final int NUM_THREADS = 8;\n final int INCREMENTS_PER_THREAD = 100_000;\n\n WaitFreeCounter counter = new WaitFreeCounter(NUM_THREADS);\n List threads = new ArrayList<>();\n\n long startTime = System.nanoTime();\n\n for (int i = 0; i < NUM_THREADS; i++) {\n Thread t = new Thread(() -> {\n for (int j = 0; j < INCREMENTS_PER_THREAD; j++) {\n counter.increment();\n }\n });\n threads.add(t);\n t.start();\n }\n\n for (Thread t : threads) {\n t.join();\n }\n\n long endTime = System.nanoTime();\n long duration = (endTime - startTime) / 1_000_000;\n\n System.out.println(\"Final count: \" + counter.get());\n System.out.println(\"Expected: \" + (NUM_THREADS * INCREMENTS_PER_THREAD));\n System.out.println(\"Time: \" + duration + \" ms\");\n }\n}\n```\n\n\n**Output:**\n\n\n```shell\nFinal count: 800000\nExpected: 800000\nTime: 45 ms\n```\n\n\n \n\n\n```csharp\nusing System;\nusing System.Collections.Generic;\nusing System.Diagnostics;\nusing System.Threading;\n\npublic class WaitFreeCounterDemo\n{\n public static void Main(string[] args)\n {\n const int NUM_THREADS = 8;\n const int INCREMENTS_PER_THREAD = 100_000;\n\n var counter = new WaitFreeCounter(NUM_THREADS);\n var threads = new List();\n\n var stopwatch = Stopwatch.StartNew();\n\n for (int i = 0; i < NUM_THREADS; i++)\n {\n var t = new Thread(() =>\n {\n for (int j = 0; j < INCREMENTS_PER_THREAD; j++)\n {\n counter.Increment();\n }\n });\n threads.Add(t);\n t.Start();\n }\n\n foreach (var t in threads)\n {\n t.Join();\n }\n\n stopwatch.Stop();\n\n Console.WriteLine($\"Final count: {counter.Get()}\");\n Console.WriteLine($\"Expected: {NUM_THREADS * INCREMENTS_PER_THREAD}\");\n Console.WriteLine($\"Time: {stopwatch.ElapsedMilliseconds} ms\");\n }\n}\n```\n\n\n**Output:**\n\n\n```shell\nFinal count: 800000\nExpected: 800000\nTime: 38 ms\n```\n\n\n**Key Points:**\n\n- Each thread gets its own slot via `[ThreadStatic]` attribute\n- No CAS failures or retries because each slot has a single writer\n- Read operation sums all slots atomically\n\n \n\n\n```go\npackage main\n\nimport (\n\t\"fmt\"\n\t\"sync\"\n\t\"sync/atomic\"\n\t\"time\"\n)\n\nfunc main() {\n\tconst numGoroutines = 8\n\tconst incrementsPerGoroutine = 100_000\n\n\tcounter := NewWaitFreeCounter(numGoroutines)\n\tvar wg sync.WaitGroup\n\n\tstartTime := time.Now()\n\n\tfor i := 0; i < numGoroutines; i++ {\n\t\tslotIdx := i // Each goroutine gets its own slot\n\t\twg.Add(1)\n\t\tgo func() {\n\t\t\tdefer wg.Done()\n\t\t\tfor j := 0; j < incrementsPerGoroutine; j++ {\n\t\t\t\tcounter.Increment(slotIdx)\n\t\t\t}\n\t\t}()\n\t}\n\n\twg.Wait()\n\tduration := time.Since(startTime)\n\n\tfmt.Printf(\"Final count: %d\\n\", counter.Get())\n\tfmt.Printf(\"Expected: %d\\n\", numGoroutines*incrementsPerGoroutine)\n\tfmt.Printf(\"Time: %v\\n\", duration)\n}\n\n// WaitFreeCounter implementation\ntype WaitFreeCounter struct {\n\tslots []int64\n}\n\nfunc NewWaitFreeCounter(numSlots int) *WaitFreeCounter {\n\treturn &WaitFreeCounter{slots: make([]int64, numSlots)}\n}\n\nfunc (c *WaitFreeCounter) Increment(slotIdx int) {\n\tatomic.AddInt64(&c.slots[slotIdx], 1)\n}\n\nfunc (c *WaitFreeCounter) Get() int64 {\n\tvar sum int64\n\tfor i := range c.slots {\n\t\tsum += atomic.LoadInt64(&c.slots[i])\n\t}\n\treturn sum\n}\n```\n\n\n**Output:**\n\n\n```shell\nFinal count: 800000\nExpected: 800000\nTime: 12.5ms\n```\n\n\n**Key Points:**\n\n- Each goroutine is assigned a dedicated slot index at creation time\n- `atomic.AddInt64` provides wait-free increment with no contention between goroutines\n- Go's lightweight goroutines make this pattern particularly efficient\n- The atomic package guarantees bounded completion for all operations\n\n \n\n### Trade-offs\n\n\n| Aspect | Lock-Free Counter | Wait-Free Counter |\n|--------|-------------------|-------------------|\n| Increment | O(1) expected, unbounded worst case | O(1) guaranteed |\n| Read | O(1) | O(N) where N = threads |\n| Memory | Single integer | N integers |\n| Contention | CAS failures under contention | None |\n| Complexity | Simple | Simple |\n\n\nThe wait-free counter trades read performance (O(N) instead of O(1)) for guaranteed increment performance. This is the classic wait-free trade-off: you get bounds, but you often pay with memory or read overhead.\n\n---\n\n## Combining Trees\n\nFor better read performance, wait-free counters can use a combining tree:\n\n\n```mermaid\nflowchart TD\n ROOT[Root: Sum]:::primary\n L1[Left Sum]:::secondary\n R1[Right Sum]:::secondary\n LL[Slot 0]:::purple\n LR[Slot 1]:::purple\n RL[Slot 2]:::purple\n RR[Slot 3]:::purple\n\n ROOT --> L1\n ROOT --> R1\n L1 --> LL\n L1 --> LR\n R1 --> RL\n R1 --> RR\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n```\n\n\nIn a combining tree:\n\n- Leaves are per-thread slots (O(1) increment)\n- Internal nodes cache partial sums\n- Read is O(log N) by traversing from root\n\nThe trade-off: increment becomes O(log N) because you must update your slot and propagate the change up the tree. But read improves from O(N) to O(log N).\n\n---\n\n## Population-Aware vs Population-Oblivious\n\nWait-free algorithms come in two flavors:\n\n### Population-Oblivious\n\nThe algorithm works without knowing how many threads exist. Threads can join and leave dynamically. The bound is independent of thread count.\n\nExample: A wait-free timestamp algorithm where each thread gets a unique timestamp in O(1) steps, regardless of how many threads compete.\n\n### Population-Aware\n\nThe algorithm must know the number of threads N upfront. The bound is typically O(N).\n\nExample: The array-based counter above. We must know N to allocate the slots array.\n\n\n| Type | Pros | Cons |\n|------|------|------|\n| Population-Oblivious | Dynamic, flexible | Harder to implement |\n| Population-Aware | Simpler, often faster | Must know N upfront |\n\n\nMost practical wait-free algorithms are population-aware because the algorithms are simpler and the number of threads is often fixed or bounded.\n\n---\n\n## Wait-Free Queue (Conceptual)\n\nA full wait-free queue is complex, but here is the conceptual approach using helping:\n\n\n```mermaid\nflowchart TD\n subgraph \"Announcement Array\"\n ANN0[Thread 0: ENQUEUE x]:::orange\n ANN1[Thread 1: DEQUEUE]:::orange\n ANN2[Thread 2: IDLE]:::secondary\n ANN3[Thread 3: ENQUEUE y]:::orange\n end\n\n subgraph \"Queue State\"\n QUEUE[Actual Queue
with version numbers]:::purple\n end\n\n subgraph \"Thread Operation\"\n SCAN[1. Scan announcements]:::primary\n HELP[2. Help pending ops
in thread order]:::green\n OWN[3. Perform own op]:::primary\n DONE[4. Mark done]:::green\n end\n\n SCAN --> HELP --> OWN --> DONE\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n```\n\n\nKey elements:\n\n1. **Announcement array:** Each thread has a slot to announce its pending operation\n2. **Helping order:** Threads help in a deterministic order (e.g., by thread ID)\n3. **Idempotent operations:** Helping the same operation twice should be safe\n4. **State versions:** Queue state includes version numbers to detect completed operations\n\nThe Kogan-Petrank queue (2011) is a practical wait-free queue implementation that uses these techniques.\n\n---\n\n## When to Use Wait-Free\n\n### Use Wait-Free When:\n\n1. **Hard real-time requirements:** Missing deadlines is unacceptable\n2. **Formal verification needed:** Bounded behavior is easier to prove correct\n3. **Fairness is critical:** No thread should ever starve\n4. **Regulatory requirements:** Some systems require bounded response times\n\n### Use Lock-Free Instead When:\n\n1. **Average performance matters more than worst-case:** Lock-free is often faster\n2. **Starvation is acceptable:** Rare in practice with proper backoff\n3. **Simplicity is important:** Wait-free algorithms are complex\n4. **Memory is constrained:** Wait-free often needs more memory\n\n### Skip Both for Locks When:\n\n1. **Low contention:** Locks are simpler and fast enough\n2. **Complex invariants:** Easier to maintain with exclusive access\n3. **Long critical sections:** Blocking is cheaper than spinning\n\n:::note C# C# provides good building blocks for wait-free algorithms. The `[ThreadStatic]` attribute enables per-thread storage without synchronization overhead, which is essential for wait-free counters. `Interlocked.Read` ensures atomic 64-bit reads on 32-bit systems. For more complex wait-free structures, combine `Interlocked` operations with arrays indexed by thread ID. The `System.Collections.Concurrent` namespace does not include wait-free collections (they are lock-free), but you can build wait-free counters using the array-based approach shown above. For high-contention counters, consider `System.Threading.ThreadLocal` combined with a summation method, which provides similar wait-free increment characteristics. :::\n\n---\n\n## Common Mistakes\n\n### Mistake 1: Confusing Lock-Free with Wait-Free\n\n\n```java\n// This is LOCK-FREE, not wait-free!\npublic void increment() {\n while (true) {\n int current = value.get();\n if (value.compareAndSet(current, current + 1)) {\n return;\n }\n // Could loop forever under contention\n }\n}\n```\n\n\nA CAS loop is lock-free (someone always wins) but not wait-free (an individual might spin forever).\n\n### Mistake 2: Incomplete Helping\n\n\n```java\n// BAD: Only helps one pending operation\npublic void operation() {\n if (announcements[0].isPending()) {\n help(0);\n }\n // Other threads might starve!\n doOwnWork();\n}\n```\n\n\n**Fix:** Help all pending operations, or use a round-robin scheme that guarantees everyone gets helped.\n\n\n```java\n// GOOD: Help all pending operations\npublic void operation() {\n for (int i = 0; i < numThreads; i++) {\n if (announcements[i].isPending()) {\n help(i);\n }\n }\n doOwnWork();\n}\n```\n\n\n### Mistake 3: Non-Idempotent Helping\n\n\n```java\n// BAD: Helping twice corrupts state\npublic void helpEnqueue(int threadId, Object value) {\n queue.add(value); // Might be added twice!\n announcements[threadId].markDone();\n}\n```\n\n\n**Fix:** Use version numbers or check-before-act to make helping idempotent.\n\n\n```java\n// GOOD: Check if already done\npublic void helpEnqueue(int threadId, Object value, long version) {\n if (announcements[threadId].version == version &&\n announcements[threadId].isPending()) {\n if (queue.addWithVersion(value, version)) {\n announcements[threadId].markDone();\n }\n }\n}\n```\n\n\n---\n\n## Performance Considerations\n\n### Overhead of Wait-Free\n\n\n| Aspect | Lock-Free | Wait-Free |\n|--------|-----------|-----------|\n| Typical operation | 10-50 ns | 50-200 ns |\n| Memory per thread | 0-8 bytes | 64+ bytes (announcements) |\n| Cache behavior | Good | Worse (scanning announcements) |\n| Complexity | O(1) expected | O(N) worst case |\n\n\nWait-free algorithms have higher overhead because:\n\n1. Announcement and cleanup costs\n2. Scanning for pending operations\n3. Helping other threads\n4. Version tracking for idempotence\n\n### When Overhead is Acceptable\n\n- N is small (few threads)\n- Worst-case bounds are critical\n- Operations are already expensive (hiding the overhead)\n- Memory bandwidth is not the bottleneck\n\n### Optimization Techniques\n\n1. **Lazy announcement:** Only announce when contention is detected\n2. **Batched helping:** Help multiple operations together\n3. **Local caching:** Cache frequently accessed data\n4. **Combining:** Let one thread represent multiple operations\n\n---\n\n## Interview Questions and Answers\n\n**Q1: What is the difference between lock-free and wait-free?**\n\nLock-free guarantees system-wide progress: at least one thread completes in a finite number of steps. Individual threads might spin indefinitely if they keep losing CAS races.\n\nWait-free guarantees per-thread progress: every thread completes in a bounded number of steps. No thread can starve regardless of contention.\n\nWait-free is strictly stronger. Every wait-free algorithm is lock-free, but not vice versa. The difference matters in real-time systems where you need bounded response times, not just eventual progress.\n\n---\n\n**Q2: Explain how the helping mechanism enables wait-free algorithms.**\n\nHelping is the key technique for wait-free algorithms. Each thread announces its operation in shared memory before starting. Other threads check for pending operations and help complete them.\n\nHere is how it guarantees bounds: suppose there are N threads. Thread T announces an operation. In the worst case, each of the other N-1 threads arrives, helps T, and then does its own work. Within N operations, T's operation is guaranteed to complete.\n\nThe critical requirements are: (1) announcements must be visible to all threads, (2) helping must be idempotent (safe to do twice), and (3) threads must help in a fair order so no one is skipped indefinitely.\n\n---\n\n**Q3: Design a wait-free counter for N threads.**\n\nThe simplest approach uses an array of N slots, one per thread:\n\n\n```java\nclass WaitFreeCounter {\n AtomicLongArray slots;\n\n void increment(int threadId) {\n slots.incrementAndGet(threadId); // O(1) wait-free\n }\n\n long get() {\n long sum = 0;\n for (int i = 0; i < slots.length(); i++) {\n sum += slots.get(i); // O(N) wait-free\n }\n return sum;\n }\n}\n```\n\n\nIncrement is O(1) because each thread has exclusive access to its slot. Read is O(N) because we must sum all slots. Both are wait-free since there is no contention or retrying.\n\nFor better read performance, use a combining tree where internal nodes cache partial sums. This makes increment O(log N) and read O(log N).\n\n---\n\n**Q4: When would you choose wait-free over lock-free?**\n\nChoose wait-free when:\n\n- Hard real-time requirements exist (missing deadlines is failure)\n- Formal verification is required (bounded behavior is provable)\n- Fairness is critical (no thread should ever starve)\n- Regulatory requirements mandate bounded response times\n\nChoose lock-free when:\n\n- Average performance matters more than worst-case\n- Starvation is acceptable (rare in practice)\n- Simplicity is important\n- Memory is constrained\n\nIn practice, lock-free is far more common because starvation is rare, wait-free overhead is significant, and the complexity of wait-free algorithms introduces bug risk.\n\n---\n\n**Q5: What is the difference between population-aware and population-oblivious wait-free algorithms?**\n\nPopulation-aware algorithms require knowing the number of threads N upfront. The progress bound is typically O(N). Example: array-based counter with N slots.\n\nPopulation-oblivious algorithms work without knowing N. Threads can join and leave dynamically. The bound is independent of thread count. Example: wait-free timestamp algorithms.\n\nPopulation-aware is more common because it is simpler to implement and faster. Population-oblivious is needed when threads are dynamic or the system cannot predict concurrency levels.\n\n---\n\n## Summary\n\n### Key Takeaways\n\n- Wait-free guarantees every operation completes in bounded steps (strongest progress guarantee)\n- The progress hierarchy: Blocking < Obstruction-Free < Lock-Free < Wait-Free\n- Helping mechanism: threads help complete each other's operations\n- Wait-free counter: per-thread slots give O(1) increment, O(N) read\n- Wait-free is rarely used in practice due to overhead and complexity\n- Lock-free is usually sufficient because starvation is rare\n\n### Quick Reference\n\n\n| Progress Guarantee | System Progress | Per-Thread Progress |\n|--------------------|-----------------|---------------------|\n| Blocking | No | No |\n| Obstruction-Free | In isolation | No |\n| Lock-Free | Yes | No (may starve) |\n| Wait-Free | Yes | Yes (bounded) |\n\n\n### Progress Bounds\n\n\n| Algorithm | Increment | Read |\n|-----------|-----------|------|\n| CAS counter (lock-free) | O(1) expected, unbounded worst | O(1) |\n| Array counter (wait-free) | O(1) bounded | O(N) |\n| Combining tree (wait-free) | O(log N) | O(log N) |\n\n\n### Course Conclusion\n\nThis chapter completes our journey through lock-free and wait-free programming. Starting from Compare-and-Swap, through atomic operations and memory ordering, to lock-free stacks and queues, and finally wait-free algorithms, you now have the conceptual foundation for understanding and implementing non-blocking concurrent systems.\n\nIn practice, most applications use locks for their simplicity. Lock-free is reserved for performance-critical paths. Wait-free is reserved for systems with the strictest requirements. Knowing when to use each, and understanding the trade-offs, is what separates a good concurrent programmer from a great one.\n\n---\n\n## References\n\n- Herlihy, M. \"Wait-Free Synchronization\" - ACM TOPLAS, 1991 (the original wait-free paper)\n- Herlihy, M. & Shavit, N. \"The Art of Multiprocessor Programming\" - Chapters 3, 6 on progress guarantees\n- Kogan, A. & Petrank, E. \"Wait-Free Queues with Multiple Enqueuers and Dequeuers\" - PPoPP 2011\n- Michael, M. & Scott, M. \"Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms\" - PODC 1996\n- Java LongAdder documentation - https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/LongAdder.html","pageType":"concurrency-interview"}

Wait-Free Algorithms

Ashish Pratap Singh

Get Premium