COMPUTATION IN FAULTY STARS

The question of simulating a completely healthy hypercube with a degraded one (one with some faulty processors) has been considered by several authors. We consider the question for the star-graph interconnection network. With suitable assumptions on the fault probability, there is, with high probability, a bounded distance embedding of K(n)xS(n-1) in a degraded S-n, of congestion O(n). By a different method, a congestion O(log(n)) embedding of S-n can be obtained. For the hypercube O(1) congestion has been obtained, but this is open for the star graph. Other results presented include a guaranteed O(n) slowdown simulation if there are sufficiently few faults, and upper and lower bounds for the minimal size of a system of faults rendering faulty every m-substar.