Lesson 18: Fault Tolerance & Redundancy

Warm-Up

Your school has two exits. Fire code demands it — not because one exit doesn't work, but because one exit might not work, exactly when it matters.

Now a network version: four computers in a line, A—B—C—D. If the B—C cable is cut, A and B are marooned from C and D. One failure, network halved. Add a single extra cable from A to D, making a ring — now cut any one cable and every computer can still reach every other, the long way around.

That extra cable is redundancy: a connection you don't need until you desperately do. The Internet is redundancy at planetary scale — and that's not an accident of growth but its founding design goal: a network that keeps working when pieces fail.

Core Concept

Fault tolerance and redundancy

A system is fault-tolerant when it can continue functioning despite the failure of some components. The Internet achieves this through redundancy: multiple physical paths between devices, more connections than the bare minimum needed.

The CED's chain of claims:

1. Redundant routing exists by design in the Internet.
2. When one path fails (cut cable, dead router, power outage), data is rerouted along surviving paths — often automatically and invisibly.
3. Redundancy means the network usually keeps working even as parts fail — the failure must sever every path between two points to disconnect them.
4. Redundancy has a cost — extra cables, routers, and complexity — accepted because reliability is worth it. (Trade-off framing, as always.)

Vocabulary precision: fault tolerance is the property (keeps working through failures); redundancy is the mechanism (extra paths providing alternatives). An exam answer defining fault tolerance as "having many connections" swaps the property for the mechanism — close, but the tighter answer distinguishes them.

Reading network diagrams

Exam diagrams show devices (lettered circles/boxes) and connections (lines). Two question types:

Type 1: Count the routes. "How many distinct paths exist from A to D that don't revisit a device?" Method: enumerate systematically — list every neighbor of A, extend each partial path one hop at a time, never revisiting a node, count the completions. Write them out; don't eyeball.

Type 2: Survive the failure. "Connection X–Y fails. Can A still reach D?" Method: strike the failed link off the diagram, then check whether any path remains (one is enough). Related: "which single failure would disconnect A from D?" — look for a link (or device) that every A→D path uses. If every route crosses the same bridge, that bridge is the vulnerability; if no single link is shared by all paths, no single link failure can disconnect them.

[DIAGRAM: Five devices. A connects to B and C. B connects to A, C, and D.
C connects to A, B, and E. D connects to B and E. E connects to C and D.
Layout: A on the left; B upper middle; C lower middle; D upper right; E lower right.]

Routes from A to D (no revisits): A-B-D · A-B-C-E-D · A-C-B-D · A-C-E-D — four routes. Now fail the B–D link: surviving A→D routes are A-B-C-E-D and A-C-E-D — still connected ✓. Fail device E and link B–D together: A-B-D ✗ (link gone), anything via E ✗ — disconnected. The mechanics are exactly this: strike, re-enumerate, conclude.

Why this matters beyond diagrams

The design insight the exam wants you to articulate: the Internet was built assuming failures are normal events — hardware breaks, lines cut, regions lose power — so the network's job is to route around damage, not to prevent it. Combined with Lesson 17: independent packet routing is what lets traffic instantly use surviving paths; nobody re-plans routes centrally when a cable dies. Redundancy provides the spare paths; dynamic routing exploits them.

One more CED phrase: when a system's redundancy is exhausted — enough failures that no path remains — the network partitions (splits into isolated islands). Fault tolerance raises the failure count needed; it can't make disconnection impossible.

Worked Examples

Example 1 (easy): Definitional

Problem: A hospital's network keeps operating when a router fails because traffic automatically flows through alternate routers. Which terms describe (i) the property and (ii) the mechanism?

Solution: (i) The network is fault-tolerant — it functions despite component failure. (ii) The mechanism is redundancy — alternate routers/paths available for rerouting.

Interpretation: Property vs. mechanism, stated separately — the precision the best answer choice will have.

Example 2 (medium): Route counting

Problem: Using the five-device diagram from section (b), how many routes from B to E avoid revisiting any device?

Strategy: Systematic enumeration from B's neighbors (A, C, D).

Solution: Extend every partial path; cross out dead ends: - Via A: B-A-C-E ✓ (A's only other neighbor is C; C reaches E) - Via C: B-C-E ✓ · B-C-A-... ✗ dead end (A's remaining neighbor B is already visited) - Via D: B-D-E ✓

Total: 3 routes (B-C-E, B-A-C-E, B-D-E), with one dead end honestly explored and crossed out.

Interpretation: Dead ends are part of honest enumeration — write them and cross them out. The systematic sweep (extend every partial path, kill the dead ones) is slower and correct; eyeballing finds either too few or too many.

Example 3 (medium): Single point of failure

Problem: A network: P—Q, Q—R, Q—S, R—T, S—T. Which single DEVICE failure disconnects P from T?

Solution: P's only connection is Q — every P→T path starts P-Q. If Q fails, P is isolated entirely. (Check the others: R fails → P-Q-S-T survives; S fails → P-Q-R-T survives; so only Q.) Q is the single point of failure for P.

Interpretation: A device with only one link (P here) makes its neighbor a chokepoint. Scan the diagram for one-link devices first — their neighbors are always failure-question answers.

Example 4 (AP-style): The design claim

Problem: Which statement best explains why the Internet continues functioning when a major undersea cable is severed?

(A) The Internet Protocol prevents cables from failing (B) Redundant connections provide alternative paths, and routing adapts to use them (C) A central authority quickly assigns all traffic a new path (D) Traffic waits until the cable is repaired

Solution: (B) — redundancy (spare paths) + adaptive routing (using them). (A) claims failure-prevention, which no protocol does; (C) resurrects the central controller (always wrong — Lesson 17); (D) describes a system with no fault tolerance at all.

Interpretation: The correct fault-tolerance answer always has two parts: alternative paths exist and routing uses them. Missing either half is a distractor.

Common Mistakes

1. Confusing fault tolerance (property) with redundancy (mechanism). Redundancy is how; fault tolerance is what you get.
2. Sloppy route counting. Revisiting a device (A-B-C-B-D doesn't count), missing longer valid routes, or double-counting reversals. Enumerate in writing, extend systematically, cross out dead ends.
3. Thinking one failure can't disconnect anything. It can — when every path shares that link or device (Example 3). Redundancy between two specific points is what protects them, and some points don't have it.
4. "The Internet reroutes because someone re-plans the routes." No one re-plans; routers adapt using surviving links (decentralization, again). Central-coordinator answers are always wrong.
5. Forgetting redundancy's cost. More links = more hardware and complexity. The exam's trade-off answer acknowledges the cost is accepted for reliability — "redundancy is free" is a wrong choice.

Practice Problems

Problems 4–8 use this network:

[DIAGRAM: Six devices. A—B, A—C, B—C, B—D, C—E, D—E, D—F, E—F.
Layout: A far left; B upper middle-left; C lower middle-left; D upper middle-right;
E lower middle-right; F far right.]

12 (short response). Using the six-device diagram: a contractor proposes removing the C—E connection to save money. State one specific pair of devices whose connectivity would survive (with an example path) and explain the general cost of the removal in fault-tolerance terms.

Create PT Connection

No network diagrams in your PT — but fault-tolerance thinking maps directly onto defensive programming, which the written responses reward. Redundancy's lesson is plan for failure as a routine event: what does your program do when the list is empty, the input is invalid, the index is out of range? A program that checks LENGTH(entries) = 0 before dividing is applying the same design philosophy as a network with a spare path — the failure case was anticipated, so the system degrades gracefully instead of collapsing.

Mini practice (WR 2(b) flavor): "Describe how your program responds to an input that could cause an error." Model: If the user submits an empty list, my average procedure would divide by zero — a run-time error. I added a selection statement that returns a "no data" message when LENGTH(scores) = 0, so the program continues functioning despite the bad input — the software equivalent of routing around a failure.