Next: 3.3.2 Input blocks count Up: 3.3 On-line reconfiguration Previous: 3.3 On-line reconfiguration

### 3.3.1 Blocks with too many faults fall asleep

The erasure algorithm begins by repeating the following basic step times, where , and . Initially, every working switch in the network is awake. At each basic step, each switch that is awake examines its neighbors within the same block, and falls asleep if more than of them are faulty or asleep. The following lemma shows that if there were not too many faults to begin with, then few working switches fall asleep.

Proof: The proof is by induction on the number of basic steps. The base case is trivial, since initially no working switches are asleep. Now let be the set of working switches that are asleep at the end of step i. Suppose that . Then

since the switches in have at least neighbors, and each switch in has at most neighbors that are not asleep or faulty. Since by induction, and , we have a contradiction. Thus . As a consequence, the switches in have at least neighbors. Thus,

Now suppose that . Since by induction, we have a contradiction.

to .667emto .667em

The next lemma shows that if any working switch is awake after step , then it is connected to many nearby working switches.

Proof: If r is still awake at the end of step i, then r must have had at least neighbors that were awake at the end of step i-1. In turn, these neighbors must have had at least neighbors that were awake at the end of step i-2, provided that . Otherwise, these switches had at least neighbors that were awake. In general, r can reach a set of switches that were awake at the end of step i-j. Furthermore, there is a path of length j from r to any switch in this set that passes only through working switches. Choosing j such that , i.e.,

and choosing completes the proof.

to .667emto .667em

Next: 3.3.2 Input blocks count Up: 3.3 On-line reconfiguration Previous: 3.3 On-line reconfiguration

Bruce Maggs
Mon Jul 22 19:56:03 EDT 1996