Gustafson's Law and the Universal Scalability Law

Symptom

Two measurements that both look like they break the previous post.

The first: your Spark job takes four hours on ten nodes. You move it to a hundred nodes and it still takes four hours — but it is now processing ten times the data. T081 said the ceiling was 20×, and nobody hit a ceiling.

The second, less pleasant: your service does 12,000 requests per second on 40 nodes. You provision 80, expecting somewhere north of 12,000 and prepared to settle for 15,000. You measure 10,400. The graph does not flatten — it turns over and goes down, and the only thing you changed was the amount of hardware.

Amdahl’s law explains neither, because Amdahl’s law is missing a term in one direction and an assumption in the other.

Statement

What T081 established, in two sentences: fix the workload, split a fraction of it across $N$ workers, and speedup is $1/((1-p) + p/N)$, bounded forever by $1/(1-p)$. Everything below keeps that algebra and changes what is held fixed.

Gustafson’s law. Hold time fixed instead of work. If $\alpha$ is the serial fraction of the scaled workload — the workload you actually run on $N$ nodes — then the scaled speedup is

Linear in $N$, with a slope slightly under 1. No ceiling.

The Universal Scalability Law (Gunther). Relative throughput on $N$ workers:

With $\beta > 0$ this function rises, peaks, and falls. The peak sits at

$$N^{*} = \sqrt{\frac{1-\alpha}{\beta}}$$

and beyond it, adding capacity removes throughput.

Argument

Gustafson is Amdahl asked backwards. Amdahl fixes the problem and asks how much faster $N$ workers finish it. Gustafson fixes the wall clock and asks how much more work $N$ workers get through. Normalise the parallel run to 1 unit of time, of which $\alpha$ is serial and $1-\alpha$ is parallel. To do that same work on one processor takes $\alpha + (1-\alpha)N$, since the parallel part now runs sequentially. Speedup is the ratio:

$$S(N) = \alpha + (1-\alpha)N = N - \alpha(N-1)$$

That is the entire derivation, and it is worth noticing that neither law is more correct than the other. They differ in one assumption — whether problem size is pinned — and the assumption is a fact about your workload, not a modelling choice. A user waiting on a request has a pinned problem: Amdahl. A nightly job that will happily chew a bigger shard: Gustafson.

The USL adds the term Amdahl is missing. Start by rewriting Amdahl as a throughput curve. With serial fraction $\alpha$,

$$S(N) = \frac{1}{\alpha + (1-\alpha)/N} = \frac{N}{1 + \alpha(N-1)}$$

which is the USL with $\beta = 0$. So Amdahl is a special case, and the question is what it left out.

It left out the workers talking to each other. Amdahl’s penalty term $\alpha(N-1)$ grows linearly: each additional worker waits on the same serial section. But cache-coherence traffic, distributed lock handoff, gossip, and cross-replica consistency are not one worker waiting on a queue — they are pairs of workers exchanging state, and there are $N(N-1)$ ordered pairs. Hence the term $\beta N(N-1)$, quadratic in $N$, in the denominator.

This is where the compound kind matters. The $\alpha$ term is algebra: it follows from the definition of a serial section, exactly as in T081. The $\beta$ term is not. It is a modelling choice — the functional form $N(N-1)$ is chosen because pairwise exchange is quadratic, and the coefficient $\beta$ is fitted to measurements by regression. That is why this post is tagged empirical first and theorem second. Nobody proved your system’s coherency cost is quadratic. Somebody observed that the curve fits, remarkably often, across systems that have nothing else in common.

The peak. Differentiate $C(N)$, set to zero, and the roots give

$$N^{*} = \sqrt{\frac{1-\alpha}{\beta}}$$

Work an example. A service measures $\alpha = 0.03$ and $\beta = 0.0005$ — a 3% serial fraction and a coherency cost most people would call negligible. Then $N^{*} = \sqrt{0.97/0.0005} = \sqrt{1940} \approx 44$.

$N$	$C(N)$
10	7.6×
20	11.4×
30	13.0×
44	13.6×
88	11.8×

Forty-four nodes is the maximum this architecture can deliver, ever. Doubling to 88 does not stall — it loses 13% of the throughput, while doubling the bill. That is the second symptom at the top of this post, and the number that predicts it was available from a load test on 5, 10, 20 and 30 nodes.

Forbids

Unbounded scale-out. With any $\beta > 0$ there is a hard maximum throughput at a computable $N$, and every node past it makes things worse. “Throw more nodes at it” is not a strategy that degrades gracefully; it reverses.

Reading a ceiling off Amdahl for a distributed system. Amdahl is the optimistic bound. It cannot express retrograde scaling because it has no term that can produce one, so a capacity plan built on it will be wrong in the expensive direction.

Extrapolating from two load points. Two points fit a line. Fitting $\alpha$ and $\beta$ needs enough points on both sides of the knee — six is the usual working minimum, and points beyond the peak are the most informative ones you can collect.

Citing Gustafson for a latency budget. If a user is waiting, the problem size is pinned by definition and the scaled-speedup framing does not apply.

Does not forbid

Gustafson does not repeal Amdahl. The commonest misuse, and it usually appears in a document justifying a cluster. Both laws are correct; they answer different questions. Any time the deliverable is “this specific request, faster”, the workload is fixed and Amdahl’s ceiling is the operative one. Gustafson applies to batch and throughput work, where a bigger machine means a bigger problem — which is precisely why HPC calls the two cases strong and weak scaling and insists that a benchmark say which it measured.

The USL does not prove that scaling stops around fifty nodes. $\alpha$ and $\beta$ are measured, not universal. Genuinely shared-nothing workloads — thumbnailing images off a queue, Monte Carlo runs, per-tenant sharded services — measure $\beta$ statistically indistinguishable from zero and scale nearly linearly as far as anyone has bothered to test. The law describes the shape of the curve; your architecture decides the constants, and driving $\beta$ toward zero is a design outcome rather than a fact of nature.

A good fit is not a diagnosis. Fitting $\beta = 0.0005$ tells you coherency cost exists. It does not tell you whether it is cache-line ping-ponging, a chatty coordinator, a distributed lock, or a connection pool. Teams that treat the fitted parameter as the finding, rather than as the prompt to go profiling, spend months optimising the wrong layer. The model is a curve fit over a system it knows nothing about.

Retrograde scaling is not always coherency. The USL folds every superlinear-cost mechanism into one term. In practice the turnover is often queueing at a shared resource, garbage-collection pressure, or a thread pool thrashing — mechanisms with their own theory (T083, T084) and their own fixes. The curve is right about the shape and silent about the cause.

Boundary

• Shard until $\beta$ vanishes. The direct engineering response: partition so that workers do not need to know about each other. Shared-nothing architecture is the USL’s $\beta$ term written as a design constraint.
• Fit the curve before buying the hardware. Six load points, a two-parameter regression, and $N^{*}$ falls out. This is the rare case where a model genuinely predicts the failure in advance.
• Weak scaling as an honest benchmark. If a vendor’s scaling graph does not say whether the problem grew, the graph does not say anything.
• The queueing side. Both laws are about parallel work. For a system serving arrivals, Little’s law (T083) and the $1/(1-\rho)$ utilisation blowup (T084) bind sooner and are the correct tools.
• The degenerate cases are worth holding onto. $\beta = 0$ gives Amdahl; $\alpha = \beta = 0$ gives perfect linear speedup. One formula contains the whole family, which is what the “universal” in the name is claiming.

Read next