Barriers

The problem it solves

Work that happens in phases. Every worker computes its part, then every worker combines the results. The second phase is only correct if the first has finished — all of it, not just this worker’s share.

Without something enforcing that, the ordering is a hope. A worker that finishes its own contribution early moves straight on to reading the total, gets a number that is still being assembled, computes on it, and reports success. Nothing errors. Nothing in the program knows that phase one was unfinished, because there is nothing in the program that represents “phase one is finished”.

A barrier is that representation. Every participant arrives; nobody leaves until everybody has arrived; then everybody leaves together. It makes the phase boundary a real thing rather than an assumption about timing.

The mechanism

A barrier is created with a participant count. await blocks until that many threads have called it, at which point all of them are released.

The subtlety worth knowing — and the one this page’s engine got wrong first — is what “released” means. It is not enough to reset the arrival count. The waiting threads are parked at the barrier, and if the count is cleared without moving them past it, they arrive a second time and wait for a group that has already gone. The barrier must advance everyone it releases, which is why real implementations carry a generation: a waiter records which generation it arrived in, and is released when the barrier moves beyond it.

That generation is also what makes a barrier reusable. Java’s CyclicBarrier resets automatically and can be used for phase after phase; CountDownLatch does not reset and is a one-shot. Choosing the wrong one gives you either a latch that cannot be reused or a barrier that lets a fast worker lap the group and arrive at the next phase’s barrier while others are still in this one.

What the enumeration shows

Three workers, each contributing to a total and then reading it.

With the barrier: no interleaving reads a partial total. Step through and watch two workers park at the barrier with their badges showing barrier sync while the third is still working — that waiting is the cost, and it is exactly the slowest participant’s duration.

Without it: 1,866 of 2,500 interleavings read a partial total. Not a corner case; the overwhelming majority. And the run completes normally in every one of them, with a wrong number and no indication anywhere that anything went wrong. That silence is the reason this failure is worth demonstrating rather than describing — a race that crashes gets fixed, and a race that returns a plausible number does not.

The numbers worth carrying

• Three workers, two phases, no barrier: 1,866 of 2,500 interleavings compute on incomplete data. With a barrier: 0.
• A barrier costs the slowest participant, every phase. With n workers of variable duration, expected phase time is the expected maximum of n samples, not the mean — which grows with n even when the mean does not. This is the same arithmetic as tail latency amplification, and it is why barriers and stragglers are one conversation.
• Consequence: adding workers to a barrier-synchronised phase has diminishing and eventually negative returns, because each extra worker is another chance to draw a slow sample.

Where it breaks down

The participant count must be exact. A barrier for three that only ever sees two arrivals blocks forever. This is a real hazard when the count is derived from configuration, or when a worker dies mid-phase — and it produces a hang, not an error. CyclicBarrier addresses the second case with BrokenBarrierException: if any waiter is interrupted or times out, the barrier breaks and everybody is released with an exception, on the reasoning that a partially-arrived barrier is not recoverable.

Barriers serialise on the maximum. If one worker consistently takes twice as long, the barrier makes every worker take that long. The fix is not a better barrier — it is work stealing, so that idle workers take from the slow one rather than waiting for it.

Nested barriers deadlock easily. Two groups of workers that each wait on the other’s barrier is the same cycle as deadlock, with barriers as the resource.

A barrier is not a memory fence in every language, but usually is. The release must establish happens-before between phase one’s writes and phase two’s reads or the barrier guarantees ordering and not visibility — see visibility. Java’s CyclicBarrier and C++’s std::barrier both provide it; a hand-rolled counter plus condition variable provides it only because the mutex does.

What people get wrong

“A barrier makes it faster.” It makes it correct and slower. It adds waiting; what it buys is that phase two reads finished data.

“CountDownLatch and CyclicBarrier are the same.” A latch counts down once and stays open — one-shot, and the counting-down threads need not be the waiting ones. A barrier resets and is symmetric: everybody who arrives also waits. Using a latch for repeated phases means allocating a new one per phase, which is a common and workable pattern but a different one.

“The last thread does the combining.” That is a legitimate design — CyclicBarrier takes an optional barrier action run by the last arriver — and it is not the default. Assuming it happens without arranging it is how the partial read on this page occurs.

“We can skip it because the phases are obviously ordered.” Obvious to a reader, not to the scheduler. The enumeration shows 1,866 orderings that disagree.

In production

CyclicBarrier and CountDownLatch in Java, std::barrier and std::latch in C++20, sync.WaitGroup in Go — which is a latch rather than a barrier, since Wait blocks the coordinator while Done is called by workers who do not themselves wait. asyncio.Barrier arrived in Python 3.11. pthread_barrier_t exists and is optional in POSIX, which is why some platforms lack it.

Where you meet them without naming them: every bulk-synchronous parallel computation, every simulation timestep, every map-then-reduce, every GPU kernel launch boundary, and the join phase of a fork-join pool. Anywhere the phrase “wait for all of them to finish” appears in a design, a barrier or a latch is what implements it.

The practical advice: prefer a latch for one-shot “wait until these are done” and a barrier for repeated phases; prefer a higher-level construct — invokeAll, WaitGroup, a task group — over hand-rolling either; and if the phase time is dominated by one slow participant, stop synchronising harder and start balancing the work.

The follow-up questions

“What is the difference between a latch and a barrier?” — One-shot and asymmetric versus reusable and symmetric. Say which you would use for repeated phases.

“What does a barrier cost?” — The slowest participant, every phase. Then the point about expected maximum growing with the worker count.

“A worker dies before reaching the barrier. What happens?” — Everyone else waits forever, unless the barrier can be broken. This is why BrokenBarrierException exists.

“You remove the barrier and the program still gives the right answer in testing.” — 1,866 of 2,500 orderings say otherwise; testing sampled the lucky ones. A good moment to mention that correct output is not evidence of a correct program.