Finding Fault-Tolerant Solutions for Complete Bipartite Networks

A major goal in designing multicomputer networks is to include fault tolerance capability so that the system can continue to operate correctly after losing some of its basic components. This is usually achieved by introducing redundancy, i.e, Adding spare processors and links to the network. However, due to the limitation on the number of links adjacent to a node in VLSI design, it is important to minimize the node-degree of the overall network. We apply this strategy to the problem of designing (optimal) fault-tolerant solutions of complete bipartite networks. No polynomial solution is known for this problem, except for the case of handling a single node failure. We generalize this result to the case of tolerating two node failures.