The question this answers
How do N workers agree that a phase is finished before any of them starts the next one?
A physics step over a 4,000-cell grid split across 4 workers: each phase computes new cell values from its neighbours' *previous* values, and there are 200 phases.
The grid itself, plus a phase counter. Each worker writes only its own slice but reads its neighbours' boundary cells — which is exactly why the phase boundary has to be a hard line rather than a suggestion.
Every read in phase k observes a value written in phase k−1 and never one written in phase k. No worker begins phase k+1 while any worker is still in phase k.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The line, and why it has to be a line
A barrier is a rendezvous for N participants: each one calls await on it, blocks, and none of them proceeds until the Nth arrives — at which point all N are released. It is symmetric (everyone waits for everyone) and reusable (the next phase uses the same barrier), which is what distinguishes it from a latch (Latches & Countdowns).
The reason a stencil computation needs one is the invariant above. Worker 2 reading worker 1's boundary cell must read the *previous* phase's value. If worker 1 is allowed to race ahead and overwrite that cell with its phase-k value, worker 2's phase-k result is computed from a mixture of two phases. The simulation does not crash; it produces a plausible, wrong number, and it produces a different wrong number on every run. That is Nondeterminism: Same Input, Different Output at its most expensive.
The waiting is real cost. The barrier releases at the pace of the slowest participant, every phase, 200 times. If one worker's slice is 20% heavier, the other three idle for 20% of every phase and the whole computation runs at the slow worker's speed. Load balance is not an optimisation here; it is the dominant term.
The schedule where the barrier is not enough
Having a barrier is not the same as putting it in the right place, and the classic error is a single barrier per phase where the algorithm needs two. With one barrier, workers are synchronised at the *end* of compute — but nothing prevents a fast worker, released from the barrier, from writing its phase-k+1 values into the shared grid while a slow worker is still reading those same cells for its phase-k computation. It arrived at the barrier; it just kept reading afterwards.
The fix is either double buffering — read from grid A, write to grid B, swap at the barrier, so a write can never land on a cell someone is reading — or two barriers per phase, one after compute and one after the write-back. Double buffering costs memory and is almost always the better trade because it removes the synchronisation rather than adding to it. This is Copy or Share? applied to a hot loop.
| # | Worker 1 (fast) | Worker 2 (slow) | Barrier (N=2) | State |
|---|---|---|---|---|
| 1 | phase 1: computes its slice from neighbours | · | · | phase=1 cell[100]=v0 arrived=0 |
| 2 | writes its slice; arrives at the barrier | · | · | phase=1 cell[100]=v1 arrived=1 |
| 3 | · | phase 1: computes, writes, arrives at the barrier | · | phase=1 cell[100]=v1 arrived=2 |
| 4 | · | · | count reached 2 — releases both workers | phase=2 cell[100]=v1 arrived=0 |
| 5 | phase 2: computes its slice quickly and writes cell[100] = v2 | · | · | phase=2 cell[100]=v2 |
| 6 | · | phase 2: reads neighbour cell[100] expecting the phase-1 value, gets v2 | · | phase=2 cell[100]=v2 ✕ W2's phase-2 result mixes a phase-1 value for most neighbours with a phase-2 value for cell[100]. No exception, no assertion, a different wrong answer every run. |
| 7 | · | writes a corrupted slice; arrives at the barrier | · | phase=2 corrupted=yes |
Implementing one, and the generation counter that stops it eating itself
A reusable barrier has a subtle bug that a one-shot latch does not: after release, a fast participant can loop around and re-enter the *same* barrier before a slow participant has finished waking from the previous release. If the barrier is just a counter, that fast arrival increments a count the slow participant is still reading, and one participant can be released twice while another waits forever.
The standard fix is a generation counter. Waiters capture the current generation before blocking and wake only when the generation changes; the releasing participant increments the generation and resets the count atomically. std::barrier in C++20 does exactly this with its phase token, and every correct implementation does something equivalent.
The implementation below is for tasks on one event loop, so the counter needs no atomics — a check and increment with no await between them is atomic here (Event Loops as a Concurrency Model). Across real threads the same structure needs a mutex or Atomics, and the timeout question becomes harder: a barrier with a timeout must decide whether a timed-out participant *breaks* the barrier for everyone (Java's CyclicBarrier does; the alternative is a permanently short-handed barrier that hangs forever).
1class Barrier {2 private count = 03 private generation = 04 private waiters: Array<{ gen: number; resolve: () => void; reject: (e: Error) => void }> = []5 private broken: Error | null = null6 7 constructor(private readonly parties: number) {8 if (parties < 1) throw new RangeError('parties must be >= 1')9 }10 11 // Returns the generation that just completed, so callers can assert phase order.12 async arrive(timeoutMs?: number): Promise<number> {13 if (this.broken) throw this.broken14 15 // Check-and-increment with no await between: atomic on one event loop.16 const gen = this.generation17 this.count += 118 19 if (this.count === this.parties) {20 this.generation += 1 // bump BEFORE waking, so re-entrants join the next generation21 this.count = 022 const waking = this.waiters23 this.waiters = []24 for (const w of waking) w.resolve()25 return gen26 }27 28 return new Promise<number>((resolve, reject) => {29 const entry = {30 gen,31 resolve: () => resolve(gen),32 reject,33 }34 this.waiters.push(entry)35 36 if (timeoutMs !== undefined) {37 setTimeout(() => {38 if (this.generation !== gen) return // already released; nothing to do39 // A late participant would leave everyone hanging. Break the barrier40 // for ALL waiters rather than leaving a short-handed barrier forever.41 this.break_(new Error('barrier timed out waiting for ' + (this.parties - this.count) + ' parties'))42 }, timeoutMs)43 }44 })45 }46 47 break_(err: Error) {48 this.broken = err49 this.generation += 150 this.count = 051 const waking = this.waiters52 this.waiters = []53 for (const w of waking) w.reject(err)54 }55}56 57// Usage: 200 phases over a double-buffered grid.58// Double buffering is what makes ONE barrier per phase sufficient.59async function worker(id: number, bar: Barrier, buffers: [Grid, Grid]) {60 for (let phase = 0; phase < 200; phase++) {61 const read = buffers[phase % 2]62 const write = buffers[(phase + 1) % 2]63 computeSlice(id, read, write) // never writes where anyone is reading64 await bar.arrive(5_000) // a hung worker fails everyone, loudly65 }66}Key points
- A barrier is symmetric and reusable: every participant waits for every other, then all proceed, and the same barrier serves the next phase.
- It synchronises *arrival*, not *access*. Reads and writes to shared cells after release can still cross a phase boundary.
- Double buffering — read from A, write to B, swap at the barrier — removes the hazard instead of adding a second barrier to guard it.
- The barrier runs at the pace of the slowest participant, every phase, so load imbalance is multiplied by the phase count.
- A reusable barrier needs a generation counter, or a fast participant re-entering can be released twice while a slow one waits forever.
- A participant that never arrives hangs everyone. A timeout must break the barrier for all parties rather than leaving it short-handed.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • The barrier holds a party count N, an arrival count, and a generation number.
- • Each participant increments the arrival count and, if it is not the Nth, records the current generation and waits.
- • The Nth arrival increments the generation, resets the arrival count to zero, and wakes every waiter recorded against the old generation.
- • Waking all N at once is what makes it a rendezvous rather than a handoff — nobody is released early.
- • Because the generation was bumped before waking, a fast participant that immediately re-enters joins the *next* generation instead of corrupting the current one.
- • On failure — a timeout or a participant throwing — a correct implementation transitions to a broken state and fails every current and future arrival, so the hang becomes an error.
- • W1 arrives (count 1); W2 arrives (count 2 = N); the barrier releases both; both proceed to phase 2 — the schedule that works.
- • W1 released, races ahead, writes cell[100] with its phase-2 value; W2 reads cell[100] expecting the phase-1 value — a phase boundary crossed with the barrier fully intact, and a silently wrong answer.
- • Without a generation counter: W1 is released and re-enters, incrementing count to 1; W2 has not finished waking and now sees count 1 in a barrier it thought it had passed; a later arrival releases W1 twice and leaves W2 waiting for a party that already went.
- • W3 crashes before arriving. With no timeout, W1, W2 and W4 wait forever and the process looks alive; with a timeout that only fails W3, the barrier is permanently short-handed; with a barrier that breaks for everyone, all four fail fast and the supervisor restarts the job.
- • One worker is 20% slower every phase; over 200 phases the other three spend 20% of the total wall-clock blocked, and the computation runs at the slow worker's speed exactly.
- • Guaranteed: no participant returns from the barrier until all N have arrived.
- • Guaranteed: all N are released together — no participant gets a head start from the barrier itself.
- • Guaranteed: with a generation counter, a fast re-entrant participant joins the next phase rather than disturbing the current one.
- • NOT guaranteed: any ordering of what participants do *after* release. Fast ones will race ahead immediately.
- • NOT guaranteed: protection of shared data. The barrier is a rendezvous, not a lock; concurrent access between barriers is your problem.
- • NOT guaranteed: progress if a participant dies. Without a timeout or a broken-barrier state, the default outcome is a silent hang.
- • NOT guaranteed: fairness of release order, which is why algorithms must not depend on who resumes first.
- • Every participant waits for the slowest, every phase — the total idle time is (N−1) × (slowest − average) × phases, and it is usually the largest single loss in a phased computation.
- • The barrier's own counter is a contention point across real threads; at high phase rates and high N, the atomic increment and the wake storm are measurable.
- • Releasing N waiters simultaneously is a wake burst — a small, well-behaved Thundering Herd that is fine at N=8 and is not fine at N=10,000.
- • Blocked participants on an event loop are cheap (a pending promise); blocked OS threads hold stacks and scheduler slots, so a barrier over threads costs more to wait at.
- • Hang: one participant never arrives and every other waits indefinitely with no error and a healthy-looking process.
- • Phase leakage: a released participant writes data another is still reading for the previous phase — wrong results, no error, non-reproducible.
- • Double release from a missing generation counter: one participant passes twice while another starves.
- • Broken-barrier cascade: a timeout fails every party, which is the correct behaviour and still means the whole job dies from one slow worker.
- • Deadlock by miscount: the barrier is constructed for N parties and only N−1 ever call it, so the first phase never completes.
- • Starvation of unrelated work: on an event loop, a barrier implemented with busy-waiting instead of promises never yields and blocks everything (Busy Waiting).
- • Iterative numerical work — stencils, simulations, graph algorithms in rounds — where each phase depends on the previous phase's complete output.
- • Parallel algorithms in the bulk-synchronous shape: compute locally, exchange at the boundary, repeat.
- • Warm-up coordination: N workers must all be ready before the benchmark or the load test starts, so nobody measures start-up.
- • Test harnesses that need every participant poised at the same instant to make a race likely (Stress Testing: A Test That Passed Once Proves Nothing).
- • Unbalanced work, where the barrier converts imbalance directly into idle time multiplied by the phase count.
- • Fine-grained phases, where the synchronisation cost per phase rivals the work per phase — merge phases instead.
- • Large N, where the wake burst and the counter contention dominate.
- • Any situation where participants can fail independently and the job should survive it; a barrier makes every participant a single point of failure for all the others.
- • Time spent blocked at the barrier per participant per phase. The spread across participants *is* the load imbalance, quantified.
- • Phase duration distribution: if p99 is far above p50, one participant is intermittently slow and everyone pays for it.
- • Barrier arrival timestamps per participant, which tells you *which* worker is late rather than just that someone is.
- • For correctness: a per-phase checksum of the grid compared against a single-threaded reference run. Phase leakage shows up here and nowhere else.
- • Count of broken-barrier events, which is the difference between "the job hung" and "the job failed at 15:04 because worker 3 stopped responding".
- • The party count becomes a configuration coupling: every place that spawns workers must agree with the barrier's N, and a mismatch is a hang rather than an error.
- • Timeout policy is a real design decision with no free option — break for everyone, or risk a permanently short-handed barrier.
- • Double buffering doubles the memory for the shared structure and adds a swap that must not be forgotten.
- • Debugging a barrier hang requires knowing who has not arrived, which means instrumenting arrivals before you need it — after the hang it is too late.
- • A latch (
CountDownLatch,std::latch) when the wait is one-shot and asymmetric — one coordinator waiting for N workers to finish. Simpler, and it cannot be re-entered wrongly (Latches & Countdowns). - •
Promise.all/gather/ fork-join, when each phase can be expressed as "start N tasks, wait for all, start the next N". Same synchronisation, no barrier object, and failure handling comes for free (Promise.all & gather). - • Message passing between phases: each worker sends its boundary to its neighbours and waits for theirs. More messages, no global rendezvous, and a slow worker only delays its neighbours (Message Passing).
- • Restructure to remove the phase dependency — asynchronous or chaotic relaxation converges without global phases for some problems, trading determinism for the elimination of all this waiting.
- • Do fewer, larger phases. Halving the phase count halves every cost in this lesson.
Barrier vs latch
barrier every worker blocks at await(); the last arrival releases all N, and the barrier resets
wall = max(phase1) + max(phase2) = 95 + 57 = 152 ms
latch workers count down and carry on; a separate waiter is released when the count hits 0
wall = max(phase1) + finalise = 95 + 20 = 115 ms — and the latch cannot count up again
none wall = max over workers of (phase1 + phase2) = 142 ms, with no happens-before edge at allFork/join and the split threshold
fork(lo, hi): if (hi - lo <= 64) return sequential(lo, hi) // the base case is the tuning knob mid = (lo + hi) / 2 left = spawn fork(lo, mid) // +0.05 ms right = fork(mid, hi) // run one half on THIS thread return left.join() + right // join is where the parallelism ends levels requested 4 → 4 actually taken leaves 16 × 256 elements span 0.91 ms total 1.21 ms
The lost update, step by step
| # | Task A — counter++ | Task B — counter++ | State |
|---|---|---|---|
| 1 | rA ← counter | · | counter=0 rA=0 rB=— |
| 2 | · | rB ← counter | counter=0 rA=0 rB=0 |
| 3 | rA ← rA + 1 | · | counter=0 rA=1 rB=0 |
| 4 | counter ← rA | · | counter=1 rA=1 rB=0 |
| 5 | · | rB ← rB + 1 | counter=1 rA=1 rB=1 |
| 6 | · | counter ← rB | counter=1 rA=1 rB=1 ✕ 2 increments completed, counter = 1 |
What people believe, and what is true
A barrier protects the shared data between phases.
It coordinates arrival. Between barriers, concurrent access is entirely unprotected — that is what double buffering or a lock is for.
A barrier and a latch are the same thing.
A barrier is symmetric and reusable — everyone waits for everyone, repeatedly. A latch is one-shot and asymmetric — waiters wait, workers count down, and it never resets.
If a worker is slow we lose only its extra time.
You lose that extra time multiplied by (N−1) participants and by the number of phases. A 20% slow worker makes the whole job 20% slower, every phase.
Go deeper
Overview
Everyone stops at the line; when the last one arrives, everyone goes. Reusable for the next phase.
Practical
Double-buffer so one barrier per phase is enough, give every arrival a timeout that breaks the barrier for all parties, and record arrival timestamps so a hang names the guilty worker.
Advanced
The generation counter is what makes reuse safe; without it a fast re-entrant participant corrupts the count the slow one is still reading. C++20 exposes this as a phase token you can wait on explicitly.
Internals
Threaded implementations use an atomic counter plus a futex or condition variable, and the last arrival performs the reset and the broadcast wake. The broadcast is why large-N barriers get expensive: N−1 threads become runnable simultaneously and contend for cores and for the cache lines they are about to touch.