Next: 3.3.3 Output blocks that Up: 3.3 On-line reconfiguration Previous: 3.3.1 Blocks with too

### 3.3.2 Input blocks count awake switches in output blocks

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.

Next: 3.3.3 Output blocks that Up: 3.3 On-line reconfiguration Previous: 3.3.1 Blocks with too

Bruce Maggs
Mon Jul 22 19:56:03 EDT 1996