Fault tolerance of a class of connecting networks
John Paul Shen, John P. Hayes · 1980
Several proposals have been made for using a class of connecting networks called β-networks in multicomputer systems, such as systems containing large numbers of microprocessors. A β-network is a network of 2 × 2 crossbar switches called β-elements. This paper presents an analysis of the fault tolerance of β-networks intended for multicomputer applications. A fault model is used which allows β-elements to be stuck in either of their two normal states. A new connectivity property called dynamic full access (DFA) is introduced which serves as the criterion for fault tolerance. A β-network is said to have the DFA property if each of its inputs can be connected to any of its outputs in a finite number of passes through the network. A fault is called critical if it destroys the DFA property. Two graph-theoretical characterizations of the critical faults of a β-network are presented. It is shown that there is a one-to-one correspondence between minimal critical faults and the cutsets of the circuit adjacency graphs derived from the β-network. It is further shown that a fault is critical if and only if it is incompatible with all Eulerian circuits associated with the β-network. Some applications of the theory are discussed.