Conditional fault-diameter of torus networks

Abstract EN

We obtain the conditional fault-diameter of the square torus Interconnection network under the condition of forbidden faulty sets (i.e.

assuming that each non-faulty processor has at least one non-faulty neighbor).

We show that under this Condition, the square torus, whose connectivity is 4, can tolerate up to 5 faulty nodes without becoming disconnected.

The conditional node connectivity is, therefore, 6.

We also show that the conditional fault-diameter of the square torus is equal to the fault-free Diameter plus two.

With this result the torus joins a group of interconnection networks (including the hypercube and the star-graph) whose conditional fault-diameter has been shown to be only two units over the fault-free diameter.

Two fault-tolerant routing algorithms are discussed based on the proposed vertex disjoint paths construction.