This paper presents a partially adaptive fault-tolerant routing algorithm for hypercube multicomputers. The algorithm is tolerant to n-1 link and/or node faults for an n-cube. It makes routing decisions adaptively based on local failure information only. It is simple to implement and needs a very small message overhead. A comparison between the algorithm and a popular previous work is given.

Multicast refers to the message delivery from a source node to an arbitrary number of destination nodes in a communication network. The 2D mesh topology has become increasingly popular as interconnection network for multicomputers and distributed systems. Two multicast algorithms are proposed for 2D mesh networks. The computational complexity of the algorithms is analyzed. The performance of the proposed algorithms is evaluated by intensive simulations. A comparison between the proposed algorithms and two existing algorithms is given.

Fault-tolerant communication mechanism for multicomputer systems is an important feature to reliability-critical applications. In this paper, we will present a fault-tolerant routing algorithm that has a better performance than a previous work in the sense that it requires less message overhead and the message header needs to be updated at fewer intermediate nodes. A comparison between the algorithms and a previous work is given.

Multicast algorithms for faulty hypercube multicomputers are discussed. Two types of algorithms are proposed. Type I algorithms have the following features: they are distributed, in the sense that the same algorithm is implemented in all involved nodes and based on local information only; they can always find shortest paths from the source to all destinations whenever such exist; and they are easy to implement in hardware. The algorithms deal with nodes faults only, and they cannot deliver messages to those destinations that can be reached through some longer paths. Type II algorithms deal with both link faults and node faults. They can deliver messages to all reachable destinations if the total number of faults is less than the dimension of the hypercube. However, these algorithms are not easy to implement in hardware.>