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.
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.
