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 th…