Performance distribution of a fault-tolerant system in the presence of failure correlation

IIE Transactions, June, 2006 by Gregory Levitin, Min Xie

3.3. If m = M stop the procedure.

4.2. The case of independent CCFs

The necessary condition for component success is the nonoccurrence of any CCF j with |[[OMEGA].sub.j]| > N - M. The probability of such an event is:

p* = [[product].[|[[OMEGA].sub.j]|>N-M]][q.sub.j]. (1)

When the probability [p.sub.j] that the component produces a correct output after termination of the jth version is determined one can avoid considering CCFs [[OMEGA].sub.j] with |[[OMEGA].sub.j]| > N - M. Any [p.sub.j] obtained without considering these CCFs should be multiplied by the probability p*.

Let [[omega].sub.i] be a set of CCFs that affect version i and [x.sub.m] be the Boolean indicator of the status of CCF m ([x.sub.m] = 0 if CCF m occurs and [x.sub.m] = 1 otherwise). If any CCF m (m [member of] [[omega].sub.i]) occurs then version i produces an incorrect output. This means that [[product].sub.m[member of][[omega].sub.i]][x.sub.m] = 0 is the condition of version i failure.

For any set of versions [phi] one can define a Boolean function [L.sub.[phi],k] (X) of vector X = ([x.sub.1],[x.sub.2],..., [x.sub.Y]) of CCF statuses that represents the condition that these versions produce exactly k correct outputs ([L.sub.[phi],k](X) = 1 if the number of correct outputs is k and [L.sub.[phi],k](X) = 0 otherwise). For example, a set consisting of single version [phi] = {i} can produce one correct output if the condition [L.sub.{i},1](X) = [[product].sub.m[member of][[omega].sub.i]][x.sub.m] = 1 is met and zero correct outputs if the condition [L.sub.{i},0](X) = (1 - [[product].sub.m[member of][[omega].sub.i]][x.sub.m]) = 1 is met.

Note that the functions [L.sub.[phi],k] (X) for different k represent mutually exclusive events. Therefore, for any realization x of the random binary vector X for a set [phi] consisting of K versions:

[K.summation over (k=0)][L.sub.[phi],k](x) = 1. (2)

This allows us to define the random number of correct outputs produced by the set [phi] as an integer-valued function of the random binary vector X in the form of:

[H.sub.[phi]](X) = [K.summation over (k=0)]k x [L.sub.[phi],k](X). (3)

The random number of correct outputs produced by a single version i can be represented, according to Equation (3) as follows:

[H.sub.{i}](X) = [1 x [L.sub.{i},1](X) 0 x [L.sub.{i},0](X)] = 1 x [[product].[m[member of][[omega].sub.i]]][x.sub.m] 0 x (1 - [[product].[m[member of][[omega].sub.i]]][x.sub.m]). (4)

Having the functions [H.sub.[phi]] (X) and [H.sub.[pi]] (X) for the two disjoint sets [phi] and [pi] allows us to obtain the function [H.sub.[phi][union][pi]] (X) for the set [phi][union][pi] using the following operator [cross product]:

[H.sub.[phi][union]{i}](X) = [H.sub.[phi]](X) [cross product] [H.sub.{i}](X) = [K.summation over (k=0)]k x [L.sub.[phi],k](X) [cross product] [H.summation over (h=0)]h x [L.sub.[pi],h](X) = [K.summation over (k=0)][H.summation over (h=0)](k h) x [L.sub.[phi],k](X)[L.sub.[pi],h](X), (5)

in which the multiplication of the Boolean function corresponds to a logical conjunction operator (the multiplication of Boolean functions with a multi-linear form is performed in the usual manner taking advantage of the rule that [x.sub.m] x [x.sub.m] = [x.sub.m]). The logical condition [L.sub.[phi],k](X)[L.sub.[pi],h](X) = 1 corresponds to the case in which versions from set [phi] produce k correct outputs and versions from set [pi] produce h correct outputs which results in a total of k h correct outputs.