%-------------------------------------------------------------------------------
\movedUpBody{-0.75in}{\Brown{Software Faults}}
\vspace{0.5in}
\begin{center}
%\centerline{\epsfxsize=5.0in \epsffile{Figures/201.eps}}
	\begin{figure*}
	\epsfxsize=5.0in
	\centerline{\epsfbox{Figures/201.eps}}
	\end{figure*}
{\small \% of outages by fault category (30,000 system years)}
\end{center}
\vspace{0.2in}
\hspace{0.7in} $\bullet$ Software faults are increasingly dominant\\
\hspace{0.7in} $\bullet$ $\approx$ 3 bugs per 1000 lines of code! \ \ \ \MidnightBlue{[Gray \& Reuter 93]}

%-------------------------------------------------------------------------------
\movedUpBody{-0.75in}{\Brown{Traditional Rollback Recovery in Distributed Systems}}
\vspace{0.3in}
\begin{center}
	\begin{figure*}
	\epsfxsize=5.7in
	\centerline{\epsfbox{Figures/202.eps}}
	\end{figure*}
\begin{tabbing}
xxxxxx\= xxxxx\= xxxxxxxxxxxxxxxxxxxxxxxxxx\= \kill
\> Three phases: \\
\>\>$\bullet$ {\bf Detection:} process crash detection\\
\>\>$\bullet$ {\bf Restoration:} {\em maximum recoverable (consistent) state\/} \\
\>\>$\bullet$ {\bf Re-execution:} simple \\[0.2in]
\> Assumptions: failstop, independent failures
\end{tabbing}
\end{center}

%-------------------------------------------------------------------------------

\movedUpBody{-0.75in}{\Brown{Synchronization Faults}}
\vspace{0.2in}
\begin{tabbing}
xxxxxx\= xxxxx\= xxxxxxxxxxxxxxxxxxxxxxxxxx\= \kill
\> $\bullet$ A {\em synchronization fault\/} is a fault whose occurrence depends on\\  
\> $\mbox{\hspace{12pt}}$ the relative timing among processes. e.g. races, load imbalance.
\end{tabbing}
\vspace{0.3in}

\centerline{\epsfxsize=4.8in \epsffile{Figures/101.eps}}

\vspace{0.1in}

\begin{tabbing}
xxxxxx\= xxxxx\= xxxxxxxxxxxxxxxxxxxxxxxxxx\= \kill
\> $\bullet$ Suitable for rollback recovery. \\[3pt]
\> $\bullet$ Difficult to eliminate during testing.
\end{tabbing}

%-------------------------------------------------------------------------------
\movedUpBody{-0.75in}{\Brown{Detection}}
\vspace{0.2in}
\begin{center}
\begin{tabbing}
xxxxxx\= xxxxx\= xxxxxxxxxxxxxxxxxxxxxxxxxx\= \kill
\> $\bullet$ Monitoring for global conditions: {\em predicates\/}.\\[0.1in]
\> $\bullet$ Example: race
\end{tabbing}
	\begin{figure*}
	\epsfxsize=4.0in
	\centerline{\epsfbox{Figures/103.eps}}
	\end{figure*}
\vspace{0.4in}
\begin{tabbing}
\= xxxxx\= xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\= \kill
{\bf Predicate Detection Problem:} \MidnightBlue{[Cooper \& Marzullo 91,Garg \& Waldecker 91]}\\ [5pt]
To detect a consistent state satisfying a given predicate.
\end{tabbing}
\end{center}

%-------------------------------------------------------------------------------

\movedUpBody{-0.75in}{\Brown{Restoration}}
\vspace{0.1in}
\begin{center}
\begin{tabbing}
xxxxxx\= xxxxx\= xxxxxxxxxxxxxxxxxxxxxxxxxx\= \kill
\> $\bullet$ Failures are not failstop: failure latency\\
\> $\bullet$ Which state to restore? \ \  \MidnightBlue{[Wang et al 97], [Chandra \& Chen 98]}
\end{tabbing}
\vspace{0.1in}
	\begin{figure*}
	\epsfxsize=3.6in
	\centerline{\epsfbox{Figures/102.eps}}
	\end{figure*}
\begin{tabbing}
xxxxxx\= xxxxx\= xxxxxxxxxxxxxxxxxxxxxxxxxx\= \kill
\> $\bullet$ Traditional rollback recovery can be applied:\\[2pt]
\>\> $-$ Coordinated checkpointing \ \ \MidnightBlue{[Chandy \& Lamport 85]}\\[1pt]
\>\> $-$ Optimistic logging  \ \ \MidnightBlue{[Strom \& Yemini 85]}\\[1pt]
\>\> $-$ Causal logging  \ \ \MidnightBlue{[Alvisi et al, 93], [Elnozahy \& Zwaenepoel 92] }
\end{tabbing}
\end{center}

%-------------------------------------------------------------------------------

\movedUpBody{-0.75in}{\Brown{Re-execution}}
\vspace{0.2in}
\begin{tabbing}
xxxxxx\= xxxxx\= xxxxxxxxxxxxxxxxxxxxxxxxxx\= \kill
\> $\bullet$ Failures are not independent\\
\> $\bullet$ Re-execute in order to avoid a recurrence of a failure\\
\> $\bullet$ {\em Controlled Re-execution\/} for synchronization faults 
\end{tabbing}
\begin{center}
	\begin{figure*}
	\epsfxsize=4.5in
	\centerline{\epsfbox{Figures/104.eps}}
	\end{figure*}
\vspace{0.4in}
\begin{tabbing}
xxxxxx\= xxxxx\= xxxxxxxxxxxxxxxxxxxxxxxxxx\= \kill
\>{\bf Predicate Control Problem:} \ \ \MidnightBlue{[Tarafdar \& Garg 98]}\\
\> To add synchronizations so that all consistent states satisfy \\
\> a given predicate.
\end{tabbing}
\end{center}

%-------------------------------------------------------------------------------

\movedUpBody{-0.75in}{\Brown{Talk Outline}}
\vspace{1.0in}
\begin{tabbing}
xxxxxx\= xxxxx\= xxxxxxxxxxxxxxxxxxxxxxxxxx\= \kill
\>$\bullet$ Model\\ \ \\
\>$\bullet$ Predicate Control Problem\\ \ \\
\>$\bullet$ Predicate Detection Problem\\ \ \\
\>$\bullet$ Controlled Re-execution: An Experimental Study \\ \ \\
\>$\bullet$ Conclusions
\end{tabbing}
%-------------------------------------------------------------------------------
