Reliable Communication on Cube-Based Multicomputers

We consider a distributed unicasting algorithm for hypercubes with faulty nodes(including disconnected hypercubes)using the safety level concept.The safety level of ach node in an n-dimensional hypercube in an approximated measure of the number and distribution of faulty nodes in the neighborhood and it can be easily calculated through n-1 rounds of information exchange among neighboring nodes.Optimal unicasting between two nodes is guaranteed if the safety level of the source node is no less than the Hamming distance between the source and the destination.The feasibility of an optimal or suboptimal unicasting can be easily determined at the source node by comparing its safety level,together with its neighbors‘ safety levels,with the Hamming distance between the source and the destination.The proposed scheme is also the first attempt to address the unicasting problem in discronnected hypercubes.The safety level concept is also extended to be used in hypercubes with both faulty nodes and links and in generalized hypercubes.

Reliable communication on cube-based multicomputers

We consider a distributed unicasting algorithm for hypercubes with faulty nodes (including disconnected hypercubes) using the safety level concept. The safety level of each node in an n-dimensional hypercube is an approximated measure of the number and distribution of faulty nodes in the neighborhood and it can be easily calculated through n - 1 rounds of information exchange among neighboring nodes. Optimal unicasting between two nodes is guaranteed if the safety level of the source node is no less than the Hamming distance between the source and the destination. The feasibility of an optimal or suboptimal unicasting can be easily determined at the source node by comparing its safety level, together with its neighbors' safety levels, with the Hamming distance between the source and the destination. The proposed scheme is also the first attempt to address the unicasting problem in disconnected hypercubes. The safety level concept is also extended to be used in hypercubes with both faulty nodes and links and in generalized hypercubes.