A broadcast overlay runs n-1 links over n nodes: what does that tree structure force you to trade away when the cluster is asked to survive the loss of any single link?
answer
- no slack at the floor
- n-1 is minimal connectivity
- every link is the only route across itself
- two links per node to survive one loss
- n links minimum, and a cycle with them
basics
~20 sTree-ness itself. n-1 links is the floor for reaching everyone, so a tree has no spare route: losing any link splits it in two. Surviving any single loss needs at least n links, hence cycles and duplicates.
solid answer
~40 sThe trade is forced by the count. Any connected graph on `n` nodes needs at least `n-1` links, so a tree sits exactly on the floor and every link is load-bearing: because the only route between the two sides of a link is that link, removing it leaves two components. No clever placement of `n-1` links avoids this — it is a property of the number, not the layout. Surviving the loss of *any* single link means every node needs at least two links, so the total is at least `n`, and a connected graph with `n` links carries a cycle. That cycle is the redundancy and also the cost: nodes on it receive a flooded message twice, so the overlay now needs message identifiers or a hop limit.
go deeper
Hold on to the core fact: a tree uses the fewest links that still reach everyone, so it has nothing spare, and losing one link leaves part of the cluster cut off.
Explain why the floor forces it: with n-1 links the only route between a link's two sides is that link, so its loss splits the graph into exactly two parts, whatever the layout.
Reason about placement. Know that an added link protects only the links on the cycle it creates, and that the split sizes depend on where the lost link sat in the structure.
Own the trade explicitly: redundancy is bought in links and paid for in duplicate suppression and route ambiguity, and single-link tolerance at the n-1 floor is not available at any layout.
## Why n-1 is a floor, not a choice A connected graph on `n` nodes has at least `n-1` links. The argument is short: build the graph up node by node, and every node after the first must arrive attached by at least one link, or it is unreachable. A tree is precisely a connected graph that attains this floor, and every other characterization of a tree is a restatement of sitting on it. Sitting on the floor has an immediate consequence. In a tree, the unique path between the endpoints of a link `uv` *is* the link `uv` — if any other route existed, there would be two paths between `u` and `v`, which a tree forbids. So deleting `uv` leaves `u` and `v` with no route at all, and the overlay falls into exactly two pieces: the part still reachable from `u` and the part still reachable from `v`. This holds for every link in the tree. **There is no arrangement of `n-1` links that behaves better**, because any such arrangement that is connected is a tree, and every tree has this property. ## What tolerance costs, in links To survive the loss of any single link, every node must keep a route after the loss, so every node needs at least two links. Summing degrees gives at least `2n`, and since each link contributes to two nodes, the link count is at least `n`. That bound is attained: a ring of `n` nodes has exactly `n` links, every node at degree two, and cutting any one link turns it into a chain that is still connected. | Links over n nodes | Structure | Single-link tolerance | Delivery | |---|---|---|---| | fewer than n-1 | necessarily split | — | some nodes unreachable | | exactly n-1 | a tree | none, anywhere | every node exactly once | | n-1 + k, partial | tree plus k loops | only on links inside a loop | duplicates on those loops | | n (ring) | one loop over all nodes | every link | every node twice | The third row is the one most real designs land on, and it carries the subtlety worth stating out loud: **extra links buy tolerance only where they are, not globally.** One added link creates one cycle, and only the links on that cycle become survivable; every link hanging off it is still a single point of partition. ## What is actually being traded Three distinct costs appear the moment the structure leaves tree-ness, and they arrive together: 1. **Duplicate delivery.** A message flooded into a cycle travels both ways around it, so every node on the cycle receives it more than once. On a tree this could not happen, which is why a tree-shaped flood needs no bookkeeping at all. 2. **A termination rule.** Because structure no longer guarantees the flood ends, every participant must carry a suppression mechanism — a seen-set keyed by message identifier, or a hop budget. That is new state and new expiry policy on every node. 3. **Ambiguous routes.** With one route per pair, "the distance" and "the next hop" are well defined and need no agreement. With cycles, different nodes can make different, individually reasonable choices, and the system needs a rule to keep them consistent. Against those sits the single benefit: a link loss inside a cycle degrades the topology instead of partitioning it. ## The judgment a lead owns The mathematics narrows the decision to a small set of honest options, and then stops: - **Stay on the floor and make recovery fast.** Keep `n-1` links, accept that any loss splits the cluster, and invest in detecting the split and rebuilding a different tree. The spanning-tree count says a large mesh has an enormous number of alternative trees, so a rebuild has choices. - **Buy tolerance where a split is worst.** Add a small number of links across the cuts whose two sides you least want separated. Tolerance is then local and explicitly chosen, and the duplicate suppression is the price for the whole overlay regardless. - **Leave tree-ness entirely.** Accept `n` or more links and design for duplicates from the start — the ring being the minimal such shape, at the cost of long routes. What the mathematics forbids is the option people most often ask for: single-link tolerance at `n-1` links, achieved by wiring the tree more cleverly. There is no such wiring. Saying that clearly, and then choosing which of the three real options fits, is the whole of the judgment.
- Does adding one link to the tree make the whole overlay tolerant to a single link loss?No. One added link creates one cycle, and only the links on that cycle survive being cut — every link outside it still splits the overlay when lost. Tolerance is a property of where the redundancy sits, not of its existence, which is why the placement question is the real one.
- What is the minimum number of links over n nodes that survives the loss of any single link?Exactly `n`. Every node needs degree at least two, so the degree sum is at least `2n` and the link count at least `n`; a ring attains it. The cost of that minimum is route length, since a ring's longest route grows with the cluster.
- If the tree splits, how large are the two pieces?Exactly the two subtrees hanging off the lost link's endpoints, so the split sizes are determined entirely by where the link sat. A link near a leaf isolates one node; a link near the middle of a balanced tree separates roughly half the cluster. That distribution, not the count of links, is what makes some links worth protecting.
saying these in an interview costs you the question
- Thinks clever placement of n-1 links can survive a loss
- Believes one extra link protects every link in the overlay
- Says a tree keeps a spare route between every pair
- Assumes duplicate delivery can be avoided once cycles exist
- Claims losing a link only isolates that link's two endpoints
- Thinks surviving any single loss costs twice as many links