A COHERENT MODEL FOR RELIABILITY OF MULTIPROCESSOR NETWORKS

Graph G has perfectly reliable nodes and edges that are subject to sto chastic failure. The network reliability R is the probability that the surviving edges induce a spanning connected subgraph of G. Analysis p roblems concern determining efficient algorithms to calculate R, which is known to be NP-hard for general graphs. Synthesis problems concern determining graphs that are, according to some definition, the most r eliable in the class of all graphs having a given number of edges & no des. In applications where the edges are perfectly reliable and the no des are subject to failure, another measure (residual node connectedne ss reliability) is defined as the probability that the surviving nodes induce a connected subgraph of G. Referring to such a subset as an op erating state, the measure is not coherent because a superset of an op erating state need not be an operating state. This paper proposes a ne w definition of network reliability that handles the case of node fail ures; it is coherent. We determine many of its properties, and present several analysis & synthesis results.