Optimal fault-tolerant networks with a server
Fast computation through parallel processing and large distributed memory are two important qualities of new multiprocessor computing machines. Various processors of these machines are interconnected through a suitable network. However, a fault in a single processor may drastically reduce the performance rate of these machines. Hence, the designing aspects of fault-tolerant networks have received much attention in recent years. A network N' with n + k processors is called a k-fault-tolerant network with respect to a target network N with n processors if every truncated network of N' with k faulty processors retains the network of N. A processor in a network which is connected to all other processors is called a server. In this paper, we characterize the k-fault-tolerant networks when the target network contains a server. (C) 2000 John Wiley & Sons, Inc.
network server multiprocessor graph interconnection network node failure node fault tolerance spare nodes optimal networks multipartite graph