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

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

If set [pi] consists of a single version i one can obtain the function [H.sub.[phi][union]{i}](X) using Equations (4) and (5) in the following form:

[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] x [1 x [L.sub.{i},1](X) 0 x [L.sub.{i},0](X)],

= [K.summation over (k=0)](k 1)[L.sub.[phi],k](X)[L.sub.{i},1](X) [K.summation over (k=0)]k x [L.sub.[phi],k](X)[L.sub.{i},0](X),

= [K 1.summation over (k=0)]k x [L.sub.[phi][union]{i},k](X) (6)

Indeed, [L.sub.[phi],k](X)[L.sub.{i},1](X) = 1 represents the logical condition that set [phi] produces k correct outputs and set i produces one correct output which results in a total of k 1 correct outputs; [L.sub.[phi],k](X)[L.sub.{i},0](X) = 1 represents the logical condition that set [phi] produces k correct outputs and set i produces zero correct output which results in a total of k correct outputs.

Consecutively applying the operator [H.sub.{1,..., i}](X) = [H.sub.{1,..., i-1}](X)[cross product] [H.sub.{i}](X) for i = 2,..., N one can obtain the expression for the random number of correct outputs in the entire component:

[H.sub.{1,..., N}](X) = [N.summation over (k=0)]k x [L.sub.{1,..., N},k](X). (7)

Proposition 1. The following algorithm determines Boolean conditions that the component succeeds after termination of the jth version for M [less than or equal to] j [less than or equal to] N.

Step 1. Determine the function [H.sub.{i}](X) for each version of the component according to Equation (4).

Step 2. Define [H.sub.[empty set]](X)=1.

Step 3. For j = 1, 2,..., N:

3.1. Obtain [H.sub.{1,..., j}](X) = [H.sub.{1,2,..., j-1}](X) [cross product] [H.sub.{j}](X) using Equation (6).

3.2. If j [greater than or equal to] M assign: [b.sub.j](X) = [L.sub.{1,..., j},M](X), where [b.sub.j](X) is the Boolean condition that the software component succeeds after termination of the jth version.

3.3. Remove the term M x [L.sub.{1,..., j},M](X) from [H.sub.{1,..., j}](X).

Proof. The entire component produces the correct output directly after the end of the execution of j versions (j [greater than or equal to] M) if and only if the jth version succeeds and exactly (M - 1) out-of-the-first (j - 1) executed versions succeed. The condition of this event is:

[b.sub.j](X) = [L.sub.{1,..., j-1},M-1](X)[L.sub.{j},1](X) = 1. (8)

According to Equation (6) the term M x [L.sub.{1,..., j},M](X) obtained by the operator:

[H.sub.{1,..., j}](X) = [H.sub.{1,..., j-1}](X) [cross product] [H.sub.{j}](X), (9)

is equal to the following sum:

M x [L.sub.{1,..., j},M](X) = M x [L.sub.{1,..., j-1},M-1](X)[L.sub.{j},1](X) M x [L.sub.{1,..., j-1},M](X)[L.sub.{j},0](X). (10)

The first term of the sum corresponds to the event when the jth version succeeds and exactly (M - 1) out-of-the-first (j - 1) versions succeed (only in this case does the component produce the correct output directly after execution of j versions); the second term corresponds to the event when the jth version fails and exactly M-out-of-the-first-(j - 1) versions succeed.