This section presents an algorithm for determining which switches to
remove from the network in 
time. The algorithm is
on-line in the sense that the computation is performed entirely by
the switches, without the aid of any off-line computation. As in
Section 3.2, the reconfiguration of the network
consists of two parts. First, each splitter must determine if the
number of faults in its input block exceeds an 
fraction,
and, if so, then it must erase itself. This part is difficult because
each splitter must count its own faults and distribute the count to
its working switches, even though the splitter itself may contain many
faults. Second, faults are propagated from the outputs of the network
towards the inputs. A switch is declared faulty if more than 
of
its upper or lower output edges lead to switches that are faulty, but
not erased. After erasure and fault propagation, all of the remaining
faulty switches are erased.
The erasure part consists of two tasks. First, we must identify those
blocks that contain too many faults and must be erased. Then for each
splitter, each input switch must be told whether either of the two
output blocks in the splitter have been erased. To help with these
tasks, we add some edges to the network. In particular, each switch
is connected in a random fashion to 
other switches in the same
block. These edges will be used solely for the purpose of counting,
and not for routing. They increase the VLSI layout area of the
network by at most a constant factor. For sufficiently small, but
fixed, 
, with probability close to 1, every set S of
switches in a block of size M will have at least
neighbors [7, 12]. We will choose
to be small so that 
will be close to 
.