next up previous
Next: 3.3.4 Input switches are Up: 3.3 On-line reconfiguration Previous: 3.3.2 Input blocks count

3.3.3 Output blocks that are not to be erased are marked

If any large tree in the input block counts more than tex2html_wrap_inline1043 switches that are awake in an output block of size tex2html_wrap_inline1045 then it marks all of those switches. As we shall see, a block will be erased unless it contains a marked switch, in which case it will not be erased. The following lemma bounds the number of network outputs that are erased.


Proof: If an output block of size tex2html_wrap_inline1051 has fewer than tex2html_wrap_inline1053 faults, then by Lemma 3.3, after tex2html_wrap_inline1055 steps it will have at most tex2html_wrap_inline1057 faulty and asleep switches. Since the switches in each large tree have at least tex2html_wrap_inline1059 neighbors in each output block, at least tex2html_wrap_inline1061 of those neighbors must be awake. These neighbors will all be marked and the block will not be erased. Thus, if an output block is erased, then it must have had at least an tex2html_wrap_inline1063 fraction of faulty switches to begin with.

to .667emto .667em

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