Exercises

$\Delta_{\text{uncoded}} = 5 \cdot (1 - 1/20) = 5 \cdot 0.95 = 4.75$ GB.

$H_{10} \approx 1 + 0.5 + 0.333 + 0.25 + 0.2 + 0.167 + 0.143 + 0.125 + 0.111 + 0.1 \approx 2.929$.

$\mathbb{E}[T_{(10)}] = H_{10} / \lambda \approx 2.93$ time units — almost $3\times$ the per-worker mean of $1/\lambda = 1$.

$500 \cdot 10^7 \cdot 16 = 8 \cdot 10^{10}$ bits, i.e., $10$ GB per round.

False. The per-iteration latency is $\mathbb{E}[T_{(N)}] = H_N/\lambda$, which increases with $N$. Without redundancy, adding workers only slows things down — each extra worker adds one more exponential tail that can delay the iteration.

At $\mu = 1/N$: $(1 - 1/N)/(N \cdot 1/N) = 1 - 1/N$. ✓ At $\mu = 1$: $(1 - 1)/N = 0$. ✓

Let $f(\mu) = (1-\mu)/(N\mu) = 1/(N\mu) - 1/N$. Then $f'(\mu) = -1/(N\mu^2)$ and $f''(\mu) = 2/(N\mu^3) > 0$ for $\mu > 0$. Hence $f$ is convex in $\mu$, as required.

$\mathbb{E}[T_{(k)} - T_{(k-1)}] = 1/[(N-k+1)\lambda]$, so $\mathbb{E}[T_{(K)}] = \sum_{k=1}^K 1/[(N-k+1)\lambda] = (H_N - H_{N-K})/\lambda$.

$H_N - H_{N-K} = \ln(N/(N-K)) + o(1) = -\ln(1 - K/N) + o(1) \to -\ln(1-\alpha)$. Hence $\mathbb{E}[T_{(\alpha N)}] \to -\ln(1-\alpha)/\lambda$.

$d b = 10^8 \cdot 32 = 3.2 \cdot 10^9$ bits per user.

At $10^9$ bits/s ingress and $3.2 \cdot 10^9$ bits per user, the server can ingest $\sim 0.3$ users per second — or, stated in the opposite direction, just 0.3 users fit in the $1$-second budget. To serve $n = 1000$ users per round we either need compression (e.g., 1-bit quantization reduces it to $1$ user per $100$ ms) or a parallel-aggregation architecture.

A plaintext gradient can be inverted to reconstruct the training samples. Addressed in Chapter 10 (secure aggregation).

Timing and existence of uploads reveal that a particular user holds data matching the current model. Addressed by differential privacy and cover-traffic protocols in Chapter 18.

Even the aggregated model weights can memorize individual training samples. Addressed by DP-SGD (Chapter 9) and the PIR-style mechanisms of Part IV when applied to model serving.

$\mathbb{E}[T_{(8)}] = H_{10} - H_2 \approx 2.929 - 1.5 = 1.429$.

$\mathbb{E}[T_{(10)}] = H_{10} \approx 2.929$.

Tolerating just 2 stragglers cuts the iteration latency by roughly a factor of $2$. The cost of course is the storage/computation redundancy that Chapter 5 will quantify.

If all users are employees of one organization, the parameter server is run by that organization's SRE team, and the data is not regulated externally (HIPAA, GDPR, export controls), then the server is not an adversary — it is part of the trusted computing base. In this setting no privacy- preserving protocol is required, because there is no adversary to defend against.

The defense fails the moment any of the following becomes true: (i) users include external parties, (ii) the server is subject to a court order or subpoena, (iii) the server can be compromised by an attacker, (iv) the server's personnel are not contractually bound to the data owner. Each of these is the threat model addressed in Chapters 10–12.

$R(N) = H_N$. For $N = 10$: $R = 2.93$. For $N = 100$: $R = 5.19$. For $N = 10000$: $R = 9.79$.

The price of synchrony is sub-linear ($\Theta(\log N)$), but still substantial — a cluster of 10 000 workers pays almost $10\times$ its per-worker mean time on every synchronous barrier. This is one of the central empirical reasons coded computing exists.

Couple the $(N-1)$-sample system to the $N$-sample system by letting the first $N-1$ samples coincide. Then $T_{(N)}^{(N-\text{worker})} \geq T_{(N-1)}^{(N-1)-\text{worker}}$ pointwise, hence in expectation.

For a Pareto distribution with shape parameter $1 < \alpha \leq 2$, the increments $\mathbb{E}[T_{(N)}] - \mathbb{E}[T_{(N-1)}]$ can be non-monotone — they may grow in $N$ before shrinking, reflecting the heavy-tailed nature of the distribution. The intuition is that adding a new worker has a non-trivial chance of producing a very large outlier that dominates the order statistic.

Section 1.3's aggregation-cost bound gives $n d$ scalars of uplink even without privacy or robustness.

To detect (or at least bound) the corruption introduced by $B$ Byzantine workers, the protocol must receive enough redundant information to localize the corruption. Any linear-algebraic argument (e.g., Reed–Solomon error correction over gradient-sized vectors) requires at least $2B$ redundant scalars per coordinate — hence $\Omega(B d)$.

Adding baseline and overhead gives $\Omega(n d + B d)$. Chapter 11 makes this precise and characterizes the achievable rate region.

Total $100$ GB = $8 \cdot 10^{11}$ bits. Divide by $n = 10^6$ users: $8 \cdot 10^5$ bits/user/round.

Model $d b = 10^9 \cdot 32 = 3.2 \cdot 10^{10}$ bits. Fraction $\approx 2.5 \cdot 10^{-5}$ — about 25 000 out of $10^9$ coordinates.

Top-$K$ with $K = 25\,000$ keeps the largest-magnitude 0.0025% of gradient entries each round. Convergence remains provable under standard error-feedback techniques (Stich et al., 2018) with a slowdown factor of $\Theta(\sqrt{d/K}) \approx 200$ in round count. The combined wall-clock cost (uplink × rounds) is actually smaller than plaintext at these parameters — illustrating why compression is standard in production FL.

Let $L$ be the latency of a pure synchronous $K$-of-$N$ round: $\mathbb{E}[L] = (H_N - H_{N-K})/\lambda$. The hybrid scheme saves the time of the last finisher of the previous round that the buffer was able to absorb. By memorylessness this saving is again exponential with rate $\lambda$ and can be computed independently.

The absorbed round's last-response savings is $\mathbb{E}[T_{(N)} - T_{(K)}] = H_N/\lambda - (H_N - H_{N-K})/\lambda = H_{N-K}/\lambda$ over the pre-started round. Amortized over many rounds this gives a per-round saving of $H_{N-K}/(\lambda \cdot M)$ where $M$ is the absorbed-round stretch.

For moderate $M$ the hybrid scheme sits between fully synchronous $K$-of-$N$ (upper bound) and fully asynchronous (which has no staleness penalty only in expectation). It is roughly equivalent to using a slightly tighter recovery threshold — buying latency at the cost of coded-storage overhead.