next up previous
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 tex2html_wrap_inline1065 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 tex2html_wrap_inline1067 times. If any of an input's tex2html_wrap_inline1069 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 tex2html_wrap_inline1071 steps, each input switch will know if the upper output block has been erased.

lemma248

Proof: If any switch in an upper output block of size tex2html_wrap_inline1077 is marked, then at least tex2html_wrap_inline1079 of them are marked, which for tex2html_wrap_inline1081 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 tex2html_wrap_inline1085 other working switches via paths of length at most tex2html_wrap_inline1087 . These switches have at least tex2html_wrap_inline1089 neighbors in the upper output block, which for tex2html_wrap_inline1091 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 tex2html_wrap_inline1093 fraction of faulty and asleep switches.

lemma251

Proof: If an output block of size tex2html_wrap_inline1099 has more than tex2html_wrap_inline1101 faulty or asleep switches, then every large tree in the corresponding input block has at most tex2html_wrap_inline1103 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 tex2html_wrap_inline1105 time is the same as the propagation algorithm from the Leighton-Maggs algorithm. It consists of tex2html_wrap_inline1107 stages, numbered 1 through tex2html_wrap_inline1111 . At stage i, each switch on level tex2html_wrap_inline1115 counts the number of faulty neighbors it has on level tex2html_wrap_inline1117 . 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 tex2html_wrap_inline1119 , so that each unerased block has at most an tex2html_wrap_inline1121 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 up previous
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