A Converse Argument and the Roadmap to Part II–V

Why the Converse Matters as Much as the Construction

A coding-theoretic result consists of two halves: an achievability (a construction reaching a target rate) and a converse (a proof that no scheme can do better). The achievability is what an engineer builds; the converse is what tells the engineer when to stop looking for a better scheme. Without the converse, the tradeoff curve is merely a plausible heuristic — with it, the curve is a law.

This short section develops the converse argument for the computation–communication tradeoff in enough detail to make the cut-set mechanics clear, then hands off to the later chapters that apply the same recipe to privacy (Ch 10), PIR (Ch 13), and AirComp (Ch 16).

Theorem: Cut-Set Converse for Coded Shuffling

Any distributed-computing scheme over $N$ workers with storage load $\mu$ must have communication load $\Delta \;\geq\; \frac{1 - \mu}{N\mu}.$ Equivalently, the achievable curve of Section 2.3 is information-theoretically tight: no scheme, coded or otherwise, can beat $(1-\mu)/(N\mu)$ at storage $\mu$ .

The master must reconstruct intermediate values for each of the $N$ keys; each key is $F/N$ bits. If a worker stores a fraction $\mu$ of the dataset, the missing fraction (that must come from network traffic) is $1 - \mu$ . Spreading this deficit across the $N\mu$ workers that could in principle help (those that store the relevant portion) gives per-recipient traffic of at least $(1-\mu)/(N\mu)$ . The full proof replaces this informal counting by a formal cut-set argument over subsets of workers.

Proof

Identify the cut

Fix a worker $i$ and a subset $\mathcal{S} \subseteq \{1, \ldots, N\} \setminus \{i\}$ of workers that do store the intermediate values that $i$ needs. By the storage constraint, each intermediate value assigned to $i$ is held by some subset of $\mathcal{S}$ of size at most $\mu N$ .

Apply the Output-Entropy Bound

From Theorem (Output-Entropy Bound, §2.1), the messages $\{X_j : j \in \mathcal{S}\}$ must contain at least $H(Y_i \mid \mathcal{D}_i)$ bits, the conditional entropy of worker $i$ 's target output given its storage.

Symmetrize over $\mathcal{S}$

Averaging over all size- $(N-1)$ subsets $\mathcal{S}$ and using the symmetry of the storage mapping, one obtains $\sum_{k \neq i} H(X_k) \geq F(1-\mu) \frac{N-1}{N\mu}.$

Close the loop

Summing over all $i$ and normalizing by $F$ gives $\Delta \geq (1-\mu)/(N\mu)$ . Equality holds for the construction in §2.3. $\blacksquare$

This Is the Template for Every Converse in the Book

The four-step recipe — identify the cut, apply an entropy bound, symmetrize over subsets, normalize — is exactly the template that Chapters 10–16 will reuse with different specializations:

Chapter	Cut	Entropy quantity	Symmetrization
Ch 10 (secure aggregation)	server vs. any $T$ users	$I(\mathbf{g}_k; \text{view of server})$	over $\binom{n}{T}$ subsets
Ch 13 (PIR)	user vs. any $N - T$ databases	$H(Q_k \mid W)$	over colluding sets
Ch 16 (AirComp)	receiver vs. $n$ users	$I(Y; \{x_k\})$	over power allocations

Once a reader is comfortable with the cut-set recipe, the converses of Parts III–V follow quickly — they are variations on a theme, not separate techniques.

Example: Converse for $N = 3$ Workers

Illustrate the cut-set argument on a three-worker MapReduce. Each worker holds a fraction $\mu = 2/3$ of the dataset. What is the optimal communication load, and how does the cut-set bound rule out a better scheme?

Solution

Apply the formula

$\Delta^*(\mu) = (1 - 2/3)/(3 \cdot 2/3) = (1/3)/2 = 1/6$ .

Cut-set check

The cut between the master and any single worker's ingress must carry at least $H(Y \mid \mathcal{D}_i)$ bits. With $\mu = 2/3$ , each worker has 2/3 of the information already; the remaining 1/3 must flow over the cut. Across three workers, averaging gives at least $(1/3) \cdot (1/2) = 1/6$ . No scheme achieves less.

Achievability

The explicit coded-shuffling construction of §2.3 achieves exactly $1/6$ , so the cut-set bound is tight. The three-worker case is a clean numerical illustration; the general proof is structurally identical.

Roadmap: How the Framework Specializes

The $(\mu, \Delta, K)$ framework recurs throughout the book, augmented with problem-specific parameters:

Part II (Chapters 5–8). Coded computing for matrix multiplication, gradient aggregation, tensor ops. The recovery threshold $K$ becomes the primary object; polynomial codes achieve $K$ that matches an information-theoretic lower bound.
Part III (Chapters 9–12). Secure aggregation and federated learning. A privacy parameter $T$ (number of colluding users) enters the region, and the achievable rate region shrinks in predictable ways. The CCESA and ByzSecAgg CommIT results live here.
Part IV (Chapters 13–15). Private information retrieval. The rate is now the download rate $R_{\text{PIR}} = F / D$ rather than a load, and the Sun–Jafar capacity $C_{\text{PIR}} = (1 + 1/N + \ldots + 1/N^{K-1})^{-1}$ is the analogue of $\Delta^*(\mu)$ .
Part V (Chapters 16–18). Over-the-air computation and wireless FL. The bit-pipe model is replaced by a wireless MAC channel; the communication load becomes a function of transmit power and received MSE.

Each part adds one new dimension to the $(\mu, \Delta, K)$ triple. The information-theoretic formulation developed here is what lets us reason about each dimension rigorously and jointly.

Key Takeaway

A converse gives a scheme its right to exist. Without a matching lower bound, a clever construction is just an upper bound — one might always hope for a better scheme. The cut-set converse of §2.4 makes the coded-shuffling scheme optimal (not merely good), and the same recipe will make every later construction in this book optimal in its own sense. If you remember one thing from this chapter, let it be the cut-set recipe.

Historical Note: The 'CCC' Paper and the Birth of Coded Computing

2015–2018

The result of this chapter — the tight tradeoff $\Delta^*(\mu) = (1-\mu)/(N\mu)$ — is due to Songze Li, Mohammad Ali Maddah-Ali, and A. Salman Avestimehr at USC. The paper was first posted on arXiv in 2015 and later published in the IEEE Transactions on Information Theory in 2018. It is widely credited as the paper that turned "coded computing" into a named research programme, distinct from the older traditions of network coding and distributed-storage coding. The follow-on literature has now extended the framework to matrix multiplication (Yu et al.), gradient descent (Tandon et al., Lee et al.), and federated learning (So et al., Jahani-Nezhad et al.) — with multiple results from the CommIT group at TU Berlin that we tag as commit_contribution blocks in the relevant chapters.

🔧Engineering Note

A Practical Interpretation of the Two Halves

A system architect cares about three quantities:

Can I build it? (Achievability: yes, here is the construction.)
Should I build it? (Converse: no better scheme exists, so your engineering time is well spent optimizing this one.)
How much better is this than what we had? (Gain over the uncoded baseline: $N\mu \cdot$ communication reduction.)

The converse is the answer to question (2). In production system design, knowing that you have reached the information-theoretic floor is what justifies stopping the optimization pass and moving on to the next bottleneck. Without the converse, engineering time leaks into searches for improvements that provably cannot exist.

Practical Constraints

•
Cut-set bounds are tight for single-unicast networks but can be loose in multi-unicast / multicast settings
•
For non-symmetric storage loads the converse is more subtle and often still open
•
Practical coded-shuffling implementations match theory at $\mu \geq 0.1$ in production

Why This Matters: The Converse Changes When the Channel Changes

The cut-set converse in this section assumes noiseless bit-pipes between workers and master. Over a wireless MAC channel, the cut- set bound is replaced by the multiple-access channel's capacity region — an object with genuinely different structure. For analog AirComp (Chapter 16) the "converse" becomes a distortion lower bound rather than a load lower bound, because the receiver is willing to tolerate a controlled amount of noise in the aggregate. The meta-lesson is that each change of channel model forces us to re-derive the converse; the achievability results (coded schemes) transfer more smoothly.

Common Mistake: A Tight Converse Does Not Say the Scheme Is Unique

Mistake:

Conclude that because the cut-set converse is tight, there is a unique optimal scheme.

Correction:

Many different constructions can achieve the same $(\mu, \Delta)$ point — the coded-shuffling construction of §2.3 uses XOR combinations, but one can alternatively use Reed–Solomon or polynomial codes. The converse fixes the rate, not the code. This matters practically because implementation constraints (encoding complexity, numerical stability, compatibility with downstream gradient compression) can favor different constructions at the same operating point.

Quick Check

Which of the following describes the relationship between the coded-shuffling converse of §2.4 and the secure-aggregation converse of Chapter 10?

They are unrelated: different adversary models require different proof techniques.

Chapter 10 uses the identical formula after substituting the storage parameter for the number of colluding users.

Both follow the four-step cut-set recipe (cut, entropy bound, symmetrize, normalize); Chapter 10 specializes it to the honest-but-curious server model.

Coded-shuffling converses do not apply because privacy changes the objective.