Scaling Limits — Amdahl, Gustafson and the Coherency Penalty

Three models of what happens when you add machines: a hard ceiling, an escape from it, and the case where throughput actually falls.

AI SystemsAdvanced⏱ 1 hour8 min readamdahlgustafsonuniversal scalability lawspeedupcontention

1 problem →

AssumesLittle's Law and the Capacity of a Serving System

The ceiling

PropositionAmdahl's law

Let a fixed workload take unit time on one processor, of which a fraction $s \in [0,1]$ is serial and $1-s$ is perfectly parallelisable across $p$ processors. Then

T(p) \;=\; s + \frac{1-s}{p}, \qquad S(p) \;=\; \frac{T(1)}{T(p)} \;=\; \frac{1}{\,s + (1-s)/p\,} \;\xrightarrow[p\to\infty]{}\; \frac 1s .

Key idea

With 5% serial work the ceiling is $20\times$ , and 64 processors already deliver $15.4\times$ — 77% of everything more hardware will ever give. The practical reading is not "parallelism is futile" but measure $s$ before buying: the derivative $S'(p)$ falls off a cliff at $p \approx 1/s$ , and spending past that point is close to pure waste.

The escape

Amdahl assumes the problem is fixed. Often it is not: given more machines, people run bigger batches, longer contexts, more shards.

PropositionGustafson's scaled speedup

Suppose that on $p$ processors the work is sized so that the run takes unit wall-clock time, of which $\sigma$ is serial and $1-\sigma$ is parallel. The same work on one processor would take $\sigma + (1-\sigma)p$ . Hence

S_{\text{scaled}}(p) \;=\; \sigma + (1-\sigma)\,p ,

which is linear in $p$ with no ceiling.

The case where more machines are worse

Both laws above are monotone in $p$ . Real distributed systems often are not: throughput peaks and then declines. The universal scalability law adds a term for the cost of keeping $p$ participants consistent, which grows like the number of pairs.

PropositionThe universal scalability law has an interior maximum

Define relative capacity

C(p) \;=\; \frac{p}{1 + \alpha\,(p-1) + \beta\,p\,(p-1)} ,

with $\alpha \ge 0$ the contention coefficient (serialisation, as in Amdahl) and $\beta \ge 0$ the coherency coefficient (pairwise consistency traffic). If $\beta > 0$ then $C$ is maximised at

p^\star \;=\; \sqrt{\frac{1-\alpha}{\beta}} ,

and $C(p) \to 0$ as $p \to \infty$ .

Assumptions

This is a two-parameter model, fitted to measurements, not a theorem about computation. Its justification is that $\alpha$ captures a queueing-like serial term and $\beta$ a term proportional to $\binom p2$ pairwise interactions; whether a given system obeys it is an empirical question. It is stated here because the qualitative prediction — an interior maximum — is real and is routinely observed.

With $\alpha = 0.03$ and $\beta = 10^{-4}$ the formula gives $p^\star \approx 98$ , and a direct search over integer $p$ agrees at $98$ . Beyond that, adding machines reduces total throughput.

Key idea

The three regimes are distinguished by a single question: what has to agree with what?

Nothing shared, no serial section: linear scaling.
A serial section: Amdahl, flattening at $1/s$ .
Every participant must see every other's updates: coherency, peaking at $\sqrt{(1-\alpha)/\beta}$ and then falling.

A distributed KV cache with cross-replica invalidation is in the third regime. Independent stateless replicas behind a load balancer are in the first. Which one you are in is an architectural choice, not a tuning parameter.

What this does not say

None of these models say anything about latency — they are all statements about throughput or completion time of a fixed job. A system can be scaling perfectly by $C(p)$ while its p99 degrades, because adding replicas increases fan-out, and Tail Latency and Fan-Out Amplification showed what fan-out does to a tail. Capacity and tail latency must be tracked separately; optimising one routinely damages the other.

References

PaperG. M. Amdahl (1967). Validity of the Single Processor Approach to Achieving Large Scale Computing CapabilitiesTwo pages, and the source of the ceiling argument.
PaperJ. L. Gustafson (1988). Reevaluating Amdahl's LawPoints out that the fixed-problem-size assumption is what produces the ceiling.
BookN. J. Gunther (2007). Guerrilla Capacity PlanningDevelops the universal scalability law and its two-parameter fit.

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

PropositionAmdahl's lawproof includedIf a fraction s of the work is inherently serial, speedup is capped at 1/s however many processors are added.
PropositionGustafson's scaled speedupproof includedIf the problem grows with the machine so that the serial part stays fixed in absolute time, speedup is linear in the processor count.
PropositionThe universal scalability law has an interior maximumproof includedWith a coherency term, capacity peaks at p* = sqrt((1−α)/β) processors and decreases beyond it.

Problems (1)

All problems

Fit a scalability curve and find where it turns overNumericalAdvanced⏱ 1 hour