Distributing a File to N Nodes — Fan-Out vs. Pipelined Chain

The constraint that makes this interesting: every node — including the one that starts with the file — has a single NIC capped at B up and B down (say 1 MB/s each direction). No magic backbone, no multicast-capable switch. Given that, how do you get the file to N−1 other nodes fastest?

Pipelined chain (bucket brigade), not fan-out. Fan-out forces every one of the (N−1) copies through the same single uplink — the source's — so it costs (N−1)·S/B no matter how you slice the connections. A chain that relays the file node-to-node, split into small chunks so every hop is pipelined, spreads those same (N−1) copies across (N−1) different uplinks running concurrently. Wall-clock collapses toward S/B — the time to push the file out once — almost independent of N. The catch: you only get that if you chunk and pipeline. A naive whole-file relay (no pipelining) is exactly as slow as fan-out.

1. The setup

One node (S0) holds a file of size S. There are R other nodes that need a full copy (N = R + 1 nodes total). Every node's NIC is symmetric and independent in each direction: B up, B down — so a node can receive on one flow and transmit on another at the same time, but it cannot exceed B in either direction, no matter how many flows share it. We'll run the numbers with S = 1000 MB, B = 1 MB/s, R = 10 receivers — clean numbers, real gap between strategies.

2. Fan-out (star) — the trap

Splitting the connections doesn't split the bottleneck: S0's NIC still has to push out (N−1) full copies, at a combined rate no higher than B.

Whether S0 opens all R connections at once (each getting B/R) or serves them one at a time at full B, the total bytes leaving S0's single uplink is (N−1)·S, capped at rate B. Either way:

Fan-out time

T_fanout = R · S / B → with our numbers: 10 · 1000 / 1 = 10,000s ≈ 2.8 hours

3. Naive chain — the same trap, wearing a different hat

The obvious "fix" — relay the file S0→R1→R2→…→R10 instead of fanning out — looks smarter, but if each hop waits for the whole file to land before forwarding it, you've just serialized the same (N−1) transfers instead of parallelizing them:

Naive (unpipelined) chain time

T_chain_naive = R · S / B = 10,000s — identical to fan-out. No win.

This is the part people miss: relaying isn't the win by itself. The win comes from chunking + pipelining, which lets the R links run concurrently instead of one after another.

4. Pipelined chain (bucket brigade) — the actual answer

Split the file into k chunks of size S/k. Each node forwards chunk i to its downstream neighbor the instant it has fully received it — while simultaneously still receiving chunk i+1 from upstream (this is exactly why the NIC needs independent up and down capacity). Once the pipeline is full, every one of the R links is busy carrying a different chunk at the same wall-clock moment.

Diagonal bands = chunks moving hop-by-hop. At the dashed instant, five different links each carry a different chunk simultaneously — that concurrency is the whole trick. Fan-out and the naive chain never get this: they only ever use one link at a time.

Time for the last chunk to clear the pipeline: it waits for the source to finish pushing out the previous (k−1) chunks — that's the source's own uplink, still one flow — then it takes R more hops to reach the far end:

Pipelined chain time (k chunks)

T(k) = (S/B) · (1 + (R−1)/k)

As k → ∞, T(k) → S/B — the time to push the file out once. R barely matters anymore.

5. Numbers side by side

Strategy	Formula	S=1000MB, B=1MB/s, R=10	vs. ideal floor (S/B=1000s)
Fan-out	`R·S/B`	10,000s (2.8h)	10×
Naive chain (k=1)	`(S/B)(1+(R-1)/1)`	10,000s (2.8h)	10×
Pipelined chain, k=10	`(S/B)(1+9/10)`	1,900s (32min)	1.9×
Pipelined chain, k=100	`(S/B)(1+9/100)`	1,090s (18min)	1.09×
Pipelined chain, k=1000	`(S/B)(1+9/1000)`	1,009s (16.8min)	1.009×
Ideal floor	`S/B`	1,000s (16.7min)	1×

Finer chunking is free speed up to the point where per-chunk overhead (packet/frame headers, RTT, TCP slow-start, ACKs) stops being negligible next to the chunk's own transfer time. In practice you pick the largest chunk count where that overhead is still small — not k→∞ literally.

6. Why chain wins — the one-sentence reason

Aggregate bandwidth, not total bytes

Both strategies move the same (N−1)·S total bytes — that part is fixed by the problem. The difference is how many distinct NICs carry those bytes at the same instant. Fan-out funnels everything through one node's uplink (effective aggregate throughput: B). A pipelined chain spreads the load across R different uplinks running concurrently (effective aggregate throughput: R·B) — full utilization of every link in the spanning tree at once. That's the entire trick, and it's why "relay" alone (§3) doesn't help without chunking: without pipelining, only one link is ever active, so aggregate throughput is still just B.

This isn't just "10× slower" — that 10× was a coincidence of picking R=10 in the worked example. The exact, provable result is T_fanout / T_pipelined(k) → R as k → ∞: fan-out is R times slower, whatever R happens to be. Double your fleet, double the penalty — linearly, forever. The two charts below make that literal.

Same worked example as §5, generalized across R. Fan-out's cost is unbounded in the fleet size; the pipelined chain barely notices R at all.

A straight diagonal, not a curve — the slowdown is exactly proportional to R at the ideal (k→∞) limit. At any finite k it's slightly under R (9.91× rather than 10× at k=1000 — see the correction term in §4), but the line R is the theorem you'd defend on a whiteboard.

7. When does a tree, or fan-out, actually become correct?

A tree doesn't help here, given the constraint. If an internal node has to serve 2 children through the same single NIC, that NIC's capacity B splits between them — you don't get two full-rate branches for free. A tree only pays off when internal nodes have spare capacity beyond one downstream flow (multi-homed boxes, or a beefier source), in which case it trades a small bandwidth cost for shallower depth (log N hops instead of N) and smaller failure blast radius — a dead link only takes out its subtree, not "everyone after it" like a chain.
Fan-out is correct when the source isn't NIC-bound like the clients are — classic CDN origin: the source's pipe is provisioned far above R·B, so it genuinely can push a full-rate copy to every receiver in parallel. The math in §2 assumed the source has the same single-NIC cap as everyone else; relax that and the answer flips.
Chain's real weakness is fragility and tail latency — one dead node or slow link stalls everyone downstream of it, and the farthest node always waits for the pipeline-fill term. At large R, real systems hedge with a few parallel chains or a randomized mesh rather than one long line (next section).

8. What real systems actually do

System	Shape	Why
BitTorrent	many parallel, randomized bucket-brigades (rarest-first piece selection)	approximates full use of aggregate peer upload capacity; no single peer becomes the sequential bottleneck; tolerates churn
MPI collective `Bcast`	pipelined chain/ring for large messages; binary tree for small ones	large messages are bandwidth-bound → pipeline wins (§4); small messages are latency-bound → tree's log-depth wins instead
Chain Replication	strict chain, writes flow head→tail	same bandwidth-pipelining argument, plus the chain order gives strong consistency for free
Uber Kraken / P2P image & model distribution	torrent-style swarm across the fleet	pushing multi-GB container/checkpoint images to thousands of hosts from one registry is the fan-out trap at datacenter scale
CDN origin push (contrast case)	direct fan-out from origin	origin is deliberately over-provisioned vs. any single edge box — the source isn't the bottleneck, so §7's exception applies

Say out loud: "With every node NIC-capped the same way, fan-out forces all (N−1) copies through one uplink — R·S/B. A chain only helps once you chunk and pipeline it, so R links run concurrently instead of one — time collapses toward S/B, independent of N. Trees cost the same per-branch bandwidth unless nodes have spare capacity; they buy you shallower depth and smaller blast radius instead. Fan-out is only right again if the source itself isn't bandwidth-bound like the receivers are — the CDN-origin case."