After the large trees have marked switches in the output blocks that
are not to be erased, the rest of the input switches that are awake
must be informed. First, every working input switch (awake or asleep)
queries its 
upper output neighbors to determine if they are marked.
If any of them are, then the input switch colors itself. Then
the following coloring step is repeated 
times. If
any of an input's 
neighbors in the input block are colored,
then the switch colors itself. (The same algorithm is then applied to
the lower output block.) The following lemma shows that after
steps, each input switch will know if the upper output block
has been erased.
Proof:
If any switch in an upper output block of size 
is marked, then
at least 
of them are
marked, which for 
is more than
half of the switches in the block. By Lemma 3.4,
each input switch in a block of size M that is awake can reach at
least 
other working switches via paths of
length at most 
. These switches have at least 
neighbors in the upper output block, which for
is more than half of the
switches in the block. If more than half of the switches in the upper
output block are marked, and more than half of the switches are
neighbors, then at least one neighbor is marked.
The last step before fault propagation is to declare any switch that
is asleep to be faulty. The following lemma shows that the blocks
that are not erased contain at most a 
fraction of faulty and asleep switches.
Proof:
If an output block of size 
has more than
faulty or asleep switches, then every
large tree in the corresponding input block has at most
neighbors in the output block that
are awake, and none of those neighbors will be marked.
The algorithm for propagating faults from the outputs to the inputs in
time is the same as the propagation algorithm from the
Leighton-Maggs algorithm. It consists of 
stages, numbered
1 through 
. At stage i, each switch on level 
counts the number of faulty neighbors it has on level 
. If more
than half of its upper or lower outputs lead to faulty switches that
have not been erased, then the switch declares itself to be faulty.
Otherwise it does nothing. We will choose 
, so that each unerased block has at most an 
fraction of faulty switches. As a consequence, we can apply
Lemmas 3.1 and 3.2 to bound
the number of faults that propagate to the inputs.