A Time Redundancy Approach to TMR Failures Using Fault-State Likelihoods.
Failure to establish a majority among the processing modules in a triple modular redundant (TMR) system, called a TMR failure, is detected by using two voters and a disagreement detector. Assuming that no more than one module becomes permanently faulty during the execution of a task, Re-execution of the task on the Same HardWare (RSHW) upon detection of a TMR failure becomes a cost-effective recovery method, because 1) the TMR system can mask the effects of one faulty module while RSHW can recover from nonpermanent faults, and 2) system reconfiguration-Replace the faulty HardWare, reload, and Restart (RHWR)-is expensive both in time and hardware. We propose an adaptive recovery method for TMR failures by "optimally" choosing either RSHW or RHWR based on the estimation of the costs involved. We apply the Bayes theorem to update the likelihoods of all possible states in the TMR system with each voting result. Upon detection of a TMR failure, the expected cost of RSHW is derived with these likelihoods and then compared with that of RHWR. RSHW will continue either until it recovers from the TMR failure or until the expected cost of RSHW becomes larger than that of RHWR. As the number of unsuccessful RSHW's increases, the probability of permanent fault(s) having caused the TMR failure will increase, which will, in turn, increase the cost of RSHW. Our simulation results show that the proposed method outperforms the conventional reconfiguration method using only RHWR under various conditions.
Introduction
Fault tolerance is generally accomplished by using redundancy in hardware, software,
time, or combination thereof. There are three basic types of redundancy in hardware and
software: static, dynamic, and hybrid. Static redundancy masks faults by taking a majority
of the results from replicated tasks [13]. Dynamic redundancy takes a two-step procedure
for detection of, and recovery from, faults [2]. The effectiveness of this method relies on
selecting a suitable number of spares, a fault-detection scheme, and a switching operation.
Hybrid redundancy is a combination of static and dynamic redundancy [4]. A core based
on static hardware redundancy, and several spares are provided to tolerate faults. Such
redundant systems could provide very high reliability depending on the number of spares
used under the assumption of perfect coverage and switching operation. However, new faults
may occur during the detection of existing faults, and the switching operation becomes very
complex as the number of spares increases. In order to reduce the complexity of switching
operation and enhance reliability at low cost, self-purging [12] and shift-out [5] schemes were
developed, where faulty modules were removed but not replaced by standby spares. In these
schemes, the additional operation required to select nonfaulty spare(s) is not needed, thus
making the switching operation simpler. But it is difficult to implement either a threshold
voter or a shift-out checking unit which requires comparators, detectors, and collectors.
Triple Modular Redundancy (TMR) has been one of the most popular fault-tolerance
schemes using spatial redundancy. In the Fault-Tolerant MultiProcessor (FTMP) [6], computations
are done on triplicated processors/memories connected by redundant common
serial buses, and its quad-redundant clocks use bit-by-bit voting in hardware on all transactions
over these buses. C.vmp [18] is also a TMR system which traded performance
for reliability by switching between TMR mode with voting and independent modes under
program control. In [22], an optimal TMR structure to recover from a transient fault
was shown to extend significantly the lifetime of a small system in spite of its requirement
of reliable voter circuits. The authors of [3] proposed a modular TMR multiprocessor to
increase reliability and availability by using a retry mechanism to recover transient faults,
and switching between TMR and dual-processor modes to isolate a permanent fault. A
simple multiple-retry policy (retry a pre-specified number of times) - also used to discriminate
a permanent fault - was employed there. This policy can tolerate multiple faults
only by treating them as a sequence of single faults with repair between fault occurrences,
thus requiring frequent voting for effective fault detection. A TMR failure caused by near-
Ccoincident faults in different modules must also be detected and recovered. The effect of
dependent faults inducing a TMR failure was eliminated by periodic resynchronization at
an optimal time interval [7]. However, the fault model of [7] and [22] did not include the
possibility of permanent faults for which resynchronization is no longer effective.
In addition to the use of spatial redundancy with fault masking or reconfiguration,
time redundancy can be applied effectively to recover from transient faults. Such recovery
techniques are classified into instruction retry [10], program rollback [16], program reload
and restart with module replacement. Several researchers attempted to develop an optimal
recovery policy using time redundancy, mainly for simplex systems. Koren [9] analyzed
instruction retries and program rollbacks with such design parameters as the number of
retries and intercheckpoint intervals. Berg and Koren [2] proposed an optimal module
switching policy by maximizing application-oriented availability with a pre-specified retry
period. Lin and Shin [10] derived the maximum allowable retry period by simultaneously
classifying faults and minimizing the mean task-completion time.
The main intent of this paper is to develop an approach of combining time and spatial
redundancy by applying time redundancy to TMR systems. (Note that spatial redundancy
is already encapsulated in the TMR system.) When a TMR failure - failure to
establish a majority due to multiple-module faults - is detected at the time of voting,
or when a faulty module, even if its effects are masked, is identified, the TMR system is
conventionally reconfigured to replace all three or just the faulty module with fault-free
modules. If the TMR failure had been caused by transient faults, system reconfiguration
or Replacement of HardWare and Restart (RHWR), upon detection of a TMR failure, may
not be desirable due to its high cost in both time and hardware. To counter this problem,
we propose to, upon detection of a TMR failure, Re-execute the corresponding task on
the Same HardWare (RSHW) without module replacement. Instruction retry intrinsically
assumes almost-perfect fault detection, for which TMR systems require frequent voting,
thereby inducing high time overhead. However, the probability of system crash due to
multiple-channel faults is shown in [17] to be insignificant for general TMR systems, even
when the outputs of computing modules are infrequently voted on as long as the system
is free of latent faults. Unlike simplex systems, program rollback is not adequate for TMR
systems due to the associated difficulty of checkpointing and synchronization. So, we consider
re-execution of tasks on a TMR system with infrequent voting. For example, since
more than 90% of faults are known to be non-permanent - as few as 2% of field failures
are caused by permanent faults [14] - simple re-execution may be an effective means to
recover from most TMR failures. This may reduce (i) the hardware cost resulting from the
hasty elimination of modules with transient faults and (ii) the recovery time that would
otherwise increase, i.e., as a result of system reconfiguration. Note that system reconfiguration
is time-consuming because it requires the location and replacement of faulty modules,
program and data reloading, and resuming execution.
We shall propose two RSHW methods for determining when to reconfigure the system
instead of re-executing a task without module replacement. The first (non-adaptive) method
is to determine the maximum number of RSHWs allowable (MNR) before reconfiguring the
system for a given task according to its nominal execution time without estimating the
system (fault) state - somewhat similar to the multiple-retry policy applied to a general
rollback recovery scheme in [20]. By contrast, the second (adaptive) method (i) estimates
the system state with the likelihoods of all possible states and (ii) chooses the better of
RSHW or RHWR based on their expected costs when the system is in one of the estimated
states. RHWR is invoked if either the number of unsuccessful RSHWs exceeds the MNR
in the first method or the expected cost of RSHW gets larger than that of RHWR in the
second method. For the second method, we shall develop an algorithm for choosing between
RSHW and RHWR upon detection of a TMR failure. We shall also show how to calculate
the likelihoods of all possible states, and how to update them using the RSHW results and
the Bayes theorem.
The paper is organized as follows. In the following section, we present a generic methodology
of handling TMR failures, and introduce the assumptions used. Section 3 derives the
optimal voting interval (X v ) for a given nominal task-execution time X . The MNR of the
first method and the optimal recovery strategy of the second method are computed for
given X . We derive the probability density function (pdf) of time to the first occurrence
of a TMR failure, the probabilities of all possible types of faults at that time, transition
probabilities up to the voting time, the costs of RSHW and RHWR, and the problem of up-dating
likelihoods of the system state and the recovery policy after an unsuccessful RSHW.
Section 4 presents numerical results and compares two recovery methods of RSHW and
RHWR. The paper concludes with Section 5.
Detection and Recovery of a TMR Failure
Detection and location of, and the subsequent recovery from, faults are crucial to the
correct operation of a TMR system, because the TMR system fails if either a voter fails at
the time of voting or faults manifest themselves in multiple modules during the execution of
a task. The fault occurrence rate is usually small enough to ignore coincident faults which
are not caused by a common cause, but non-coincident fault arrivals at different modules
are not negligible and may lead to a TMR failure.
Disagreement detectors which compare the values from the different voters of a TMR
system can detect single faults, but may themselves become faulty. FTMP [6], JPL-STAR
[1], and C.vmp [18] are example systems that use disagreement detectors. In FTMP, any
detected disagreement is stored in error latches which compress fault-state information
into error words for later identification of the faulty module(s). System reconfiguration
to resolve the ambiguity in locating the source of a detected error is repeated depending
on the source of the error and the number of units connected to a faulty bus. Two fault
detection strategies - hard failure analysis (HFA) and transient failure analysis (TFA)
are provided according to the number and persistency of probable faulty units. These
strategies may remove the unit(s) with hard failures or update the fault index (demerit)
of a suspected unit. Frequent voting is required to make this scheme effective, because
any faulty module must be detected and recovered before the occurrence of a next fault on
another module within the same TMR system.
Voting in a TMR system masks the output of one faulty module, but does not locate
the faulty module. One can, however, use a simple scheme to detect faulty modules and/or
voter. Assuming that the probability of two faulty modules producing an identical erroneous
output is negligibly small, the output of a module-level voter becomes immaterial when
multiple modules are faulty [8]. A TMR failure can then be detected by using two identical
voters and a self-checking comparator as shown in Fig. 1. These voters can be implemented
with conventional combinational logic design [23]. The comparator can be easily made self-checking
for its usually simple function: for example, a simple structure made of two-rail
comparators in [11] for each bit can be utilized for its high reliability and functionality. This
TMR structure can also detect a voter fault. When a TMR failure or a voter fault occurs,
the comparator can detect the mismatch between the two voters that results from either
the failure to form a majority among three processing modules, or a voter fault. (Note that
using three voters, instead of two, would not make much difference in our discussion, so we
processor 3
processor 2
processor 1
voter 2
voter 1
ae
oe
comparator
\Phi \Phi \Phi \Phi \Phi*
\Omega \Omega \Omega \Omega \Omega \Omega \Omega OE
\Phi \Phi \Phi \Phi \Phi*
J" \Phi \Phi \Phi \Phi \Phi*

Figure

1: The structure of a TMR system with two voters and a comparator.
will focus on a two-voter TMR structure.)
If the comparator indicates a mismatch between two voters at the time of voting, an
appropriate recovery action must follow. Though RHWR has been widely used, RSHW may
prove more cost-effective than RHWR in recovering from most TMR failures. To explore
this in-depth, we will characterize RSHW with the way the MNR is determined. The
simplest is to use a constant number of RSHWs irrespective of the nominal task-execution
time and the system state which is defined by the number of faulty modules and the fault
type(s). Taking into account the fact that the time overhead of an unsuccessful RSHW
increases with the nominal task-execution time X , one can determine the MNR simply
based on X , without estimating the system state. A more complex, but more effective,
method is to decide between RSHW and RHWR based on the estimated system state.
Since the system state changes dynamically, this decision is made by optimizing a certain
criterion which is dynamically modified with the additional information obtained from each
unsuccessful RSHW. In this adaptive method, the probabilities of all possible states will
be used instead of one accurately-estimated state. Upon detection of a TMR failure, the
expected cost of RSHW is updated and compared with that of RHWR. The failed task will
then be re-executed, without replacing any module, either until RSHW recovers from the
corresponding TMR failure or until the expected cost of RSHW becomes larger than that
of task execution. 2 As the number of unsuccessful RSHWs increases, the possibility of
permanent faults having caused the TMR failure increases, which, in turn, increases the
cost of RSHW significantly.
This procedure is described in the algorithm of Fig. 4.
Throughout this paper, we assume that the arrival of permanent faults and the arrival
and disappearance of non-permanent faults are Poisson processes with rates
respectively.
Optimal Recovery from a TMR Failure Using RSHW
3.1 The Optimal Voting Interval
n) be the nominal task-execution time measured in CPU cycles between
the (i \Gamma 1)-th and i-th voting, and let X 1 be that between the beginning of the task and the
first voting, in the absence of any TMR/voter failure. As shown in Fig. 2, for 1  i  n let
task-execution time from the beginning of the task to the first completion of
the i-th voting possibly in the presence of some module failures, and let W
E(w is the expected execution time of the task. Upon detection of a TMR failure,
let p and q be the probabilities of recoverying a task with RSHW and RHWR, respectively,
1. Assuming that the time overhead of reconfiguration is constant T c , W n
is expressed as a recursive equation in terms of W i , 1  i  n. Let F i (t) (2  i  n) be
the probability of a TMR failure in t units of time from the system state at the time of the
(j \Gamma 1)-th voting, and let F 1 (t) be that from the beginning of the task. The probability of
a recovery attempt (i.e., RSHW or RHWR) being successful depends upon F i (t). When a
TMR failure is detected at the time of first voting (i.e., it occurred during the execution
of the task portion corresponding to X 1 ), the system will try RSHW (or RHWR) with
probability p (or q) to recover from the failure. This process is renewed probabilistically
for the variable w 1 which is the actual task-execution time corresponding to the nominal
task-execution time X 1 . Thus,
where T c is the setup time for system reconfiguration.
Let T v be the time overhead of voting which is in practice negligible. The above equation
is also renewed for all w i 's (2  i  n) after each successful recovery. Hence,
defined as the actual task-execution time between the (i \Gamma 1)-th and i-th votings,
oe -oe -oe - oe -
TMR failure
voting
oe

Figure

2: Graphical explanation for V i and w i for 1  i  n.
From the above equations, the following recursive expressions are derived for 2  i  n:
Applying this recursively times, we can get:
Y
The optimal voting frequency is derived by minimizing W n with respect to n and X i ,
subject to
If all inter-voting intervals are assumed to be identical then the constant voting interval is
an optimal value of n must be determined by minimizing
Eq. (3.1). Examples of n for a given X with typical values of are shown in

Table

1. The voting points can be inserted by a programmer or a compiler.
3.2 Pre-determination of Non-adaptive RSHWs
In the first method, we determine a priori the maximum number of RSHWs (MNR), km ,
based on X without estimating the system state. The associated task will be re-executed up
to km times. As X increases, the effect of an unsuccessful RSHW becomes more pronounced;
that is, the possibility of successful recovery with RSHW (instead of RHWR) will decrease
with X due to the increased rate of TMR failures, and the time overhead of an unsuccessful
RSHW also increases with X while the time overhead of RHWR remains constant. So, km
decreases as X increases.
Let C 1 (k; X) be the actual time/cost of task execution in the presence of up to k RSHWs
for a task with the nominal execution time X , which can be expressed as:
Y
Y
s (p n
the probability of the n-th RSHW becoming successful
(unsuccessful) and the probability of a TMR failure during X after system reconfiguration,
respectively, where p n
In fact, p n
s and p n
u cannot be determined
without knowledge of the system state after the (n \Gamma 1)-th unsuccessful RSHW, which is too
complicated to derive a priori. We will approximate these probabilities using the following
useful properties of a TMR system. Since the probability of permanent faults having caused
the TMR failure increases with the number of unsuccessful RSHWs, p n
s is monotonically
decreasing in n:
Though
s and R(n) j p n+1
s depend upon X and fault parameters, it is assumed for
simplicity that p 1
s is given a priori as a constant P and R(n) is a constant R for all n.
modified in terms of P and R:
Y
The cost of RHWR, denoted by C 2 (X), is derived by using recursive equations:
Now, km can be determined as the integer that minimizes C 1 (k; X) subject to C 1
Example values of km for typical values of P and R are shown in Table 2.
3.3 Adaptive RSHW
In this method, the system chooses, upon detection of a TMR failure, between RSHW
and RHWR based on their expected costs. RSHW will continue either until it becomes
successful or until the expected cost of the next RSHW becomes larger than that of RHWR.
The system state is characterized by the likelihoods of all possible states because one can
observe only the time of each TMR failure detection, which is insufficient to accurately
estimate the system state. The outcome of one RSHW, regardless whether it is successful
or not, is used to update the likelihoods of states in one of which (called a prior state)
the RSHW started. The possible states upon detection of a TMR failure can be inferred
from the posterior states which are the updated prior states using the RSHW result and
the Bayes theorem.
Unlike a simplex model, there are too many possible states and events to analyze a
TMR system accurately. We will thus use the simplified Markov-chain model in Fig. 3 to
derive the state probabilities and transition probabilities in a TMR system. The model
consists of six states which are distinguished by the number of permanent faults and that
of non-permanent faults, where two- and three- fault states are merged into one state due
to their identical effects in our analysis. In Fig. 3 the transitions over the bidirectional
horizontal lines result from the behavior of non-permanent faults and the transitions over
the unidirectional vertical lines are caused by the occurrence of permanent faults. Note
that even occurrences of near-coincident faults can be represented by sequential occurrences
with slightly different interarrival times. The model, thus, includes only transitions between
neighboring states - any transition from a state due to multiple faults occurs in two steps
through one of its neighboring states.
Some faults may disappear without affecting the execution of a task. This happens
when the latency of a fault is greater than its active duration, i.e., it will not manifest itself.
Note that the occurrence of an error in a module during the task execution may produce
an erroneous output for the task, even if the fault which had induced the error disappeared
before producing the final output of the task. In other words, a transient fault may have
permanent effects on task execution. 3
The optimal recovery algorithm based on the adaptive method in Fig. 4 can be illustrated
as follows. Upon detection of a TMR failure, the first step is to derive the probabilities
3 In fact, this problem can be eliminated by resynchronizing the processors after a transient fault is
detected [21]. This, however, requires frequent voting and additional mechanisms for detecting errors in
each processor and resynchronizing the processors.
of all possible states at time X f evolved from each prior state. Let T i
f be the time when
the TMR system moved to the failure state from prior state i during [0; X f ], where X f is
the time of detecting a TMR failure (i.e., a voting time). Occurrence of a TMR failure
is then represented by an event (T i
We want to calculate the
probabilities of all possible states  i
at voting time X f evolved from prior state i,
which are actually conditional probabilities given the observed event (T i
be calculated from the probabilities of all types of TMR failures  i
f ) at time T i
f and the
transition probabilities Pmn
during the remaining task-execution time,
f .
The probabilities of all possible states are thus
f
f
where subscripts indicate the prior state, the state at time T i
f , and the state
at the time, X f , of detecting a TMR failure, respectively. As mentioned earlier, a voting
failure may result from a voter fault or multiple-module faults. Multiple-module faults
can be classified based on the number of modules with permanent faults: Type-I, Type-
II, and Type-III failures represent zero, one, and more than one permanent-fault module,
respectively, where all possible states of each type are listed in Fig. 3. Let S(x; y) be
the state with x permanent-fault modules, y non-permanent-fault modules, and 3
nonfaulty modules.
Although there are ten different states, we only need to consider six of them by merging
This merger of states simplifies the model of a TMR system without losing model accuracy,
because:
ffl By modifying the transition rates, one can make the simplified Markov-chain model
in Fig. 3 represent a TMR system very accurately, and
ffl The merger is based on a realistic assumption that simultaneous occurrence of faults
in different processor modules is highly unlikely.
Moreover, the merger does not change the analysis of a TMR failure because merged
states have similar effects on the TMR failure as compared to the original states. For
example, the merged states induce the same type of TMR failure, where the 'type' is
determined by the number of permanent-fault modules. There are four possible states,
which led to Type-I failures (i.e., it was S(0; 1),
&%
&%
&%
&%
&%
oe
oe
oe
TYPE-III failure
possible states
at time X f
TYPE-II failure
possible states
at time X f
TYPE-I failure
possible states
at time X f

Figure

3: A simplified Markov-chain model for a TMR system.
S(0; 2), or S(0; 3) at time T i
f , because a non-permanent fault might disappear after inducing
error(s). Type-II and Type-III failures have three possible states, fS(1; 0); S(1; 1); S(1; 2)g
and fS(2; 0); S(2; 1); S(3; 0)g, respectively, at time T i
f and X f .
For notational simplicity, let state S i j S(x; y) where y. Then, the set of all
possible states after the merging is out of these, fS 1
are the set of possible fault states transited from S 0
f , and T 2
respectively. S 4 and S 5 may change to S 5 (or S 8 ) at T 4
f (or T 5
f ), and S 8 remains unchanged
due to the persistence of a permanent fault.
Let a path denote the transition trajectory between a pair of states. Since there are
usually more than one path between a given pair of nodes, each of these paths is assigned
an ID number. From the simplified model in Fig. 3, T i
f is the minimum-time path from S i
to any type of TMR failure. Let t i
j be the time taken from S i to a TMR failure via path
j. Then, T i
where the pdf of t i
j is calculated by convolving the pdf 's of all
sub-paths that make up path j. The pdf of a sub-path between two states
is obtained by using the distribution of sojourn time
of
with several exits in the
Markov chain model (Fig. 3):
\Gamma(
represents the set of all outgoing arcs of S j k . Then, the pdf of t i
j is
where path j is composed of sub-paths fij must be one of possible
fault states: Sm 2 fS 1 g. (When the inter-arrival time of events such as fault
occurrence, fault disappearance, and fault latency, is not exponentially distributed, we need
a semi-Markov chain model in place of a Markov chain model.) Let J i
represent the set of
all paths to a fault state Sm from S i . The likelihood of a fault state Sm at time T i
equal to
f ), which is obtained by:
is the set of all paths to all possible fault states evolved from S i , i.e.,
8g. The probabilities of S 1 and S 2 leading to Type-I failure are
computed based on the behavior of non-permanent faults, i.e., depending on whether or
not a non-permanent fault, after having induced some error(s), is still active when a second
non-permanent fault occurs. Likewise, the probabilities of S 4 and S 5 leading to Type-II
failure are computed by the behavior of a non-permanent fault, if it had occurred earlier
than permanent fault(s). When an intermittent fault is considered, the fault state must
be divided by fault active and fault benign states as in [15], which makes the problem
too complicated to be tractable. The numerical examples of F T i
f
(X) and the mean of T i
f
several X are given in Figs. 5 and 6, in which analytic results are compared
against the results obtained from Monte-Carlo simulations.
In addition to f T i
f
and  i
m , the transition probabilities Pmn from Sm to S n during
f must be derived in order to obtain the likelihood of every possible state at the time
of voting (failure detection), X f . Although the matrix algebra using the transition matrix
or Chapman-Kolmogrov theorem can be applied to give accurate expressions, we will use a
simplified method for computational efficiency at an acceptably small loss of accuracy. For
the transition probabilities from T i
f , we need not consider subsequent errors but can focus
on only those states useful in choosing between RSHW and RHWR.
Observe that the occurrence rate,  p , of permanent faults is much smaller than both the
appearance and disappearance rates of non-permanent faults. Using this observation, one
can analyze the behavior of permanent faults separately from that of non-permanent faults.
The transition probabilities due to the occurrence of permanent faults are represented by
because of the persistence of permanent faults.
Although these probabilities depend upon  i
are approximated
by using only the prior probabilities of source states,  i
f ). This approximation causes
only a very small deviation from the exact values because the occurrence rate of permanent
faults is usually very small as compared to the other rates. For example, consider P 1n
for n  4, i.e., transitions from S 1 due to the occurrence of permanent fault(s). The
corresponding transition probabilities are derived from the model in Fig. 3 in terms of the
pdf 's of sub-paths between two states. Let
f , then
The probability  i
f ) for S 1 is thus reduced to (1\GammaF 15 (T
transitions
from other source states due to the occurrence of permanent faults can be derived. Conse-
quently, the prior probabilities are transformed into
f ); respectively. Using these transformed prior probabilities, we will
derive the transition probabilities based only on the behavior of non-permanent faults.
Considering only the behavior of non-permanent faults divides the above model into
a two-state model fS 4 and a three-state model fS 0 as shown in Fig. 3. The
transition matrix of the three-state model fS 0 is derived by (i) using the Laplace
transform which reduces the linear differential equations of three states to algebraic equations
in s, (ii) solving the algebraic equations, and (iii) transforming the solution back into
the time domain.
The linear differential equation of fS 0 with only the effects of non-transient
faults is
The Laplace transform of T is:
The solution requires the inverse of A:
A
Let the roots of s
be ff and fi, then a ij , the ij-th
element of A, can be obtained by partial fraction expansion:
c (ij)1
s
c (ij)2
c (ij)3
Since c (ij)2 and c (ij)3 are conjugates, c ff). The effect of
permanent faults changes the initial probabilities of
where A
Thus, the i-th column of the 3 \Theta 3 transition matrix P(T ) reduces to:6 6 6 4
where
The above equations indicate that the coefficients of exponentials in A 0 , A 1 , and A 2 include
the effects of the occurrence of permanent fault(s) on the prior probabilities. Likewise, the
transition matrix of a two-state model for fS 4 can be derived as:4 (
e \Gamma(2 n+)T )A 4 (
e \Gamma(2 n+)T )A 5
e \Gamma(2 n+)T )A 4 ( 2n
where A the effects of permanent-
fault occurrences on the transitions to S 8 . These transition matrices and probabilities
(resulting from the occurrence of permanent faults) can describe all possible transitions in
the simplified model of Fig. 3.
When the TMR system is in S 2 , S 5 or S 8 at time X f , RSHW will be unsuccessful again
due to multiple active faults (in more than one module). If it is not in those states at
due to disappearance of active fault(s) after inducing some error(s), the system
moves to a recoverable state by RSHW. Let F T i
f
(X) be the probability of a TMR failure
evolved from S i during the execution time X , where F T i
f
is the probability distribution
function of T i
f . Since exact knowledge of the system state is not available, we estimate the
state probabilities, which are then used to calculate the expected cost of a single RSHW as
follows:
f
(X)@ X
i2f2;5;8g
i2f0;1;4g
f
where  i (0) is the probability that the state before starting one RSHW (upon detecting a
TMR failure) is S i , i.e., the probabilities of the present states become those of the prior
states for the next RSHW. The expected cost of RHWR is obtained similarly to Eq. (3.4):
f
(X)
When RSHW is unsuccessful or a voting failure occurs again, the (prior) state probabilities
are updated with the additional information obtained from the RSHW using the
Bayes theorem. The observed information tells us that a TMR failure has occurred again
during the current execution. (Note that the TMR failure detection time during the current
execution is X f .) As a result, the prior probabilities of all possible fault states for the
are renewed from those of the k-th RSHW ( k
during X f from S i )
Prob(a TMR failure during
where Prob(a TMR failure during X f
during X f from S i
f
From Eq. (3.10) one can see that the probability of the TMR system
being in a permanent-fault state increases with each unsuccessful RSHW, which, in turn,
increases the chance of adopting RHWR over RSHW upon detection of next TMR failure.
Using the above updated state probabilities, we can get the conditional probabilities of all
states upon detection of a TMR/voting failure.
When RSHW is successful, one can likewise update the probabilities of possible states,
which will then be used to guess the prior state of the next voting interval.
When the hardware cost is high and the time constraint is not stringent, one may do the
following. Since the fault occurrence rate is much smaller than the disappearance rate of
non-permanent faults, we may wait for a certain period of time (called a back-off
time) in order for the current non-permanent fault(s) to disappear before task re-execution.
An optimal back-off time is determined by minimizing the expected time overhead. When
a task is re-executed without any back-off, the cost of one RSHW is equal to Eq. (3.8).
When re-execution starts after backing off for r units of time, the cost changes (due to the
change of prior states):
f
(X)@ X
i2f2;5;8g
i2f0;1;4g
f
The optimal back-off time is obtained by minimizing C 1 (r) with respect to r.
a TMR failure
derive  n (X)
compute C 1
yes
no
successful ?
yes no
update prior prob.
oereconfiguration
re-execute
continue execution

Figure

4: Algorithm to recover from a TMR failure by estimating the system state and
comparing the costs of RSHW and RHWR.

Table

1: n vs. X for (p; T

Table

2: km vs. X for
200 3000 0:0001 0:002 50

Table

3: Parameter values used in simulations, all measured in hours.
4 Numerical Results and Discussion
A system with three replicated processing modules, two voters, and a comparator is
simulated to compare the proposed method (called Method 1) with an alternative which
is based on RHWR (called Method 2). Upon detection of a TMR failure, Method 1 will
decide between RSHW and RHWR according to their respective costs. Method 2, however,
will reconfigure the TMR entirely with a new healthy TMR or partially with healthy spare
modules following an appropriate diagnosis. If a non-permanent fault does not disappear
during the diagnosis, it will be treated as a permanent fault and replaced by a new, non-faulty
spare. We assume that (A1) an unlimited number of tasks with the same nominal
task-execution time are available to keep the running module busy, which simplifies the
description of system workload, and (A2) there are an unlimited number of spares available.
The performances of these two methods are characterized by the overhead ratio:
where E is the real execution time (including the RSHW and/or RHWR overheads) of a
task whose nominal execution time is X .
We ran simulations under the fault generation process with the parameters as given

Table

3, where the symbol * indicates a parameter varied while the others are fixed, in
order to observe the effects of the parameter on OVR in both methods. Since fault oc-
currence/disappearance rates are difficult to estimate on-line, some experimental data or
numerical data based on a model reflecting the maturity of design/fabrication process, the
environmental effects, operating conditions, and the number and ages of components, can
be used [19].
In Figs. 5 and 6, the probabilities of a TMR failure and the failure times from S 0 and
S 4 are computed from the Markov-chain model and simulations, and are then compared.
The simulation and modeling results are very close to each other. The modeling analyses
proved to be very effective in determining when and how to choose between RSHW and
RHWR under various conditions, as shown in Figs. 7-11.
The results obtained while varying X from 10 to 100 hours with T are plotted
in Figs. 7-9. The OVRs of Methods 1 and 2 with the optimal number of votings are
compared in Fig. 7. The difference between the OVRs of Method 1 and Method 2 increases
significantly with X . When X is small, the OVRs of the two methods are too small to
distinguish, which is due mainly to the small probability of a TMR failure. Fig. 8 compares
the multi-voting policy (with the optimal number of votings) and one voting policy.
Generally, the overhead of a TMR system with infrequent voting increases significantly as
increases, because the probability of a TMR failure increases with X ; e.g., if there is
no voting during the task execution, a TMR failure means the waste of the entire nominal
execution time, X . As X increases, the OVR of a one-voting policy increases more rapidly
than that of multi-voting policy. The number of RHWRs - which is represented by the
percentage of RHWR from the total number of simulations in Fig. 9 - will determine the
hardware cost of spares used. The increase in this percentage is much larger in Method
than Method 1, since the number of TMR failures increases with X , and Method 1 can
recover from most TMR failures with RSHW.
The second comparison is made while varying T c - the resetting time for system reconfiguration
- from 2:5 to 12:5 hours for X=50 hours, and the results are plotted in Fig. 10.
A larger resetting time generally results in a larger OVR. Increasing T c greatly affects the
performance of Method 2. But, it has little influence on the OVR of Method 1, since the
system recovers from most TMR failures with RSHW which has nothing to do with T c .
The third comparison in Fig. 11 is made while varying n
p from 5 to 25, where  n is fixed
at 0:005 /hr, and hours and T hours. The OVRs of both methods decrease
with n
p , but the magnitude of decrease in Method 1 is larger than that in Method 2. This
is because the probability of a TMR failure decreases as  p decreases with  n fixed, and
because the probability of successful RSHW increases with n
.
We simulated the proposed and other schemes for units of time with the fault
parameters of Table 3 for each comparison (of the mean overhead ratios of different schemes).
The fault parameters are assumed not to change during the simulation. Since the estimation
of system states depends upon the fault parameters, they must be estimated first. This
problem can be solved by assuming the parameters to be time-varying and estimating them
on-line with certain adaptive methods which, in turn, require more samples.
5 Conclusion
In this paper, we have proposed a strategy for recovering TMR failures using two different
methods that determine when and how to apply RHWR. Both methods are shown
to outperform the conventional method based solely on reconfiguration. This finding is
consistent with the fact that most faults are non-permanent, so simple re-execution can recover
from non-permanent faults and the TMR structure can mask the effects of one faulty
module.
The distinct characteristic of the proposed strategy is that it uses the estimated state
of a TMR system even with incomplete observation of system states. Detection of a TMR
failure and/or an unsuccessful RSHW does not always call for reconfiguration (RHWR) but
requires us to derive and compare the expected costs of reconfiguration and one additional
RSHW. Most TMR failures are represented by using a simplified Markov-chain model, and
the TMR failure time and the probability of another unsuccessful RSHW are also analyzed
with the model. One can therefore conclude that combining time and spatial redundancy
appropriately can be effective in handling component failures.

Acknowledgement

The authors would like to thank Allan White, Chuck Meissner, and Felix Pitts of the
NASA Langley Research Center, and Jim Smith of the Office of Naval Research for their
technical and financial assistance.



--R

"The STAR(self-testing and repairing) computer: An investigation of theory and practice of fault-tolerant computer design,"
"On switching policies for modular redundancy fault-tolerant computing systems,"
"Modular TMR multiprocessor sys- tem,"
"Reliability and analysis of hybrid redundancy,"
"Shift-out modular redundancy,"
"FTMP-a highly reliable fault-tolerant multiprocessor for aircraft,"
"Design of dependent-failure-tolerant microcomputer system using triple-modular redundancy,"
"Embedding triple-modular redundancy into a hypercube architecture,"
"Analysis of a class of recovery procedures,"
"An optimal retry policy based on fault classification,"
"A RAM architecture for concurrent access and on-chip testing,"
"A highly efficient redundancy scheme: Self-purging redundancy,"
"The use of triple-modular redundancy to improve computer reliability,"
"The measurement and analysis of transient errors in digital computer systems,"
"Error detection process - model, design, and its impact on computer performance,"
"Optimal checkpointing of real-time tasks,"
"Study on fault-tolerant processor for advanced launch system,"
"A case study of C.mmp, Cm*, and C.vmp: Part I - experiences with fault tolerance in multiprocessor systems,"
The Theory and Practice of Reliable System Design
"A watchdog processor based general rollback technique with multiple retries,"
"Transient failures in triple modular redundancy systems with sequential modules,"
"Microcomputer reliability improvement using triple-modular redun- dancy,"
"A new design method of voter in fault-tolerant redundancy multiple-module multi-microcomputer system,"
--TR
Analysis of a class of recovery procedures
A watchdog processor based general rollback technique with multiple retries
On switching policies for modular redundancy fault-tolerant computing systems
Optimal checkpointing of real-time tasks
Embedding triple-modular redundancy into a hypercube architecture
A RAM Architecture for Concurrent Access and on Chip Testing
An Optimal Retry Policy Based on Fault Classification

--CTR
Hagbae Kim , Kang G. Shin, Sequencing Tasks to Minimize the Effects of Near-Coincident Faults in TMR Controller Computers, IEEE Transactions on Computers, v.45 n.11, p.1331-1337, November 1996
Hagbae Kim , Kang G. Shin, Design and Analysis of an Optimal Instruction-Retry Policy for TMR Controller Computers, IEEE Transactions on Computers, v.45 n.11, p.1217-1225, November 1996
Jae Kwon Kim , Byung Kook Kim, Probabilistic Schedulability Analysis of Harmonic Multi-Task Systems with Dual-Modular Temporal Redundancy, Real-Time Systems, v.26 n.2, p.199-222, March 2004
Jos Manuel Cazeaux , Daniele Rossi , Cecilia Metra, Self-Checking Voter for High Speed TMR Systems, Journal of Electronic Testing: Theory and Applications, v.21 n.4, p.377-389, August    2005
Byonghyo Shim , Naresh R. Shanbhag, Energy-efficient soft error-tolerant digital signal processing, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.14 n.4, p.336-348, April 2006
bayes methods;voters;time redundancy approach;redundancy;adaptive recovery method;triple modular redundant system;system reconfiguration;processing modules;disagreement detector;fault-state likelihoods;simulation results;bayes theorem;TMR failures;fault tolerant computing;digital simulation