You are designing a parallel workload in which every worker must synchronize at a global rendezvous at the end of each step before any worker starts the next step. What costs does that repeated global rendezvous impose as the number of workers and the variance in per-worker time grow, and when would you restructure the computation to avoid it?

## The model Bulk-synchronous parallel (BSP) computation alternates: every worker computes locally, then all workers meet at a global rendezvous, then the next step begins. It is a wonderfully simple model — each step's state is globally consistent, reasoning is almost sequential — and that simplicity is bought with three costs that all worsen with scale. ## Cost 1: you pay the maximum, not the average If worker *i* takes time *T_i* for a step, the step's wall-clock cost is `max(T_1..T_N)`, and the wasted worker-time is `Σ(max − T_i) = N·max − ΣT_i`. Two consequences: - **Even perfectly balanced work degrades with N.** For any non-degenerate distribution, `E[max of N samples]` increases with N. With exponential-ish tails it grows roughly like `mean·(1 + ln N / k)`; with heavy tails it grows much faster. Doubling the worker count does not just fail to halve step time — it raises the expected step time. - **Skew is multiplied, not absorbed.** In an asynchronous design, one slow task delays only its own consumers. Under a global rendezvous, one slow worker idles N−1 others *every step*. If one worker in a thousand suffers a 50 ms pause each step, and there are 10,000 steps, everyone pays those 500 seconds. Sources of skew are rarely algorithmic: uneven data partitions, cache/NUMA locality differences, runtime pauses (GC, JIT, page faults), OS scheduling and preemption, frequency scaling and thermal throttling, co-tenant noise on shared hardware. You cannot eliminate them; you can only stop amplifying them. ## Cost 2: Amdahl's law made concrete The rendezvous does real serial work: the last arrival's transition (buffer swap, convergence test, aggregation, metric emission), plus waking N blocked threads, plus the cache-coherence traffic of everyone touching the same synchronization state. Call the per-step serial fraction *f*. Amdahl's law bounds speedup at `1 / (f + (1−f)/N)` → `1/f` as N grows. If the transition costs 1% of a step, you cannot exceed 100× speedup no matter how many cores you buy — and that ignores the straggler term above, which makes the practical ceiling lower. Gustafson's counter-framing is the useful design lever: if you can grow the *problem size* per step as you add workers, the serial fraction shrinks relative to the parallel work, and scaling stays healthy. So the honest question is not "is a global rendezvous bad?" but "is my per-step parallel work large enough relative to the rendezvous cost, at the N I intend to run?" Making steps coarser — more work between rendezvous points — is often the cheapest fix. ## Cost 3: coupled failure and coupled latency N mutually dependent parties means the availability of the computation is the product of the parties' availabilities. One crashed, cancelled, or wedged worker blocks all the others indefinitely unless the rendezvous has bounded waits and an abort path. Recovery cannot resume mid-step, so you need checkpoints at step boundaries. This operational tax is real and is usually underestimated in design reviews. ## When to keep the global rendezvous - The algorithm requires a **globally consistent snapshot** per step (many iterative solvers, lock-step physics/game ticks, deterministic replay requirements, correctness proofs that depend on step atomicity). - Workers are **homogeneous** in work and hardware, so `max ≈ mean`. - The step is **coarse** relative to the rendezvous cost. - Determinism and debuggability are worth more than the last 20% of throughput — a very common and legitimate trade. ## Ways to restructure **Finer tasks + work stealing.** Cut work into many more units than there are workers and let idle workers steal. Load balances automatically and shrinks `max − mean`, at the cost of scheduling overhead and worse locality. This is the single highest-leverage change for skew that comes from uneven partitions. **Overlap steps (pipelining / double buffering).** Let a worker begin the part of step k+1 that does not depend on other workers' step-k output while the rendezvous completes. Converts a hard stop into a soft one; costs memory for the extra buffers and complicates reasoning. **Local instead of global synchronization.** Most stencil and graph computations only need each worker's *neighbours*, not the whole world. Replacing one global rendezvous with pairwise or neighbourhood handshakes turns an O(N)-coupled critical path into an O(degree)-coupled one, and one slow worker delays only its neighbourhood. **Asynchronous / relaxed iteration.** Some algorithms converge with stale inputs (chaotic relaxation, asynchronous gradient methods, gossip protocols). Dropping the step boundary removes the straggler term entirely, at the cost of determinism, a harder convergence argument, and much harder debugging. Only do this when you can state a convergence condition, not merely hope. **Bounded-staleness middle ground.** Allow workers to run ahead by at most *s* steps. One knob interpolates between full BSP (`s = 0`) and fully asynchronous, and lets you buy most of the straggler relief while keeping a bound you can reason about. **Backup/redundant execution.** Where tail latency comes from unpredictable environmental noise rather than work distribution, duplicate the straggling unit and take the first result. Costs capacity, buys tail predictability. ## How to decide Measure, do not theorize: per step, record each worker's compute time and its rendezvous wait time. If aggregate wait time is a small share of total, the rendezvous is not your problem and you should leave the simple model alone. If wait time is large, look at *which* worker is late: consistently the same one means partitioning or hardware skew (rebalance, or steal); a different one each step means environmental noise (coarsen steps, allow staleness, or use backup execution). Only after that evidence should you trade away the determinism that the global step boundary gives you.