The SourceDoubls algorithm efficiently solves for singletons and doubletons of a digraph reliability model (defined below). In the case of a complex system of hardware and/or software represented by a correspondingly complex digraph reliability model, it can take as long as days to compute the solution by older, matrix-based methods. In contrast, SourceDoubls finds the solution in minutes, opening the possibility of using a digraph model for real-time monitoring and diagnosis of the system.

Figure 1. This Is a Digraph (Directed-Graph) Representation of reliability of a cooling system. Each node (circle) represents a failure in a component of the system. Each directed edge represents both a flow of coolant and a path of propagation of failure. The vertical bar represents an AND gate, which is used here because both the primary and backup pumps must fail in order for the cooling unit to fail for lack of coolant.

A digraph model (see Figure 1) is a graphical combinatorial failure-space model of a system, comprising nodes and AND gates connected by directed edges. Each node represents a piece of hardware or software, a mode of operation, a human action, or other component or aspect of the system wherein a failure could occur. Each directed edge represents a physical connection and/or functional dependence through which the occurrence of a failure can flow through the system to cause failure at another node. If a node is marked "failed," then the failure is deemed to propagate along the output edge(s) of the node to any connected node(s). The model can include directed loops that represent cycles. The model can be derived fairly straightforwardly from a schematic diagram of the system augmented by knowledge about the design of the system and modes of failure of components.

A common operation performed on a digraph model is the calculation of single failures and pairs of failures that could cause a target failure event to occur. A single failure that causes the target failure event is called a "singleton" of that event. Two failures that combine (as represented by use of an AND gate) to cause a target failure event are said to constitute a "doubleton" of that event. Finding singletons and doubletons for a digraph model is useful for finding weak links in the system and for quantitative estimation of the reliability of the system. Singleton and doubleton solutions can also be used in diagnosing the system because they indicate possible causes of failure events.

Figure 2. Nodes and AND Gates are represented by programming objects that contain data on identity, condition (failed or not failed), and connectivity.

The SourceDoubls algorithm solves for the singletons and doubletons of all the nodes in a digraph model of a system by use of object-oriented programming concepts (see Figure 2). Each node, AND gate, singleton, or doubleton is stored as an object in computer memory. Each node or AND-gate object includes a number of slots to represent such data as the identity of the object, its input(s) and output(s), and its singleton(s) and doubleton(s). One of the slots is the mark slot, which contains a datum (1 or 0) that indicates whether a failure has or has not propagated to the node or AND gate. The input and output slots contain lists of pointers to nodes and AND gates directly connected to a given node or AND gate. The singletons slot contains information on the identities of the nodes associated with singletons of the given node, while the doubletons slot contains a list of pointers to doubleton objects. A doubleton object contains slots that point to the two nodes (objects) that are members of the doubleton, plus flags that indicate whether information on the doubleton has been printed or processed yet.

SourceDoubls finds singletons and doubletons in source operations:

  • In the case of a singleton, a node of interest is marked as failed and the mark is propagated through the directed edges of the digraph to determine which other nodes can be expected to fail as a result. The node of interest is thus determined to be a singleton of each of the other failed nodes. The singleton calculations are completed before starting the doubleton calculations.
  • The doubletons of a given node are found by searching for the doubletons for all the AND gates directly upstream of the node. This is accomplished in a limited source operation on each AND gate in the digraph. In this operation, the mark is allowed to travel only to nodes and not through AND gates. After this operation, the AND gate is added to the list of upstream AND gates of each node that the mark reached in the operation.

The foregoing description is simplified for the sake of brevity. The algorithm also includes provisions for finding hidden doubletons, increasing computational efficiency by avoiding redundant calculations, and avoiding infinite computational loops when cycles are encountered.

This work was done by D. L. Iverson and F. A. Patterson-Hine of Ames Research Center. For further information, access the Technical Support Package (TSP) free on-line at under the Information Sciences category. Inquiries concerning rights for the commercial use of this invention should be addressed to

the Patent Counsel, Ames Research Center (605) 604-5104.

Refer to ARC-12071.

NASA Tech Briefs Magazine

This article first appeared in the April, 1999 issue of NASA Tech Briefs Magazine.

Read more articles from the archives here.