We provide a new algorithm for assessing network reliability (and performability, the more general case). As in some well-known approaches, the algorithm identifies most probable states in iterations and provides converging upper and lower bounds after each iteration. The algorithm distinguishes itself by providing superior bounds after the same number of iterations. In some instances, the algorithm can even find the exact reliability in a small number of iterations. The time complexity for each iteration, excluding the time for computing the performance value of a generated state, is only O(n) (where n is the number of components), which is the same as any existing optimal algorithm for enumerating most probable states. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

An efficient algorithm to construct testing procedures for optimally identifying a single defective unit in a series system is presented. A series system such as a local loop of telephone networks is modeled as a sequence of units. The costs incurred by the testing process are general; traveling costs and testing costs are taken into consideration. Although the model assumes that only one defective unit exists in the system, the testing tree still leads to the isolation of a defective unit if two or more exist. This occurs because whenever one proceeds to a subtree, a defective unit corresponding to a vertex within that subtree is certain to exist.>

A general multimode model for jointly assessing the performance and reliability (performability) of a communication network is considered. The performability is computed by averaging the performance over the most probable network states. An efficient algorithm, superior to all previous algorithms in both speed and flexibility, is proposed to enumerate the most probable network states. The algorithm keeps generating the network states one by one, in order of decreasing probability, until some stopping rule (if specified) is met.>

The problem of diagnosis of soft failures at the system level in large and fully distributed networks of processors (or units) is considered. A system model in which each of the network's units is assumed to possess the ability to test (or evaluate) certain other units for the presence of failures is employed. Using this model and assuming that the total number of faulty units does not exceed a given bound, a distributed algorithm is presented which allows all the fault-free units to independently converge to correct and consistent diagnoses of the system status. This algorithm is also shown to be applicable to bounded fault situations where both units and communication links can be faulty.>

Hybrid fault diagnosability in distributed multiprocessor systems is considered for the case in which, in addition to units being faulty, communication links among units can also be faulty. A hybrid fault situation is a (bounded) combination of hard and soft failing units. A novel hybrid fault diagnosability, denoted (t/t/sub s/-unit: sigma -link)-diagnosability is introduced (a total of t or fewer units can be faulty with at most t/sub s/ of them soft-failing; sigma is the number of incorrect test outcomes caused by unreliable links)., This diagnosability is compatible with the previously known t/t/sub s/-diagnosability and can additionally tolerate up to sigma incorrect test outcomes to give always-correct diagnosis for any hybrid-fault (HF)-compatible syndrome from a hybrid fault situation. It is shown that an O( mod E mod ) algorithm, proposed originally by the authors (see ibid., vol.C-35, p.503-10, 1986) for faulty unit identification in t/sub s/-diagnosable systems, can be used to analyze a syndrome from a (t/sub s/-unit sigma -link)-diagnosable system efficiently without any preclassification of the syndrome in terms of HF-compatibility. It is shown that this algorithm not only identifies all the faulty units associated with an HF-compatible syndrome but also produces nonempty, always-correct diagnosis for many HF-incompatible syndromes.>

A hybrid fault situation in a PMC system is a (bounded) combination of permanently and intermittently faulty units. Mallela and Masson [8] have given a general characterization of PMC systems for the diagnosis of hybrid fault situations. For this so-called th/thidiagnosability, when a syndrome takes on a form that is compatible with an allowable permanent fault situation, diagnosis can always be performed that is correct but perhaps incomplete. However, for general hybrid fault situations, syndromes that are compatible with permanent fault situations are exceedingly rare. Hence, th/thidiagnosability makes very limited use of the set of all syndromes that can result from application(s) of the test set. In this paper, a new, broader type of diagnosability for hybrid fault situations is defined and fully characterized. With this new type of diagnosability, at least all the permanently faulty units in a hybrid fault situation can be diagnosed from any syndrome that can result from an application of the test set. Thus, the usefulness of the syndrome space is dramatically increased. Special forms of this diagnosability are presented. Finally, relationships to other diagnosabilities are described.

Using the PMC model of a multiprocessor system, a new, general quality of hybrid fitult (combinations of hard anid soft failing units) diagnosability is characterized which encompasses previously known results as well as provides a major extension. This new diagnosability, called t/ts/τ-diagnosability, serves as a measure of the extent to which collections of test results, called syndromes, contain information relative to faulty unit identification for various testing assignments. By analyzing a system's test assignment over tahges of the parameter values t, ts, and τ, the spectrum of diagnosis quality achievable in that system can be established. Fundamental interrelationships among these parameters are developed. Optimal designs of t/ts/τ-diagnosable systems are presented. The main result of this correspondence can be viewed as a master fault diagnosability characterization which from the perspective of usefulness of the syndrome space for correct diagnosis both unifies and expands the domain of hybrid fault diagnosabilities.

In this paper, a new approach to identifying faulty units in ti-diagnosable systems is described. This approach exploits special properties of the highly structured ti-diagnosable systems to produce a faulty unit identification algorithm which is shown to be of time complexity O(|E|) where |E| corresponds to the number of tests in the system. The diagnosis quality of the algorithm is as follows: 1) if the algorithm identifies a unit as faulty, it is always correct; 2) if the collection of test outcomes takes on a form that is compatible with a permanent fault situation, the algorithm identifies all of the corresponding faulty units; and 3) the algorithm identifies at least one faulty unit over collections of test outcomes significantly larger than those that are compatible with permanent fault situations.

Consider a classical PMC system composed of n units [1] where it is assumed that at most t1 of these units are faulty. Such a system is said to be t1/t1-diagnosable [3] if, given any complete collection of test results, the set of faulty units can be isolated to within a set of at most t1 units. This paper exposes some new, important properties of general t1/t1-diagnosable systems to present an O(n2.5) algorithm by which all the faulty units except at most one can be correctly identified and all the faulty units can be isolated to within a set of t1 or fewer units in which at most one can possibly be fault free.

In this paper, a new class of diagnosable systems, called tp-self-implicating systems, which is a special case of the well-known tp-diagnosable systems introduced by Preparata et al. [1], is described. If there are no more than tp faulty units and the faults are assumed to be permanent, then the faulty units in a tp-self-implicating system can always be identified using at least one of two straight forward criteria associated with test outcomes. In each case, the given faulty unit in effect implicates itself as faulty. Necessary and sufficient conditions are given on the structures of PMC models for self-implication. Finally, an algorithm for identifying the set of faulty units in a tp-self-implicating system is given which is linear in the number of tests in the system, rendering it more efficient than the most efficient known algorithm for the general class of tp-diagnosable systems.