\documentclass[11pt]{article}


\title{Fault Tolerant Computing \\ \large 6.911 Architectures Anonymous}
\author{Chris Laas}
\date{April 11, 2000}

\pagestyle{myheadings}
\markright{Chris Laas \hfil Fault Tolerant Computing}


\begin{document}
\maketitle


\section{Summary}

As the limits of computer technology are pushed into the domains of
the very small, the very cheap, and the very robust, the near-perfect
reliability which had been granted by the digital abstraction has
eroded.  Small components may be cheap and fast, but it is an ever
greater challenge to produce the correct answer every time, an
immovable constraint of the design. 
(\verb:gcc --wrong-answer-very-quickly: isn't in terribly high
demand.)  To compound the problem, the environment is anything but
friendly to computer systems:  a typical system is under mechanical,
thermal, radiative, and electromagnetic stresses which may interfere
with the operation of the machine.

The set of errors that can occur are divided into two broad
categories, defects and faults.  Defects, which are errors made in the
hardware during manufacture, become far more common as the complexity
and density of the circuits increases, resulting in ever lower
perfect-chip yields as time goes on.  The most common results of chip
defects are faulty logic and flaky connections, which usually manifest
as opens, shorts, or stuck at 1 or 0.

On the other hand, faults are errors made during a calculation, at run
time.  For example, electromagnetic noise or particle radiation can
cause undesirable energy spikes in a circuit; in fact, this can be
exploited to use DRAM chips as reliable and cheap alpha particle
detectors.  In addition, the inherently statistical nature of
metastable circuits (such as registers) cause an low, but nonzero
error rate, which can be decreased (by slowing the clock rate) but not
eliminated.  Run-time faults typically result in unpredictable,
random, and independent errors; in contrast, defects usually cause
highly predictable and correlated errors.

The generic engineering solution to the problem of flaky components is
redundancy: using multiple unreliable components in a coordinated,
mutually verifying way can increase the reliability of the complete
system by orders of magnitude.  For example, if two identical,
redundant components are each down 0.1\% of the time, their failure
modes are completely independent and detectable, and the rest of the
system (including the arbitrator which determines which component to
trust) can be approximated as 100\% perfect, then the whole system
should be down only 0.0001\% of the time.  As the example
demonstrates, it's never possible to reach 100\% reliability, but it
is often possible to come arbitrarily close to the limit.  In general,
accomplishing this is more difficult than it seems, because any
component of the system (be it computing element, network element,
input/output device, or even redundancy arbitrator) can be the
reliability bottleneck of the system.


\section{Defect-tolerant architectures}

As manufacturing processes push the size and speed limits of silicon
circuitry, and as the sheer number of components per chip balloons,
the yield of perfect chips from a fab inevitably drops, wasting
precious resources.  While the mainstream solution to this problem is
ever-more-precise manufacturing processes in ever-more-pristine clean
rooms, the cost of such fabs is approaching billions of dollars.
Another way to increase effective yields is to design some amount of
redundancy into the system; for example, RAM chips are often
fabricated with a few extra lines of storage space, which are wired in
as replacements for any lines which turn out to be faulty.

A particularly ambitious system of this type is Teramac, a custom
configurable computer designed by HP Labs.  Teramac consists of 65,536
LUTs (distributed among about a thousand FPGAs) connected via
crossbars in a fat-tree network.  This extremely flexible architecture
had few critical paths (the only components that needed to be perfect
were the power and clock wires) and highly redundant network
connectivity through the fat-tree; this allowed the compiler to map
out the defects in the system once, and simply route around bad LUTs
and interconnects when compiling.  In particular, the conscious design
decision to out-wire Rent's Rule (Teramac used Rent's Rule exponents
of 2/3 to 1, as opposed to the ``normal'' exponents of 1/2 to 2/3)
allowed the system to function normally despite defects in 10\% of
logic cells and 10\% of interchip interconnects.  Most importantly,
the defect tolerance scaled well: if a wire or component were
physically damaged, the loss of computational capacity (after
recompiling) was roughly proportional to the fraction of damaged
parts.


\section{Fault-tolerant signal transmission}

Several forms of networks (long-haul networks, modems, cell phones),
and of medium to long term storage (DRAM, hard drives, backup tapes)
are susceptible to data corruption by noise in the environment.  Such
corruption often manifests as random, independent bit errors, which
can be protected against by a class of linear block codes known as
error correction codes.  In brief, such codes append a certain number
of redundant bits (which are a linear combination of the bits of the
input block) to a transfer block; the receiver then checks the
redundant bits against the input to determine whether there has been
an error in transmission, and can sometimes correct the error.  One
can visualize the algorithm as placing the correct blocks as points in
an $n$-dimensional space; then, any block within a certain
``distance'' of a correct block can be corrected, and any block
outside all the n-spheres thus defined are uncorrectable.  Thus, in
general, it is straightforward to find a linear encoding which can
correct up to $t$ errors, or detect up to $2t$ errors.

The encoding process is quite efficient:  it requires an $n-k$ by $k$
matrix to be applied to a $k$-vector input block.  All arithmetic is
mod 2, and so can be implemented with ANDs and XORs.  However,
decoding requires a same-size multiplication, but also requires an
$(n-k)$-bit table lookup for error correcting:  this can easily
outstrip memory resources if the redundant block size $n$ is large.


\section{General majority-vote fault-tolerance}

Transmitting redundant bits using error correcting codes is sufficient
to protect against random, independent bit errors in storage and
network elements; however, in the presence of correlated errors and
unpredictably faulty computational elements, a more general solution
in necessary.  The problem can be expressed like this: imagine that a
group of generals of the Byzantine army are camped around an enemy
city, communicating only by messenger, and are deciding whether to
attack, or to retreat.  However, the situation is complicated by the
fact that some of them may be traitors, and they can't tell which.
They must ensure that
\begin{enumerate}
\item All loyal generals decide upon the same plan of action, and
\item A small number of traitors cannot cause the loyal generals to
adopt a bad plan.
\end{enumerate}
Note that the ``traitorous'' faulty components might conspire or only
lie some of the time:  the model allows for any sort of correlated
errors, or even for malicious intelligences working against the
system.

The solution to this most general problem is, essentially, a form of
majority voting.  For Alice to tell all the other generals ``we should
retreat!'', Alice first sends a message to every other general, saying
``Alive says: we should retreat!''  This, however, doesn't satisfy the
generals, since Alice might be a traitor, telling Bob ``we should
retreat!'' and telling Carl ``we should attack!''  Thus, every other
general (for example, Bob) tells every other general ``Bob says: Alice
says we should retreat.''  But again, we run into the same problem,
and hence each general chimes in with ``Dave says: Bob says Alice says
we should retreat'' and ``Dave says: Carl says Alice says we should
attack.''

The recursion finally bottoms out at $n$ levels deep, where $n$ is the
number of units, since one processors is left out at every level of
recursion: Bob need not send a message ``Bob says: Bob says Alice says
we should retreat''.  At that point, every processor takes for granted
the statement received (which is similar to ``Zed says Yak says\dots
Bob says Alice says we should retreat'') and performs a majority vote
to determine the ``true'' next-level statement.  In other words, if
both Zed and Zach say ``Yak says\dots Bob says Alice says we should
retreat'', but Zeeb says ``Yak says\dots Bob says Alice says we should
attack'', the unit decides that Zed and Zach are right.  This process
is used to climb the recursion tree, until, at the top of the chain,
there is a final result: ``Alice says we should retreat.''

Given the strong assumption of {\em perfect connectivity} among the
generals (each general can send messages to any other general, and no
general can pretend to be another), this procedure is guaranteed to
result in agreement among all the loyal generals so long as no more
than 1/3 of the generals are traitors.  The algorithm can be modified
to cope with incomplete connectivity, so long as the subgraph of loyal
generals is connected (otherwise, there would be no way to get a
message from one loyal connected component to another).  Also, if
signed, unforgeable messages can be used, any number of faulty
processors can be dealt with, and many of the inefficiencies and
details of the procedure can be smoothed over.

Although the theoretical result is a proof of perfect operation, any
implementation of the algorithm is still not perfectly fault-tolerant,
because the proof relies on strong assumptions which are not true
100\% of the time in a non-perfect system.  In real systems, one must
worry about:
\begin{enumerate}
\item Lack of complete connectivity in any practical system.
\item Clock skew: synchronization is an entire fault-prone system in
itself.
\item With nonzero probability, more than 1/3 of the nodes will be
faulty.
\item If signed messages are used, there is always a non-zero
probability of a signed message being correctly forged, either
accidentally or maliciously.
\end{enumerate}


\section{Conclusion:  The Real World}

Real fault-tolerant (in buzzword jargon, ``ultrareliable'') systems
use all of the techniques of redundant routing, ECC, and majority
voting in various subsystems; it's a proven technology.  Most
practical implementations of majority voting use simpler, more
efficient mechanisms that that outlined above, however.  A common
implementation is to use an arbitrator to count the votes and
determine the correct result; however, care must be taken to ensure
that the arbitrator itself is fault-tolerant.

Current systems tend to focus on software techniques, such as
transactions, assertions, periodic consistency audits, and pervasive
timeouts to attain high uptimes; in general, defensive programming is
becoming an ever-more-important tool.  Along these lines, most of the
research into fault tolerance today seems to focus on the deplorably
fact that most faults are due to design errors, programmer errors, and
operator error, rather than noise or defects, which are adequately
defended against by the techniques outlined above.  For example, tools
are being developed to perform automated logic checking on programs,
determining if a program actually does what its designer intended it
to do.  Finally, this problem is ultimately human in origin, and the
optimal solutions are also human in nature: an effective technique is
to have multiple development teams independently design programs to
perform a certain task, and then use majority voting on the results of
the different programs in the actual production system.  Such
techniques are used in systems where reliability is critical, such as
life support.


\newpage


\begin{thebibliography}{9}
\bibitem{ecc}
Shu Lin.  \textsl{An Introduction to Error-Correcting Codes}.
Prentice-Hall, Englewood Cliffs, NJ, 1970, 330pp, pp. 33-57.

\bibitem{teramac}
James R. Heath, Philip J. Kuekes, Gregory S. Snider, R. Stanley Williams.
\textsl{A Defect-Tolerant Computer Architecture:
        Opportunities for Nanotechnology}.
Science, Vol. 280, 12 June 1998, pp. 1716-1721.

\bibitem{byz}
Leslie Lamport, Robert Shostak, Marshall Pease.
\textsl{The Byzantine Generals Problem}.
ACM Transactions on Programming Languages and Systems,
Vol. 4, No. 3, July 1982, pp. 382-401.


\end{thebibliography}


\end{document}



