Next: 3.3.5 A final look Up: 3.3 On-line reconfiguration Previous: 3.3.3 Output blocks that

### 3.3.4 Input switches are told whether output blocks are erased

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.

Next: 3.3.5 A final look Up: 3.3 On-line reconfiguration Previous: 3.3.3 Output blocks that

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