Chapter Summary

Chapter Summary

Key Points

• 1.

  Bonawitz's $O(n^2)$ communication overhead is the scalability bottleneck for large-$n$ FL. At $n = 10^5$, the protocol's pairwise-DH-exchange phase alone takes hours per round. Caire et al. (2022) proved this is information-theoretically optimal within the uncoded groupwise-key class — so any improvement requires leaving the class.

• 2.

  CCESA breaks the $O(n^2)$ barrier with a sparse Erdős–Rényi random graph. Edge probability $p = c\\sqrt{\\log n/n}$ instead of $p = 1$ (Bonawitz). Communication overhead drops to $O(n\\sqrt{n/\\log n})$, sub-quadratic. Privacy and reliability guarantees hold with high probability ($\\geq 1 - n^{-\\Theta(1)}$ failure) — operationally equivalent to deterministic Bonawitz.

• 3.

  The four CommIT-group Part III contributions form a coherent stack. Bonawitz baseline (2017), Caire et al. optimality within uncoded class (2022, Chapter 10), ByzSecAgg with Byzantine resilience (2023, Chapter 11), and CCESA with sub-quadratic scaling (2022, Chapter 12). Together they define the information-theoretic frontier of privacy-preserving FL.

• 4.

  Protocol choice depends on $n$ and threat model. Bonawitz for small $n$ (up to 500) and simple threat models; ByzSecAgg for Byzantine resilience; CCESA for large $n$ with passive threats; differential-privacy variants for unlimited scaling at weaker guarantees. The decision tree of §12.4 makes the choice precise.

• 5.

  Open problems remain. Closing the polylog gap in CCESA's bound, combining privacy + Byzantine + scaling in a single protocol, adaptive Byzantine resilience in the random-graph setting, asynchronous variants — all active research directions. Chapter 18 surveys these.