The problem of diagnosing single faults is addressed for systems whose
fault propagation properties can be modeled as directed graphs. In th
ese systems, the nodes represent components and the edges represent fa
ult propagation between the components. Some of the components are equ
ipped with alarms that become active in response to faulty conditions.
Two algorithms FORWARD and BACKWARD for computing the set of all pote
ntial candidates for a single fault that corresponds to a given set of
active alarms, are studied. The algorithm FORWARD moves forward from
candidate nodes checking to see if they satisfy the alarm condition, a
nd the algorithm BACKWARD moves backwards from the alarms. In terms of
worst-case time complexity the algorithm BACKWARD is better. These tw
o algorithms are analyzed using systems that are uniformly and randoml
y generated. In terms of the expected number of distinct nodes that ar
e visited, the algorithm FORWARD is shown to be better, and in terms o
f the total number of node visits the algorithm BACKWARD is found to b
e better. Thus these algorithms are suited for different modes of stor
ing the system graph.