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.

to .667emto .667em

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.

to .667emto .667em

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.

Mon Jul 22 19:56:03 EDT 1996