Connectivity and fault tolerance of multiple-bus systems

We study multiple-bus computer systems that are fault tolerant in the sense that processors remain connected in the presence of component faults such as faulty processors and buses, and faulty links between processors and buses which may represent partial bus failures. We propose several graph-theoretic models for this purpose. A processor-bus-link (PBL) graph is introduced to represent a multiple-bus system component adjacency graphs derived from the PBL graph exhibit the connectivity of the system´s components, We then transform the problem of analyzing fault tolerance of multiple-bus systems into the simpler problem of finding the node connectivity of component adjacency graphs. Minimum critical fault sets, each of which is a minimum set of faulty components whose removal disconnects processors, are also characterized.<>