A recovery attempt might not necessarily lead to a fault-free system. A recovery
procedure is therefore considered to be successful if the probability of recovery P ji
is high.
In other words, P ji ) 1 − P ji .
5.5 PASS Tracing Algorithm
Having introduced the method of active safety, the question arises now how to turn
this process into useful algorithms for detecting possible consequences and possible
problem sources in case of errors. We assume that the probability on the edges of
every node in the dependency graph is 1.
Starting from a suspected node, the PASS algorithm evaluates the possible paths
and ranks them according to their possible consequences in terms of safety (risk and
potential damage). The tracing for every path continues until the multiplicative
probability along it is less than the threshold ɛ, where the value of ɛ is statically set
using engineering expertise.
The value ɛ does not change during the lifetime of a system. For every found
path, the elements along the path are added to the set of potentially unsafe consequences. The algorithm uses two distinctive processes, namely, Forward Tracing
and Backward Tracing [4]. Both of these processes are applied to the Dependency
Matrix.
5.5.1 Forward Tracing Algorithm
The forward tracing algorithm is used to find all possible consequences of a fault in
the suspected element i on the other elements in the system. This algorithm has two
termination conditions: First, the algorithm stops if every node in the dependency
graph (described by a matrix (NÂN) with n elements) has been visited and
processed.
Cycles in the graph must be given special attention in the implementation of the
algorithm for this condition to hold. The second condition is the probability of the
analyzed path. The algorithm stops if the probability is less than ɛ.
We define the probability of the paths from the suspected node d i to node d j as
Q
(p i,j ). If multiple paths lead from node d i to node d j , all possible
Q
(p i,j ) are ranked
and the nodes along the paths are included into the set of suspected nodes.
Figure 5.3 describes the forward tracing algorithm in more detail.
Initially, every node in the graph is considered as not affected by the fault and
the result set D s is initialized to the empty set (not shown in the code). For the
suspected node, the probability is initialized to ɛ; all nodes of the graph are put into
a priority queue Q. We assume that the queue has a function called GetMax, which
5.4 Recovery Matrix
53
procedure is therefore considered to be successful if the probability of recovery P ji
is high.
In other words, P ji ) 1 − P ji .
5.5 PASS Tracing Algorithm
Having introduced the method of active safety, the question arises now how to turn
this process into useful algorithms for detecting possible consequences and possible
problem sources in case of errors. We assume that the probability on the edges of
every node in the dependency graph is 1.
Starting from a suspected node, the PASS algorithm evaluates the possible paths
and ranks them according to their possible consequences in terms of safety (risk and
potential damage). The tracing for every path continues until the multiplicative
probability along it is less than the threshold ɛ, where the value of ɛ is statically set
using engineering expertise.
The value ɛ does not change during the lifetime of a system. For every found
path, the elements along the path are added to the set of potentially unsafe consequences. The algorithm uses two distinctive processes, namely, Forward Tracing
and Backward Tracing [4]. Both of these processes are applied to the Dependency
Matrix.
5.5.1 Forward Tracing Algorithm
The forward tracing algorithm is used to find all possible consequences of a fault in
the suspected element i on the other elements in the system. This algorithm has two
termination conditions: First, the algorithm stops if every node in the dependency
graph (described by a matrix (NÂN) with n elements) has been visited and
processed.
Cycles in the graph must be given special attention in the implementation of the
algorithm for this condition to hold. The second condition is the probability of the
analyzed path. The algorithm stops if the probability is less than ɛ.
We define the probability of the paths from the suspected node d i to node d j as
Q
(p i,j ). If multiple paths lead from node d i to node d j , all possible
Q
(p i,j ) are ranked
and the nodes along the paths are included into the set of suspected nodes.
Figure 5.3 describes the forward tracing algorithm in more detail.
Initially, every node in the graph is considered as not affected by the fault and
the result set D s is initialized to the empty set (not shown in the code). For the
suspected node, the probability is initialized to ɛ; all nodes of the graph are put into
a priority queue Q. We assume that the queue has a function called GetMax, which
5.4 Recovery Matrix
53