Amdahl's law says parallel speedup is capped at 1 divided by the serial fraction, while Gustafson's law predicts speedup that keeps growing with processor count. Which assumption differs between the two models, and when does each one apply?

## The two questions Both laws model the same program with the same sequential portion. They disagree because they ask different questions. **Amdahl asks:** *I have this exact job. How much faster can N processors finish it?* Problem size fixed, hardware grows. This is **strong scaling**. **Gustafson asks:** *I have this much time. How much more work can N processors do in it?* Runtime fixed, hardware and problem grow together. This is **weak scaling**. ## Why the fixed thing changes the answer Under Amdahl, normalize the one-worker runtime to 1 and split it into serial `s` and parallel `1 - s`. Adding workers shrinks only the parallel part, so as N grows the serial seconds become a larger *share* of a shrinking total. The serial part is the bottleneck by construction, and speedup saturates at `1/s`. Gustafson starts from the other end: measure the *parallel* execution. Suppose on N workers the run spends fraction `s` of its time serial and `1 - s` in parallel work that N workers are all busy on. Doing that same work on one worker would take `s + N(1 - s)` time units, because the parallel portion would have to be executed N times over sequentially. So: `S(N) = s + N(1 - s) = N - s(N - 1)` This is linear in N with slope `1 - s`. There is no ceiling. The key move is that the parallel workload **grew with the machine** — bigger mesh, more rows, more requests — while the serial startup/aggregation stayed about the same size. ## A worked comparison Take `s = 0.05` and `N = 100`. - Amdahl: `1 / (0.05 + 0.95/100) = 16.8x`. Discouraging. - Gustafson: `100 - 0.05 x 99 = 95.05x`. Nearly linear. Nothing about the program changed. The first number says "a fixed job will not get 100x faster"; the second says "in the same wall-clock time you can process about 95x more work." Both are true statements about the same system. ## Which one your situation is Ask what a stakeholder will do with more hardware. **Amdahl-shaped (strong scaling)** when the input is given and latency is the goal: - One nightly report that must finish before 6am. - One simulation of a fixed model that must return in an hour. - A single request's tail latency. Here the serial fraction is the enemy and the ceiling is real. Buying 4x the cores for a job with 20% serial work gets you 2.5x and nothing more will help. **Gustafson-shaped (weak scaling)** when the workload expands to fill capacity: - A web service: more instances serve more concurrent users. - A search index: bigger machine, bigger corpus, same query latency. - Scientific simulation at higher resolution as the cluster grows. Here added capacity converts into more work done, and near-linear scaled speedup is achievable — provided per-worker coordination cost does not grow. Many real systems are a blend: capacity scales weakly (more nodes, more traffic) while each individual request is strongly bound by its own serial critical path. It is entirely normal for a service to scale throughput almost linearly to 50 nodes while single-request latency refuses to improve at all. Those two facts are Gustafson and Amdahl describing different axes of the same system, not a contradiction. ## Where each model over-promises Gustafson's optimism has conditions, and interviews probe them: 1. **The serial part must not grow with the problem.** If aggregation, coordination, or the final merge scales with input size or with N, the constant-`s` assumption breaks and the linearity collapses. 2. **The problem must actually be scalable.** Some workloads have a natural size; you cannot "scale up" reconciling last month's ledger. 3. **Coordination cost is still ignored.** Like Amdahl, Gustafson assumes free communication. At high N, crosstalk between workers can eat the gains — a cost neither law models, and one that requires a model with an explicit interaction penalty. 4. **Bigger results are not always more valuable.** A 100x larger simulation is only progress if the extra resolution is useful. ## How to answer this in an interview Do not describe them as rival claims where one is right. Say: same program, same serial fraction, different constraint held fixed — size versus time. Then name your own system's constraint and pick the matching model. The strongest answers add the caveat that both laws assume perfect, cost-free parallel work, so both are upper bounds; measured curves sit below them and, unlike either formula, can turn downward at high concurrency.