% $Id: challenges.tex,v 1.14 2006/04/14 22:59:58 gokhale Exp $

\section{Design Challenges for Fault-tolerant Mission-Critical Systems}
\label{sec:challenges}

In this section we describe the challenges faced designing and
developing fault tolerant infrastructure for mission critical DRE
systems.  To better enable us to describe the challenges and our
solutions (described in Section~\ref{sec:arch}), we focus on a
representative DRE system we are currently working on as part of the
DARPA Adaptive and Reflective Middleware (ARMS) program.  The DARPA
ARMS program is seeking solutions to dynamic resource management in
mission critical systems. 

\subsection{DRE System Case Study}
\label{sec:case-study}


Our DRE system provides dynamic resource management capabilities
to applications running in a large mission critical environment.
Since the application mix in our domain comprises mission critical
entities, the resource management infrastructure is responsible for
making real-time resource management decisions.
Figure~\ref{fig:mlrm-arch} illustrates our DRE dynamic resource 
manager~\cite{Campbell-MoDES:04,Schmidt:05ee}.  It is a multi-layered
architecture that translates high level operational requirements into
the sets of applications that must be run and their real-time
requirements, and maps the applications (grouped into end-to-end
application strings) over computational and communication resources.
We will refer to this multi layered architecture as a Multi-Layered
Resource Management (MLRM) framework.  The MLRM system adjusts the
resource allocations as resource availability changes (e.g., due to
failures), to accommodate for system load, or to satisfy changing
operational requirements.  

\begin{figure}[!htb]
  \centering
  \includegraphics[width=0.6\columnwidth,keepaspectratio]{arch}%
  \caption{MLRM Architecture}
  \label{fig:mlrm-arch}
\end{figure}

The MLRM is implemented using a number of base technologies including
CIAO~\cite{Schmidt:03m}, which is a C++ implementation of the
lightweight CORBA  Component Model (CCM)~\cite{LWCCM};
OpenCCM~\cite{OPEN-CCM}, which is a Java implementation of CCM;
real-time CORBA ORBs, such as TAO~\cite{Schmidt:02g}; Java ORBs, such
as JacORB~\cite{JacORB:97}, and non-CORBA technologies, such as MySQL
databases, and the MEAD~\cite{Mead:CCPE} replica management framework.

\subsection{Fault Model for MLRM}
\label{sec:ft-model}

In designing our FT solution we assume that all faults are fail-stop
at the process level, {\em i.e.}, when an application process fails it
stops communicating and does not obstruct the normal functioning of
other unrelated applications.  Network and host failures can be seen as
a collection of process failures on the network or host that has
failed.  Some examples of failures that we will tolerate include power
being disrupted to a host, an application crashing, or a data center
being destroyed.  Some examples of failures that we do not currently
tolerate are network partitioning, where only parts of the network
fail, leaving two groups of uncoordinated replicas, and malicious or
%%PGR added byzantinecite
Byzantine~\cite{lamport:byzantine} failures where a process may
intentionally attempt to deceive other members or misrepresent data.



%%PGR This doesn't seem relavent at this point, better to trim it.

%-%-%  Measuring the time it takes to deal with a failure can be thought of
%-%-%  as comprising two periods. The first is fault-detection, where we note
%-%-%  that a failure occurred.  The second is recovery, which is the time
%-%-%  between noting the fault and dealing with it in such a manner that the
%-%-%  system can again deal with messages.  We note the sum of these as the
%-%-%  failover time. 
%-%-%  % (Note that in some cases, such as active replication, failover
%-%-%  % is not strictly correct, we are searching for a new term 
%-%-%  % <ANDY, this needs help>.) 
%-%-%  
%-%-%  In the case of active replication detection and recovery happen nearly
%-%-%  instantaneously. When the GCS system comes to an agreement about the
%-%-%  current group membership the active replicas can immediately begin to
%-%-%  process message that have been queuing up during the failure
%-%-%  detection. In passive replication there is a measurable time between
%-%-%  notification and recovery where replicas promote a new master and
%-%-%  possible replay buffered messages. 
%-%-%  
\subsection{FT Challenges in DRE Systems}
\label{sec:ft-challenges}

The MLRM is a crucial piece of our mission critical system
and must be made fault tolerant, however, illustrates a number of {\em
  crosscutting concerns}  described below that affect the strategies
that we must employ in order to make it fault tolerant: 

\vspace{-0.1in}
\paragraph{\bf 1. Nearly continuous availability.}
The MLRM must be nearly continuously operational.  This means
that faults must be {\em masked} or any failover time must be very
small.  This motivated the use of active replication wherever possible
since it offers continuous availability.  However, since active
replication has limitations in the case of non determinism, this
strategy must interwork seamlessly with other solutions that deal with
non-determinism. 

\vspace{-0.1in}
\paragraph{\bf 2. Dealing with non-determinism.}
Some of the elements of MLRM, such as the bandwidth broker (BB) are
fairly deterministic, while others are necessarily nondeterministic,
including multi-threading, file I/O, and other nondeterministic
functionality.  The replication styles used must therefore address
these challenges.

\vspace{-0.1in}
\paragraph{\bf 3. Layered FT capabilities with minimal impact.}
%%PGR changed the ending here
In the layered architecture of the MLRM shown in
Figure~\ref{fig:mlrm-arch}, the top-level MLRM elements had to be made
fault tolerant without requiring all elements in the system to be
affected.  The MLRM system has hundreds of elements at the bottom
level, i.e., at the node layer, as well as potentially thousands of
applications that it is deploying.  These elements should be affected
by the fault tolerance infrastructure of the MLRM, e.g., by being
forced to use group communication systems (GCS), required by the
applications that interact with the top-level MLRM elements, but
unnecessary for those that do not.  This necessitates co-existence of
GCS and non-GCS frameworks.

\vspace{-0.1in}
\paragraph{\bf 4. Non-traditional communication patterns.}
The MLRM has multi-tier and peer-to-peer communication
patterns.  That is, many of the elements act as both clients and
servers throughout the MLRM operation, sometimes simultaneously.
The FT design must therefore be able to handle interactions that are 
much more complicated than traditional client-server CORBA systems.  
For example, one unexpected interaction that required special attention
was a case where two processes had {\it both} client and server
connections to each other (i.e. there was a cyclic dependency between 
the applications caused by callbacks). %%PGR%% added a bit

\vspace{-0.1in}
\paragraph{\bf 5. Multi-language, multi-platform environment.}
The MLRM is implemented as a mix of C++ and Java elements.  Moreover,
the system is made up of elements using the component middleware
technologies, such as the C++ CIAO and Java OpenCCM implementations,
elements that use both CORBA and non-CORBA elements, such as MySQL
databases and MEAD, which is a library that uses procedural semantics.
The FT design must account for this heterogeneity when dealing with
replica reconstitution and state synchronization in the presence of
GCS and non-GCS communication patterns. 

\vspace{-0.1in}
\paragraph{\bf 6. Statefulness of MLRM.}
%%PGR %%
When starting a new replica it is imperative that the new replica is
prepared to behave exactly as an existing replica.  Even if the
application being replicated is stateless the middleware does need to
transfer state from existing to new replicas. Thus, when a new replica
is added into a group, there is a need for consistent state
management, which works seamlessly in the face of heterogeneity.  
%%PGR I didn't get this part.
%%-%%The
%%-%%application may for stateful elements while honoring the communication
%%-%%patterns between stateful and stateless elements, and impact on the
%%-%%infrastructure hosting the stateless elements.

\vspace{-0.1in}
\paragraph{\bf 7. Fault detection in multi layered architecture.}
When we inject failures (say during testing) into the system the time
of fault injection is easy to note.  Differentiating detection from
recovery, however, is not as easy. Our FT middleware solution makes
use of the Spread GCS system~\cite{Amir:Spread} for notification of
failure.  The middleware level of our system becomes aware of the
failure when Spread notifies existing replicas.  However, Spread must
have been aware of the failure at least a small amount of time before
it reported to the FT middleware so getting a precise detection time
is non-trivial. 
%%PGR slight change here, still not entirely satisfied

\smallskip\noindent
Section~\ref{sec:arch} describes our reusable FT infrastructure that
addresses the challenges outlined above.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "middleware-2006"
%%% End: 
