Now the erasure algorithm must determine, for each splitter, whether its output blocks contain too many faults, and it must inform each input switch if either of the two output blocks must be erased.
In order to count the number of faulty switches in the output blocks,
the switches in each input block organize themselves into trees.
Suppose that some switch r in a block of size M remains awake for
steps. We call r a ruler. Each ruler attempts to
form a depth- 
breadth-first spanning tree of the working
switches that it can reach with itself as the root. If r were the
only ruler, then the number of steps required to form the spanning
tree would be at most 
. However, since each ruler
simultaneously attempts to form a spanning tree, there will be
conflicts when the trees overlap. To resolve these conflicts, we will
assume that each switch in the block possesses a distinct label. Each
time a switch is added to a spanning tree, it is given the label of
the spanning tree's ruler. If several trees attempt to add the same
switch, then the one with the smallest label succeeds, even if the
switch must be removed from another tree. Since the growth of the
spanning tree with the smallest label is unimpeded by the other
spanning trees, after 
steps, it will contain at least
switches.
Next, in 
steps, each ruler counts the number of switches in
its spanning tree. If the total is at least 
, then it broadcasts a message to the switches in the tree, telling
them that they belong to a large tree.
Now each large tree makes an underestimate of the number of
switches that are awake in the upper and lower output blocks. In
order to perform this task, a third set of edges is added to the
graph. For each input switch, 
edges are added to switches in
both the upper and lower output blocks of outputs at the next level.
The edges are inserted at random so that each set of 
switches in a block of size M has at least 
neighbors
in both the upper and lower blocks, where 
.
These edges increase the VLSI layout area of the network by at most a
constant factor. We will choose 
so that a tree of size 
will have at least
neighbors in each output block, and
we will choose 
to be large so that 
. In 
steps, each
large tree sums up the number of different switches in the upper
output block that are awake and have a neighbor in the tree. It then
does the same for the lower output block.