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

\movedUpBody{-0.75in}{\Brown{The Re-execution Problem}}
\vspace{0.3in}
\begin{center}
	\begin{figure*}
	\epsfxsize=5.6in
	\centerline{\epsfbox{Figures/204.eps}}
	\end{figure*}
\vspace{0.2in}
\begin{tabbing}
xxxxxx\= xxxxx\= xxxxxxxxxxxxxxxxxxxxxxxxxx\= \kill
\>{\bf The Re-execution Problem:}\\
\> To re-execute in order to avoid a recurrence of a previously \\
\> detected failure\\ 
\end{tabbing}
\end{center}

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

\movedUpBody{-0.75in}{\Brown{Re-execution Approaches}}
\vspace{0.5in}
\begin{center}
\begin{tabbing}
xxxxxx\= xxxxx\=\kill
\>$\bullet$ {\bf Computation Divergence Approach:}\\
\>\>$-$ based on inherent program non-determinism\\
\>\>$-$ assumes no knowledge of fault\\
\>\>$-$ gives no guarantees\\ 
\>\>$-$ e.g. Progressive Retry \ \ \MidnightBlue{[Wang et al, 97]}\\ [0.4in]
\>$\bullet$ {\bf Computation Correction Approach:}\\
\>\>$-$ based on added {\em control\/} \\
\>\>$-$ assumes some knowledge of fault\\
\>\>$-$ gives guarantees\\
\>\>$-$ e.g. Controlled Re-execution \ \  \MidnightBlue{[Tarafdar \& Garg 99]}\\[0.3in]
\>{\bf Note:} Approaches are orthogonal
\end{tabbing}
\end{center}

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

\movedUpBody{-0.75in}{\Brown{Races}}
\vspace{0.5in}
\begin{center}
	\begin{figure*}
	\epsfxsize=7.0in
	\centerline{\epsfbox{Figures/16.eps}}
	\end{figure*}
\end{center}
\begin{tabbing}
xxxxxx\= xxxxx\=\kill
\> A {\bf race\/} occurs when two processes can concurrently access \\
\> the same shared resource.\\ \\
\> Example: concurrent writes to a shared file 
\end{tabbing}

%-------------------------------------------------------------------------------
\movedUpBody{-0.75in}{\Brown{Re-execution Techniques}}
\vspace{0.3in}
	\begin{figure*}
	\epsfxsize=7.5in
	\centerline{\epsfbox{Figures/215.eps}}
	\end{figure*}

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

\movedUpBody{-0.75in}{\Brown{Controlled Re-execution}}
\vspace{0.5in}
	\begin{figure*}
	\epsfxsize=7.5in
	\centerline{\epsfbox{Figures/216.eps}}
	\end{figure*}
\vspace{0.3in}
\begin{tabbing}
xxxxxx\= xxxxx\=\kill
\> {\bf Assumptions:}\\[0.2in]
\>\> $\bullet$ Synchronizations and shared resource accesses can be traced.\\[0.1in]
\>\> $\bullet$ Shared resources are write-only.\\[0.3in]
\> {\bf Problem:} How is a control strategy determined?
\end{tabbing}


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

\movedUpBody{-0.75in}{\Brown{Off-line Mutual Exclusion}}
\vspace{0.5in}
\begin{center}
	\begin{figure*}
	\epsfxsize=7.5in
	\centerline{\epsfbox{Figures/20.eps}}
	\end{figure*}
\vspace{0.5in}
\begin{tabbing}
xxxxxx\= xxxxx\=\kill
\>{\bf Problem Statement:}\\ [0.2in]
\> Given a computation $C$, find a controlling computation $C'$ of $C$\\
\> such that all consistent global states in $C'$ satisfy mutual exclusion.
\end{tabbing}
\end{center}
%-------------------------------------------------------------------------------

\movedUpBody{-0.75in}{\Brown{Variants of Off-line Mutual Exclusion}}
\vspace{1.0in}
\begin{center}
	\begin{figure*}
	\epsfxsize=9.0in
	\centerline{\epsfbox{Figures/21.eps}}
	\end{figure*}
\end{center}
%-------------------------------------------------------------------------------

\movedUpBody{-0.75in}{\Brown{A Precedence Relation on Critical Sections}}
\vspace{0.5in}
\begin{center}
	\begin{figure*}
	\epsfxsize=7.0in
	\centerline{\epsfbox{Figures/22.eps}}
	\end{figure*}
\end{center}
%-------------------------------------------------------------------------------

\movedUpBody{-0.75in}{\Brown{Solving Off-line Mutual Exclusion}}
\vspace{0.3in}
\begin{tabbing}
xxxxxx\= xxxxx\=\kill
\>{\bf Theorem:\/} \ \ \ \MidnightBlue{[Tarafdar \& Garg 99]}\\
\>A controlling computation of a computation $C$ exists {\bf iff} \\
\>the precedence relation for $C$ contains no cycles.\\ [0.3in]
\>{\bf Direct Algorithm:\/}\\
\>\>$\bullet$ topologically sort precedence graph of critical sections\\
\>\>$\bullet$ add control synchronizations in sorted order\\
\>\>$\bullet$ $O(p^2)$ \ \ ($p$: number of critical sections in computation)
\end{tabbing}
	\begin{figure*}
	\epsfxsize=3.7in
	\centerline{\epsfbox{Figures/218.eps}}
	\end{figure*}
%-------------------------------------------------------------------------------

\movedUpBody{-0.75in}{\Brown{Solving Off-line Mutual Exclusion}}
\vspace{0.2in}
\begin{center}
	\begin{figure*}
	\epsfxsize=3.7in
	\centerline{\epsfbox{Figures/219.eps}}
	\end{figure*}
\begin{tabbing}
xxxxxx\= xxxxx\=\kill
\>{\bf Improved Algorithm:\/}\\
\>\>$\bullet$ Key idea: use process ordering of critical sections\\
\>\>$\bullet$ $O(p^2) \  \rightarrow \  O(n^2p)$ \ \ (further reducible to $O(np)$) \\ [0.2in]
\>$n$: number of processes\\
\>$p$: number of critical section in computation
\end{tabbing}
\end{center}
%-------------------------------------------------------------------------------

\movedUpBody{-0.75in}{\Brown{Extending Off-line Mutual Exclusion}}
\vspace{0.3in}
\begin{center}
	\begin{figure*}
	\epsfxsize=3.7in
	\centerline{\epsfbox{Figures/220.eps}}
	\end{figure*}
\vspace{0.2in}
\begin{tabbing}
xxxxxx\= xxxxx\=\kill
\>To allow {\bf independent} and {\bf read/write} critical sections.\\[0.3in]
\>{\bf Extended Algorithm:\/}\\
\>\>$\bullet$ Key idea: critical sections in the same SCC are {\em safe\/}.\\
\>\>$\bullet$ Similar optimization leads to $O(np)$ algorithm.
\end{tabbing}
\end{center}
%-------------------------------------------------------------------------------

\movedUpBody{-0.75in}{\Brown{Experiments}}
\vspace{0.2in}
\begin{center}
\begin{tabbing}
xxxxxx\= xxxxx\= xxx\= \kill
\> {\bf Aim:}\\
\>\> $\bullet$ To evaluate controlled re-execution with respect to simple and \\
\>\> \hspace{0.3in} locked re-execution.\\[0.3in]
\> {\bf Setting:}\\
\>\> $\bullet$ Cluster of 4 Sun Ultra10 workstations running Solaris \\
\>\> $\bullet$ Synchronization: blocking message passing using MPI\\
\>\> $\bullet$ Shared resources: files in a network file system\\
\>\> $\bullet$ Shared accesses: synchronous writes
\end{tabbing}
\end{center}
%-------------------------------------------------------------------------------

\movedUpBody{-0.75in}{\Brown{Experiments}}
\vspace{0.2in}
\begin{center}
\begin{tabbing}
xxxxxx\= xxxxx\= xxx\= \kill
\> {\bf Applications:}\\
\>\> $\bullet$ Synthetically generated MPI applications.\\
\>\> $\bullet$ Parameters based on NPB 2.1 Parallel Benchmark.\\
\>\> $\bullet$ Randomly generated communication and file access patterns.\\[0.3in]
\> {\bf Parameters:}\\
\>\> $\bullet$ mean time between communication events. \\
\>\> $\bullet$ mean time between critical sections. \\[0.3in]
\> {\bf Metrics:}\\
\>\> $\bullet$ Tracing overhead: time and space.\\
\>\> $\bullet$ Mean time to failure for:\\
\>\>\> $-$ races in simple re-execution\\
\>\>\> $-$ deadlocks in locked re-execution\\
\>\>\> $-$ cycles in controlled re-execution
\end{tabbing}
\end{center}
%-------------------------------------------------------------------------------

\movedUpBody{-0.75in}{\Brown{Tracing Overhead}}
\vspace{0.2in}
\begin{center}
\begin{tabbing}
xxxxxx\= xxxxx\= xxx\= \kill
\> {\bf Tracing Overhead:}\\[0.3in]
\>\> $\bullet$ average inter-arrivals for messages = 10ms\\
\>\> $\bullet$ average time between critical sections = 100ms \\
\>\> $\bullet$ run for 1 hour\\\\
\>\> {\bf Time Overhead} = 90ms (0.0025\%)\\
\>\> {\bf Space Overhead} =  5.62 MB 
\end{tabbing}
\end{center}
%-------------------------------------------------------------------------------

\movedUpBody{-0.75in}{\Brown{Results}}
\begin{center}
	\begin{figure*}
	\epsfxsize=7.3in
	\centerline{\epsfbox{Figures/graph1.ps}}
	\end{figure*}
\end{center}
%-------------------------------------------------------------------------------

\movedUpBody{-0.75in}{\Brown{Generalization}}
\vspace{0.2in}
\begin{center}
	\begin{figure*}
	\epsfxsize=7.0in
	\centerline{\epsfbox{Figures/20.eps}}
	\end{figure*}
\vspace{0.2in}
\begin{tabbing}
xxxxxx\= xxxxx\= xxx\= \kill
\>{\bf The Off-line Mutual Exclusion Problem:}  (for races)\\ [0.1in]
\> Given a computation $C$, find a controlling computation $C'$ of $C$\\
\> such that all consistent global states in $C'$ satisfy \Red{mutual exclusion}.\\ [0.3in]
\>{\bf The Predicate Control Problem:}  (for synchronization faults)\\ [0.1in]
\> Given a computation $C$, find a controlling computation $C'$ of $C$\\
\> such that all consistent global states in $C'$ satisfy \Red{global predicate $B$}.\\ 
\end{tabbing}
\end{center}
%-------------------------------------------------------------------------------

\movedUpBody{-0.75in}{\Brown{Predicate Control}}
\vspace{0.5in}
\begin{center}
\begin{tabbing}
xxxxxx\= xxxxx\= xxxxxxxxxxxxxxxxxxxxxxxx\=xxxxxxxxxxxxxxxx\= \kill
\>{\bf Theorem:\/} The Predicate Control Problem is NP-Hard.\\
\>\>\>\>\MidnightBlue{[Tarafdar \& Garg 98]}\\[0.4in]
\>{\bf Results:\/}\\[0.2in]
\>\>$\bullet$ mutual exclusion \>\MidnightBlue{[Tarafdar \& Garg 99]}\\[0.1in]
\>\>$\bullet$ disjunctive predicates \>\MidnightBlue{[Tarafdar \& Garg 98]}\\[0.1in]
\>\>$\bullet$ interval predicates \>\MidnightBlue{[Mittal \& Garg 00]}\\[0.4in]
\>{\bf Applications:\/}\\[0.2in]
\>\>$\bullet$ Software fault tolerance\\[0.1in]
\>\>$\bullet$ Distributed debugging\\[0.1in]
\>\>$\bullet$ Off-line scheduling
\end{tabbing}
\end{center}
%-------------------------------------------------------------------------------
