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

Mon Jul 22 19:56:03 EDT 1996