\documentclass[aspectratio=169,usenames,dvipsnames,table,10pt,t]{beamer}
\usepackage{etoolbox}
\usepackage{lmodern}
\usepackage{tikz}
%\usepackage[utf8]{inputenc}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage{graphicx}
\usepackage{float}
\usepackage{subfig}
\usepackage[none]{hyphenat}
%\usepackage[percent]{overpic}
\usepackage{tabu, booktabs, multirow, multicol}
\usepackage[export]{adjustbox}
\usepackage{multicol}
\usepackage{cleveref}
\usetikzlibrary{shapes.geometric, shapes.misc, fadings, arrows.meta, positioning, backgrounds, fit, matrix}
\usetheme{Simple}
\hypersetup{unicode=true, pdfpagemode=UseNone}

\makeatletter
\patchcmd{\@listI}{\topsep3\p@}{\topsep2ex}{}{}
\makeatother
\algnewcommand{\IfThenElse}[3]{% \IfThenElse{<if>}{<then>}{<else>}
    \State \algorithmicif\ #1\ \algorithmicthen\ #2\ \algorithmicelse\ #3
}

\taburowcolors[2] 2{themecolorlight .. themecolorultralight}
\tabulinesep = ^1.5mm_1.5mm
\newcommand{\firstrow}{
	\rowfont{\leavevmode\bfseries\color{white}}\rowcolor{themecolor}
}

\newcommand{\mysource}[1]{\par\hfill \footnotesize Source:~\itshape#1}
\input{preamble}

\title{Fault Tolerance in Linear Algebraic Methods using Erasure Coded Computations}
\subtitle{Ph.D. Final Defense}
\author{Xuejiao Kang}
\advisor{Ananth Grama}
\institute{Department of\\Computer Science}
\date{November 26, 2018}
\titlegraphic{\includegraphics[width=\paperwidth]{figures/hard-drive.jpg}}
\logo{\includegraphics[height=6mm]{figures/Purdue-Sig-Black-Gold-rgb}}

\begin{document}
\frame[noframenumbering]{\maketitle}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}
% \frametitle{Timeline}
% \label{timeline}
% \begin{itemize}
% 	\vspace{-0.5cm}
% 	\item  \Large Joined Ph.D. program in Fall 2012
% 	\vspace{0.5cm}
% 	\item  \Large Completed Qual 1 in Fall 2013
% 	\vspace{0.5cm}
% 	\item  \Large Completed Qual 2 in Fall 2014
% 	\vspace{0.5cm}
% 	\item  \Large Preliminary Exam in Spring 2017
%     \vspace{0.5cm}
% 	\item  \Large Final Defense in Fall 2018
% \end{itemize}
% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}
% \frametitle{Selected Publications}
% \label{publication}
% \begin{itemize}
% 	\item \textbf{Xuejiao Kang} , David F. Gleich , Ahmed Sameh  and Ananth Grama. Distributed Fault Tolerant Linear System Solvers based on Erasure Coding(\textbf{ICDCS17})
% 	\vspace{0.3cm}
% 	\item Woong-Hee Shin, \textbf{Xuejiao Kang}, Jian Zhang, and Daisuke Kahara. Prediction of local quality of protein structure models considering spatial neighbors in graphical models. \textbf{Scientific Reports, 7:40629,2017 (Co-FirstAuthor)}
% 	\vspace{0.3cm}
% 	\item Lenna X. Peterson, \textbf{Xuejiao Kang}, and Daisuke Kahara. Assessment of protein side-chain conformation prediction accuracy in different residue environments. \textbf{Proteins: Structure, Function, and Bioinformatics, 82: 1971-1984 (2014)}
% \end{itemize}
% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Background and Motivation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Faults in Parallel and Distributed System}
\begin{itemize}
\item As parallel \alert{systems} scale to millions of cores, faults become one of the most critical challenges.
\vspace{0.25cm}
\item As  \alert{data} centers scale to hundreds of thousands of nodes, faults are a prime consideration for distributed computations.
\vspace{0.25cm}
\item As  \alert{networks} scale from data center to wide area, network faults and partitions constitute a major consideration for wide area distributed computations.
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Estimated Chip Counts in Exascale Systems}
\begin{figure}
\vspace{-0.3cm}
\includegraphics[scale=0.55]{./figures/chipcounts.png} 
\mysource{DARPA Exascale Technology Study [Kogge et al.]}
%\source{\tiny DARPA Exascale Technology Study [Kogge et al.]
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{BlueGene Failure In Time (FIT) budget}
\begin{figure}
\includegraphics[scale=0.55]{./figures/failurerate.png} 
\mysource{P. COTEUS ET AL., IBM J. RES. \& DEV. VOL. 49 NO. 2/3}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Scaling trends for environmental factors that affect resiliency}
\vspace{-0.4cm}
\begin{figure}
%\text{Mean Time to Interrupt for different fault rates.}
\includegraphics[height=0.7\textheight]{./figures/mtti.png}
\mysource{DARPA Exascale Technology Study [Kogge et al.}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Application Utilization for checkpoint overheads}
\vspace{-1cm}
\begin{figure}
\text{If one socket fails on average \alert{every 10 years}, application utilization drops to \alert{0 at 220K sockets!}}
\includegraphics[height=0.75\textheight]{./figures/utilization.png}
\mysource{DARPA Exascale Technology Study [Kogge et al.}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Fault and Failure Models}

\begin{block}{Types of Fault}
    (i) Permanent; \qquad \qquad (ii) Transient;  \qquad \qquad (iii) Intermittent.
\end{block}

\begin{block}{Failure Model}
Failure model is an abstraction of system behavior in the presence of a fault.
\end{block}

\begin{itemize}
\item Byzantine: a component can exhibit \alert{arbitrary and malicious behavior}, perhaps involving collusion with other faulty components. 
\vspace{0.2cm}
\item Fail-stop: a component changes to a \alert{state} that permits other components to \alert{detect} the failure and then \alert{stops}. 
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}{Fault Tolerance}
% \begin{itemize}
% \item Fault tolerance becomes increasingly important as parallel and distributed system scale.
% \vspace{0.2cm}
% \item Combined with potential constraints on storage capacity, these problems are still particularly challenging.
% \vspace{0.2cm}
% \item Existing solutions do not straight-forwardly address the problem.
% \end{itemize}
% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Fault Tolerance}
\alert{Algorithm-based} methods and \alert{System-supported} methods. 
\begin{itemize}
\item Algorithmic methods alter the algorithm to make it robust to faults.
\vspace{0.3cm}
\item System-supported methods include checkpoint-restart, active replicas and deterministic replay. 
\vspace{0.2cm}
\begin{itemize}
\item Checkpoint-restart schemes involve the overhead of consistent checkpointing and I/O.
\vspace{0.2cm}
\item Active replicas execute multiple replicas of each task.
\vspace{0.2cm}
\item Tasks in deterministic replay are scheduled at different execution units and monitored for successful completion. They are rescheduled at other execution units if failures are detected.
\end{itemize}
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Error Correcting Codes}
Error Correcting Codes are commonly used in communication systems. Messages are coded (augmented) with error correction (redundant) bits, which can help detect and correct transmission errors.
\vspace{-1.0cm}
\begin{columns}
\hspace{0.2cm}
\column{0.3\textwidth}
\begin{figure}
\includegraphics[scale=0.5]{./figures/hamming_fig.pdf} 
\end{figure}
\column{0.2\textwidth}
\begin{figure}
\includegraphics[scale=0.45]{./figures/hamming_graph.pdf} 
\end{figure}
\column{0.28\textwidth}
\begin{center}
Parity check equations:
\begin{align*}
C_1 \oplus C_2 \oplus C_3 \oplus C_5 &=0 \\
C_1 \oplus C_3 \oplus C_4 \oplus C_6 &=0 \\
C_1 \oplus C_2 \oplus C_4 \oplus C_7 &=0
\end{align*}
Parity check matrix:
\bmat{\small{1&1&1&0&1&0&0\\
1&0&1&1&0&1&0\\
1&1&0&1&0&0&1}}
\end{center}
\end{columns}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Erasure Coded Storage}
Erasure codes are derived from the Error Correcting Codes and are typically used in storage 
systems to deal with known data erasures or loss.
\begin{figure}[H]
\centering
\includegraphics[scale=0.45]{figures/erasure-eps-converted-to.pdf}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Fault Tolerant Storage--Replication v.s. Erasure Coding}
%Fault Tolerance schemes for storage can be broadly classified into replication and erasure coding schemes.
\vspace{-0.5cm}
\begin{itemize}
\item Replication based schemes maintain as many copies of data as are needed to guarantee required tolerance. 
\item Erasure coding schemes transform the data so that the original data can be reconstructed from (a subset of) the available coded data.
\vspace{-0.25cm}
\begin{figure}
\includegraphics[scale=0.3]{./figures/storage.png} 
\end{figure}
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}{Fault Tolerant Storage}
% To tolerant $k$ disk failures for data size $n$, the replicated storage system requires $n(k+1)$ storage, while erasure code just requires $n+k$ storage.
% \begin{figure}
% \includegraphics[scale=0.4]{./figures/storage.png} 
% \end{figure}
% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}{Erasure Coded Computation}
% \begin{itemize}
% \item The goal is to code the result of a computation in a fault tolerant manner, as opposed to data;
% \vspace{0.5cm}
% \item Data is not linear bit strings or blocks but sparse matrices;
% \vspace{0.5cm}
% \item Recovery is easy.
% \end{itemize}
% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Erasure Coded Computation Basic Kernels}
We show the idea for \alter{erasure coded computations} using a simple example of a sparse matrix-vector product.
\begin{figure}[H]
\includegraphics[scale=0.45]{figures/fig2-1}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Erasure Coded Computation Basic Kernels}
We multiply the distribution matrix with the given sparse matrix. This results in an augmented matrix. %The first $k$ rows of the matrix remain unchanged because of the identity block of rows in the distribution  matrix. The last row is the negative sum of all other rows.
\begin{figure}[H]
\includegraphics[scale=0.33]{figures/fig2-2}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Erasure Coded Computation Basic Kernels}
Example of an alternative distribution matrix, which allows us to control the fill in the augmentation rows. We also show the augmentation block distribution across processors.
\begin{figure}[H]
\includegraphics[scale=0.33]{figures/fig2-3}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Goals and Challenges}
\vspace{-0.2cm}
\begin{block}{Goal}
\vspace{-0.4cm}
\begin{itemize}
    \item Code the result of a computation in a fault tolerant manner (in storage or communication, the computation is an identity operator).
    \item Data is not a linear bit string or a block -- but rather it is a sparse matrix.
    \item Recovery of result of computation must be easy.
\end{itemize}
\vspace{-0.2cm}
\end{block}
\begin{block}{Challenges}
\vspace{-0.4cm}
\begin{itemize}
\item \alert{Design} suitable coding matrices.
\item \alert{Reformulate} traditional linear algebraic methods in the erasure coding framework.
\item Design efficient \alert{recovery} algorithms.
\item Analyze \alert{parallel} performance.
\item Validate tolerance to \alert{different} models of fault arrivals and rates.
\end{itemize}
\vspace{-0.2cm}
\end{block}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}{Fault Oblivious Computation}
 The concept of fault oblivious parallel execution, based on \alert{Erasure Coded Computations}, is as follows:
 \begin{itemize}
 \item \alert{Augment} the input to a parallel program.
 \vspace{0.4cm}
 \item \alert{Execute} on the augmented input in a faulty environment, oblivious to faults, and generate an augmented output.
 \vspace{0.4cm}
 \item \alert{Compute} the true output based on the augmented output from the faulty execution.
 \end{itemize}
 \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Distributed Fault Tolerant Linear System Solver}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Erasure Coded Linear System Solver}
Given a linear system $\mA\vx=\vb$ ($\mA_{n\times n}$ is $SPD$), with true solution $\vx^*$, and coding matrix $\mE_{n \times k}$, we construct the augmented system $\tA\tx=\tb$.\\
\vspace{0.5cm}
\begin{equation*}
\underbrace{\bmat{
\mA & \mA\mE\\
\mE^{\Tr} \!\! \mA & \mE^{\Tr} \!\! \mA \mE
}}_{\displaystyle\tA}
\underbrace{\bmat{
\vx\\
\vr
}}_{\displaystyle\tx}
 \!=\! \underbrace{ \bmat{
\vb\\
\mE^{\Tr} \vb
}}_{\displaystyle\tb}
\end{equation*}
$\tx=\bmat{ \vx^{*}; 0}$ is a solution to the augmented system.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Erasure Coded Linear System Solver}
\alert{Properties of $\tA$:}
%The properties of the augmented system can help us recovery true solution for the original system.
\begin{itemize}
\item If $\mA$ is \alert{$SPD$}, then $\tA$ is \alert{$SPSD$};
\item The null space basis of $\tA$ is \alert{$\begin{bmatrix} \mE\\-\mI_k\end{bmatrix}$};	
\item Any solution of the augmented system can be written as 		 
\alert{\begin{equation*}
\begin{bmatrix}
\vy \\ \vz
\end{bmatrix} = \begin{bmatrix}
\vx^{*} \\ 0
\end{bmatrix} + a \begin{bmatrix}
\mE \\ -\mI_k
\end{bmatrix}
\end{equation*}}
\end{itemize}
\vspace{-0.8cm}
\begin{block}{Theorem}
Based on the properties of $\tilde{A}$, we can recover the true solution as follows:
\begin{equation}
\begin{bmatrix}
\vx^* \\ 0
\end{bmatrix} = \tx + \begin{bmatrix}
\mE \\ -\mI_k
\end{bmatrix}\vr
\end{equation}
\vspace{-0.4cm}
\end{block}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Erasure Coded Linear System Solver}
When faults happen, we can compress the augmented system to a purified system.
\begin{equation*}
\left[\begin{array}{@{}cccc@{}}
\mA_{11} & \mA_{12} &\mZ_1\\
{\mA_{12}}^{\Tr}&\mA_{22} &\mZ_2\\
{\mZ_1}^{\Tr} &{\mZ_2}^{\Tr} & {\mE}^{\Tr}\mA\mE
\end{array}\right] \left[\begin{array}{@{}c@{}}
\vc\\
\vf\\
\vr
\end{array}\right]
\!=\!\left[\begin{array}{@{}c@{}}
\vb_1\\
\vb_2\\
{\mE}^{\Tr}b
\end{array}\right]
\end{equation*}
  \centering $\downarrow$\\
 \vspace{-0.5cm}
\begin{equation*}
\begin{bmatrix}
\mA_{11} & \mZ_1\\
\mZ_1^{\Tr} & \mR
\end{bmatrix} \begin{bmatrix}
\vc \\ \vr
\end{bmatrix} = \begin{bmatrix}
\vb_1 \\ \mE^{\Tr}b
\end{bmatrix} - \begin{bmatrix}
\mA_{12} \\ \mZ_2^{\Tr}
\end{bmatrix}\vf
\end{equation*}
\vspace{-0.2cm}
  \begin{block}{Theorem}
  If $\bmat{ c; r }$ is a solution for the purified system, then
 $\tx=\bmat{ c; f; r}$ is a solution to the augmented system.
 \end{block}
\end{frame} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}{Erasure Coded Linear System Solver}
% %In fault-free CG, we have $(r_t,p_{t-1})=0$. However, given above inner product, the orthogonality of $r_t$ and $p_{t-1}$ will generally not hold. We use the last iteration residue $r_t$ as the new searching direction(that is $p_t=r_t$). This operation is similar to that we restart the CG algorithm from the last iteration before the faults happen.\\
% Based on the properties of $\tilde{A}$, we can recover the true solution as follows:
% \begin{equation}
% \begin{bmatrix}
% \vx^* \\ 0
% \end{bmatrix} = \tx + \begin{bmatrix}
% \mE \\ -\mI_k
% \end{bmatrix}\vr
% \end{equation}
% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Coding Matrix}
\begin{block}{Conditions on matrix $\mE$:}
\vspace{-0.3cm}
\begin{itemize}
\item There is always a solution to the augmented system for faults happening on any rows, as long as total number of faults $\le k$.
\item Given any solution computed with faulty components, we can extract and recover a solution for the original system.
\end{itemize}
\vspace{-0.3cm}
\end{block}
\begin{block}{Desiderata of $\mE$:}
\vspace{-0.3cm}
\begin{itemize}
\item Satisfy properties of Kruskal rank, which means every subset of $k$ rows of matrix $E$ is linearly independent.
\item Be as sparse as possible to minimize the fill in the augmented matrix.
\end{itemize}
\vspace{-0.3cm}
\end{block}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Coding Matrix}
\begin{columns}[t]
\column{0.4\textwidth}
\begin{block}{Definition}
An $n \times k$ matrix $E$ satisfies the recovery-at-random property if a random subset
of $k$ rows (selected uniformly with replacement) is rank $k$ with probability approaching 1.
\end{block}
\column{0.35\textwidth}
\begin{block}{Proposed Coding Matrix $E$}
\centering
$\begin{bmatrix}
 \bullet&\bullet&\bullet&0&0&0\\
 0&\bullet&\bullet&\bullet&0&0\\
 0&0&\bullet&\bullet&\bullet&0\\
 0&0&0&\bullet&\bullet&\bullet\\
 \bullet&0&0&0&\bullet&\bullet\\
 \bullet&\bullet&0&0&0&\bullet
\end{bmatrix}$
\end{block}
\end{columns}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Coding Matrix}
\begin{block}{Proposition}
Let $p$ be the number of nonzeros per row in $E$ and Let $E'$ be a submatrix of $E$ formed by selecting any $p$ rows of matrix $E$. The matrix $E'^{\Tr}$ has rank $p$.
\end{block}
\vspace{0.5cm}
\begin{columns}
\column{0.28\textwidth}
All rows have distinct non-zero structure.
\[\begin{bmatrix}
\bullet & \bullet & \bullet &  &  & \\
 & \bullet & \bullet& \bullet &  & \\
 &  & \bullet & \bullet &\bullet & 
\end{bmatrix}\]
\column{0.28\textwidth}
All rows have same non-zero structure.
\[\begin{bmatrix}
\bullet&\bullet&\bullet&0&0&0\\
\bullet&\bullet&\bullet&0&0&0\\
\bullet&\bullet&\bullet&0&0&0\\
\end{bmatrix}\]
\column{0.28\textwidth}
Some rows from case1 and Some from case2.
\[\begin{bmatrix}
\bullet&\bullet&\bullet&0&0&0\\
0&\bullet&\bullet&\bullet&0&0\\
0&\bullet&\bullet&\bullet&0&0\\
\end{bmatrix}\]
\end{columns}
%\begin{itemize}
%	\item \large Case 1: all rows of $E'$ have distinct non-zero structure. %Then the $p$ rows are definitely linearly independent.
%	\vspace{0.3cm}
%	\item \large Case 2: all rows of $E'$ have the same non-zero structure. %Then we got a $p-$by$-p$ random matrix which is non-singular with probability 1.
%	\vspace{0.3cm}
%	\item \large Case 3: some rows of $E'$ from case1 and some from case2. %This case can be similarly argued to have rank $p$.
%\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Coding Matrix}
\begin{block}{Theorem}
The probability that a randomly chosen set of $k$ rows from the matrix $E$ are linearly dependent is less than $\left(\dfrac{e}{p+1}\right)^{p+1}$.
\end{block}
{\em Proof:} A %necessary and 
sufficient condition for $k$ rows to be linearly dependent is that some selection of $p+1$ rows from these $k$ rows have the same non-zero structure. There are $k$ distinct non-zeros structures for the matrix $E$. %For each selection, the probability of having a specific structure is $\frac{1}{k}$. Then the probability of $p+1$ rows having same non-zero structure is $(\frac{1}{k})^{p+1}$. As we have $\binom{k}{p+1}$ ways to select $p+1$ rows, the probability that a selected block of $k$ rows is linearly dependent is given by:
\[
    \binom{k}{p+1}\left(\frac{1}{k}\right)^{p+1} \leq \left(\frac{e}{p+1}\right)^{p+1}. 
\]
As $p$ increases, this probability rapidly approaches 0, which means that the matrix $E$ is recovery-at-random.\\
 %Next theorem will give the expected maximum number of rows that share the same non-zero structure, and will help us select the most suitable $p$.\\

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Coding Matrix}
To keep the coding matrix and the associated augmented matrix sparse, $p$ should as small as possible.
\begin{theorem}
The expected number of rows from among $k$ randomly selected rows of matrix $E$ that have same nonzero structure is $O\left(\dfrac{\ln k}{\ln\ln k}\right)$.
\end{theorem}
Define a random variable $M$ to be the number of rows that have the same non-zero structure when we select $k$ rows uniformly at random from the matrix $E$.
\[
    Pr(M = t)= \binom{k}{1}\binom{k}{t} \left(\frac{1}{k}\right)^t\left(1-\frac{1}{k}\right)^{k-t} \leq k\left(\frac{e}{t}\right)^t
\]
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Coding Matrix}
The expected number of rows $E(M)$ is given by:
\vspace{-0.2cm}
\begin{equation}
\begin{split}
E(M)&=\sum_{t=1}^{k} t \cdot Pr(M=t) \\
& =\sum_{t=1}^{c\frac{\ln k}{\ln{\ln k}}} t\cdot Pr(M=t)+\sum_{t=\frac{c\ln k}{\ln{\ln k}}}^{k} t \cdot Pr(M=t) \\
& \leq \sum_{t=1}^{\frac{c\ln k}{\ln{\ln k}}} \frac{c\ln k}{\ln{\ln k}} \cdot Pr(M=t)+\sum_{t=\frac{c\ln k}{\ln{\ln k}}}^{k} k \cdot Pr(M=t)\\
& \leq \frac{c\ln k}{\ln{\ln k}}+k\cdot \frac{1}{k^{c/2-1}}\\ &=O(\frac{\ln k}{\ln{\ln k}})
\end{split}
\end{equation}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Parallel Implementation}
Since $A$ is SPD and $\tilde{A}$ is SPSD, we can apply CG to $\tA \tx = \tb$.
\begin{algorithm}[H]
\caption{Fault Oblivious CG with a Two-term Recurrence}
\begin{algorithmic}[1]
\State Let $x_0$ be the initial guess and $r_0=b-Ax_0$, $\beta_0=0$.
\For{$t=0,1,\ldots$ until convergence}
\IfThenElse{Fault detected}
    {$\beta_t = 0$}
    {$\beta_t = \dfrac{\|r_t\|_2^2}{\|r_{t-1}\|_2^2}$}
\State $p_t = r_t + \beta_t^{} p_{t-1}$
\State $q_t = A p_t$
\State $\alpha_t = \dfrac{\|r_t\|_2^2}{\langle q_t,p_t\rangle}$
\State $x_{t+1} = x_t + \alpha_t p_t$
\State $r_{t+1} = r_t - \alpha_t q_t$
\EndFor
\end{algorithmic}
\end{algorithm}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Parallel Implementation}
Assume that each viable process can detect the breakdown of its neighbor processes.
\begin{itemize}
\item Inner products $\langle r_t,r_t\rangle$ and $\langle q_t,p_t\rangle$. %The viable processes carry out the all-reduce operation by skipping the faulty components $F_t$ in the vectors.
\begin{align}
\langle \vr_t,\vr_t \rangle &= \langle(\vr_t)_{[n+k]\backslash F_t},(\vr_t)_{[n+k]\backslash F_t}\rangle
\\
\langle \vq_t,\vp_t \rangle &= \langle(\vq_t)_{[n+k]\backslash F_t},(\vp_t)_{[n+k]\backslash F_t}\rangle
\nonumber
\end{align}
\item Matrix-vector multiplication $\vq_t=\mA \vp_t$. %A viable process carries out its local aggregation operation for computing  $A_{I_i,:} p_t$ by skipping the faulty components $F_t$ in $p_t$.
\begin{align}
\mA_{I_i,:}\vp_t &= \mA_{I_i,[n+k]\backslash F_t}(\vp_t)_{[n+k]\backslash F_t}
\end{align}
\item When observing a fault, we truncate the update $\vp_t=\vr_t+\beta_t \vp_{t-1}$ to be
\begin{align}
\vp_t &= \vr_t.
\end{align}
\vspace{-0.2cm}
This corresponds to a reset of the Krylov process. 
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Reordering and Partitioning}
\includegraphics[height=0.8\textheight,center]{./ftls_fig/ftls_reorder.pdf}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Experimental Data}
We select matrices from the University of Florida Matrix Collection for our tests.
\vspace{1em}\\
\begin{tabu} to \textwidth {*{3}{X[1,cm]}}
\firstrow
Matrix & Rows & Nonzeros\\
\databcsstk & $11,948$ & $149,090$\\
\dataconsph & $83,334$ & $6,010,480$\\ 
\datainline & $503,712$ & $36,816,170$\\
\dataldoor & $952,203$ & $42,493,817$ 
\end{tabu}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Experiment Setup}
\begin{itemize}
\item The right-hand-side vector $\vb$ is first normalized (which means $\|b\|_2 = 1$). The relative error $rtol = \dfrac{\|Ax-b\|_2}{\|b\|_2}$ equals the residual norm $\|r\|_2 = \|Ax-b\|_2$.
\vspace{0.25cm}
\item The termination condition isset to  $\|r\|_2 < 10^{-6}$ for all matrices, and the maximum number of iterations for CG is set to 10000.
\vspace{0.25cm}\textbf{}
\item For the instantaneous fault arrival model, faults arrive at the $1000$-th iteration.
\vspace{0.25cm}
\item For the exponential fault arrival model, the fault rate is set as $10^{-3}$, which implies the average number of steps between two consecutive faults is 1000.
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Convergence--Fault-Free Mode}
\includegraphics[height=0.8\textheight,center]{./ftls_fig/ftls_inst_nfty_cvr.pdf}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Convergence--Faulty Mode}
\includegraphics[height=0.8\textheight,center]{./ftls_fig/ftls_inst_fty_cvr.pdf}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Speedup}
\includegraphics[height=0.8\textheight,,center]{./ftls_fig/ftls_speedup.pdf}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Time Overhead}
\includegraphics[height=0.8\textheight,center]{./ftls_fig/ftls_overhead.pdf}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[c]{Convergence under Different Fault Rates ($K = 4$)}
% \includegraphics[height=0.8\textheight,center]{./ftls_fig/ftls_step_K4_cvr.pdf}
% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Convergence under Different Fault Rates ($K= 8$)}
\includegraphics[height=0.8\textheight,center]{./ftls_fig/ftls_step_K8_cvr.pdf}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Different Fault Models}
The exponential distribution is the most commonly used random fault arrival model. It assumes the time to failure to be exponentially distributed.\\ 
\vspace{0.25cm}
The probability distribution function (PDF) of the time ($\tau$) to failure is given by:
\begin{equation*}
P_e(t<\tau) = 1 - e^{-r_e\tau} 
\end{equation*}
Here $r_e$ is the failure rate.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \begin{frame}[c]{Convergence under Different Fault Arrival Models ($K=4$)}
% \includegraphics[height=0.8\textheight,center]{./ftls_fig/ftls_diff_model_K4_cvr.pdf}
% \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Convergence under Different Fault Arrival Models ($K=8$)}
\includegraphics[height=0.8\textheight,center]{./ftls_fig/ftls_diff_model_K8_cvr.pdf}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Conclusions}
We show how to take recently proposed erasure coding schemes and apply them efficiently on parallel/ distributed platforms. 
\begin{itemize}
\item Creating a new encoding matrix that satisfies recovery requirements for almost all sets of failing components;
\item Partitioning these matrices and demonstrating their suitability w.r.t. parallel execution (low fill, low added communication);
\item Demonstrate good parallel performance and low time overhead;
\item Robustness to different fault arrival models and arrival rates.
\end{itemize}
Our proposed erasure coded computation scheme is general, and can be applied to a
number of other problems. 
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Adaptive Fault Tolerant Linear System Solver}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Adaptive Fault Tolerant Linear System Solver}
The Distributed Fault Tolerant Linear System Solver runs the augmented system from the beginning and can tolerate as many faults as the size of augmentation block during the execution.
\begin{itemize}
\item System size is augmented (\alert{$n \rightarrow n+k$}).
\vspace{0.25cm}
\item System property changes (\alert{SPD $\rightarrow$ {SPSD}}).
\vspace{0.25cm}
\item Computational overhead \alert{paid} at each iteration.
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Adaptive Fault Tolerant Linear System Solver}
Adaptive Fault Tolerant Linear System Solver runs on the original system until a fault occurs. The erased blocks are compensated for by the addition of an identical number of rows (and columns) selected from the pre-computed coding blocks $[\mE^{\Tr}\mA, \mE^{\Tr}\mA\mE]$.
\begin{itemize}
\item System size is the same (always \alert{$n$}).
\vspace{0.25cm}
\item System property is maintained (always \alert{SPD}).
\vspace{0.25cm}
\item Computational Overhead is \alert{negligible}.
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Adaptive Fault Tolerant Linear System Solver}
The initial solution of the original system can be written as:
\begin{equation}
\bmat {
    A_{11} & A_{12}\\
    A_{12}^{\Tr} & A_{22}
} \bmat {
    x_c \\ x_f
} = \bmat {
    b_c \\ b_f
}
\end{equation}
The augmented system can now be written as:
\begin{equation}
\left[\begin{array}{@{}cccc@{}}
\mA_{11} & \mA_{12} &\mZ_1\\
{\mA_{12}}^{\Tr}&\mA_{22} &\mZ_2\\
{\mZ_1}^{\Tr} &{\mZ_2}^{\Tr} & {\mE}^{\Tr}\mA\mE
\end{array}\right] \left[\begin{array}{@{}c@{}}
\vx_c\\
\vx_f\\
\vx_r
\end{array}\right]
\!=\!\left[\begin{array}{@{}c@{}}
\vb_c\\
\vb_f\\
{\mE}^{\Tr}b
\end{array}\right]
\end{equation}

After erasures, we solve the new system:
\begin{equation}
\left[\begin{array}{@{}ccc@{}}
\mA_{11}  &\mZ_1\\
{\mZ_1}^{\Tr} & {\mE}^{\Tr}\mA\mE
\end{array}\right] \left[\begin{array}{@{}c@{}}
\vx_c\\
\vx_r
\end{array}\right]
\!=\!\left[\begin{array}{@{}c@{}}
\vb_c\\
{\mE}^{\Tr}b
\end{array}\right] - \left[\begin{array}{@{}c@{}}
\mA_{12}\\
{\mZ_{2}}^{\Tr}
\end{array}\right]\vx_f
\end{equation}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Adaptive Fault Tolerant Linear System Solver}
\setlength{\intextsep}{0pt}
\begin{algorithm}[H]
\footnotesize
\caption{Adaptive Fault Oblivious CG}
\setlength\multicolsep{0pt}
\begin{multicols}{2}
\begin{algorithmic}[1]
\State{(Reliably) Compute and save the entries $\mZ_1, \mZ_2, \mE^T \mA \mE, \mE^T \vb$
for  matrix $\mE$}%($n \times k$).}
\State $\mAc = \mA$
\State $\vbc = \vb$
\State $\vx_0 = $ the initial guess
\State $\vr_0=\vbc-\mAc \vx_0$
\State $\beta_0=0$
\For{{$t=1,\ldots$ until convergence}}
\If{Fault detected}
    \State{$\vp_t = \vr_{t-1}$}
\Else
    \State{$\vp_t = \vr_{t-1} + \dfrac{\|\vr_{t-1}\|^2_2}{\|\vr_{t-2}\|^2_2} \cdot\vp_{t-1}$}
\EndIf
\State{$\vq_t=\mAc \vp_t$}
\State{$\alpha_{t}^{} = \dfrac{\|\vr_{t-1}\|^2_2}{\langle\vq_t,\vp_t\rangle}$}
\State{$\vx_{t}=\vx_{t-1}+\alpha_t^{} \vp_t$}
\State{$\vr_{t}=\vr_{t-1}-\alpha_t^{} \vq_t$}
\If {Faults detected}
\State $\mAc = \bmat{ \mA_{11} & \tZ_1 \\ \tZ_1^T & \tE^T \mA \tE }$
\State $\vbc = \bmat{ \vb_c -\mA_{12} \vx_f \\ \tE^T \vb - \tZ_2^T \vx_f}$
\State $\vx_{t} = \bmat{ \vx_c \\ 0 }$
\State $\vr_{t} = \vbc- \mAc \vx_{t}$
\EndIf
\EndFor
\end{algorithmic}
\end{multicols}
\end{algorithm}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Reordering and Partition}
\includegraphics[height=0.8\textheight,center]{./adls_fig/adls_reorder.pdf}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Experimental Data}
We select matrices from the University of Florida Matrix Collection for our tests -- $\datacbuckle$ and $\datagyro$ are used to validate the convergence of adaptive fault tolerant linear solver; $\dataconsph$ and $\dataldoor$ are used to validate parallel scalability and robustness to different fault arrival models.
\vspace{2ex}\\
\begin{tabu} to \textwidth {*{3}{X[1,cm]}}
\firstrow
Matrix & Rows & Nonzeros\\
\datacbuckle & $13,681$ & $676,515$\\
\datagyro & $17,361$ & $340,431$\\ 
\dataconsph & $83,334$ & $6,010,480$\\ 
\dataldoor & $952,203$ & $42,493,817$\\ 
\end{tabu}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Experiment Setup}
\begin{itemize}
\item The right hand side $\vb$ is normalized ($||\vb||_2=1$). The relative residual $rtol=\frac{||\mA\vx-\vb||_2}{||\vb||_2}$(equals to $||\vr||_2 = ||\mA\vx-\vb||_2$) is calculated.
\vspace{0.2cm}
\item $||\vr||_2$ is monitored at each iteration and the termination condition is set as $||\vr||_2<10^{-6}$  and the maximum number of iterations of CG is set to 10000 for all matrices.
\vspace{0.2cm}
\item For parallel performance, the matrices are first reordered using Metis. 
\vspace{0.2cm}
\item For exponential fault arrival model, different fault rates($r_e$) ranging from $\frac{1}{\origiter}$ to $\frac{3}{\origiter}$ are tested.
\vspace{0.2cm}
\item In our tests, we set the first fault to happen at $\frac{\origiter}{1+\origiter/r_e}$.
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Convergence}
\begin{figure}[H]
\vspace{-0.6cm}
    \centering
    \includegraphics[scale=0.04,center]{./adls_fig/cvr_sm_results.pdf}\\
    \includegraphics[scale=0.04,center]{./adls_fig/cvr_large_results.pdf}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Speedup}
First, we show the parallel performance of adaptive linear solver under exponential fault arrival model.
\begin{figure}[H]
\includegraphics[scale=0.05,center]{./adls_fig/step_large_sp.pdf}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Speedup}
We all show the parallel performance of adaptive linear solver under instantaneous fault arrival model.
\begin{figure}[H]
\includegraphics[scale=0.05,center]{./adls_fig/inst_large_sp.pdf}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Overhead}
The time overhead of adaptive linear solver is:
\begin{figure}[H]
\includegraphics[scale=0.05,center]{./adls_fig/overhead_results.pdf}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Conclusion}
We have developed an \alert{Adaptive Fault Tolerant Linear System Solver} capable of scaling to large numbers of processors and associated faults. %The solver works by augmenting the input matrix by erasure coded blocks as faults are detected.  
%Our proposed technique has the following significant advantages: 
\begin{itemize}
\item Coding blocks are only added when faults are detected;
\vspace{0.2cm}
\item Convergence properties of adaptive system closely follow those of original system;
\vspace{0.2cm}
\item The solver is robust to a wide range of fault characteristics.
\vspace{0.2cm}
%\item Parallel performance of the solver scales well with increasing numbers of processors;
\item Speedup is near linear and time overhead is small;
%\item Time overheads are small which implies of the solver's applicability to large distributed systems;
%\vspace{0.2cm}
\end{itemize}
%The investigation on the effect of fault rates and fault arrival patterns (instantaneous versus exponential) shows that our scheme is robust to a wide range of fault characteristics.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Erasure Coded Eigensolver}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Reformalization}
\begin{theorem}
Given an eigenvalue problem
\begin{equation}
    A x^{\star} = \lambda^{\star} x^{\star},
    \label{eq:orig-eigen-problem}
\end{equation}
where $A \in \mathbb{R}^{n \times n}$. We construct a generalized eigenvalue problem:
\begin{equation}
    \underbrace{\bmat{
        A & AE \\
        E^\Tr & E^\Tr AE
    }}_{\displaystyle\tilde{A}} \underbrace{\bmat{
        x \\ r
    }}_{\displaystyle\vphantom{\tilde{A}}\tilde{x}} = \lambda \underbrace{\bmat{
        I & E \\
        E^\Tr & E^\Tr E
    }}_{\displaystyle\tilde{B}} \underbrace{\bmat{
        x \\ r
    }}_{\displaystyle\vphantom{\tilde{B}}\tilde{x}},
    \label{eq:general-eigen-problem}
\end{equation}
where $E \in \mathbb{R}^{n \times k}$ is a coding matrix, then $x^\star = x + E r$ and $\lambda^\star = \lambda$.
\end{theorem}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Equivalence of Eigensystems}
We can write the generalized eigenvalue system as:
\begin{equation}
\label{eq:detail-generalized-system}
\bmat {
    A_{11} & A_{12} & Z_1\\
    A_{12}^{\Tr}  & A_{22} & Z_2\\
    Z_1^{\Tr} & Z_2^{\Tr} & R
} \bmat {
    c \\ f \\ r
} = \lambda \bmat {
    B_{11} & B_{12} & Q_1\\
    B_{12}^{\Tr}  & B_{22} & Q_2\\
    Q_1^{\Tr} & Q_2^{\Tr} & S
} \bmat {
    c \\ f \\ r
}
\end{equation}
where
\begin{align*}
\bmat{Z_1 \\ Z_2 } &= \bmat{A_{11} & A_{12} \\ A_{12}^{\Tr} & A_{22} }E,
& \bmat{Q_1 \\ Q_2 } &= \bmat{B_{11} & B_{12} \\ B_{12}^{\Tr} & B_{22} }E, \quad\text{and}\\
R &= E^{\Tr}AE,
& S &= E^{\Tr}BE.
\end{align*}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Equivalence of Eigensystems}
The generalized eigenvalue system will become the following purified $n\times n$ system when faults happen:
\begin{equation*}
\bmat {
    A_{11} & Z_1 \\
    Z_1^{\Tr} & R
} \bmat {
    c \\ r
} = \lambda \bmat {
    B_{11} & Y_1 \\
    Y_1^{\Tr} & S
} \bmat {
    c \\ r
} - \bmat {
    \lambda B_{12} - A_{12}\\
    \lambda Y_2^{\Tr} - Z_2^{\Tr}
} f
\end{equation*}

\begin{block}{theorem}
If $\bmat{ c; r }$  is the solution of the purified system, then $\bmat{ c; f; r}$ is the solution of the generalized eigenvalue system.
\end{block}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Equivalence of Eigensystems}
{\em Proof:} The purified system gives us 
\begin{align}
    A_{11} c + Z_1 r - \lambda B_{11} c - \lambda Q_1 r &= \lambda B_{12} f - \lambda A_{12} f \label{eq:purified-eqpartone}\\
    Z_1^{\Tr} c + R r - \lambda Q_1^{\Tr} - \lambda S r &= \lambda Q_2^{\Tr} f - \lambda Z_2^{\Tr} f \label{eq:purified-eqparttwo}
\end{align}
\Cref{eq:purified-eqparttwo} $- E_1^{\Tr} \times$ \Cref{eq:purified-eqpartone} yields
\begin{equation}
\label{eq:purified-eqpartthree}
    E_2^{\Tr} A_{12} c + E_2^{\Tr} Z_2 r - \lambda E_2^{\Tr} B_{12} c - \lambda E_2^{\Tr} Q_2 r = E_2^{\Tr} (\lambda B_{22} - A_{22}) f
\end{equation}
Premultiplying \Cref{eq:purified-eqpartthree} by $E_2^{-\Tr}$ gives
\begin{equation*}
    A_{12} c + A_{22} f + Z_2 r = \lambda B_{12} c + \lambda B_{22} f + \lambda Q_2 r 
\end{equation*} 
which is the second equation in the \Cref{eq:detail-generalized-system}.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Perturbation}
As $\tA$ and $\tB$ are SPSD, the potential eigenvectors may fall into their null space. We add perturbation to the augmented systems to avoid the problem. 
\begin{equation*}
\tA_p = \begin{bmatrix}
\mA & \mA\mE\\
\mE^{\Tr} \!\! \mA & \epsilon \mI_k +\mE^{\Tr} \!\! \mA \mE
\end{bmatrix},\quad
\tB_p = \begin{bmatrix}
\mI & \mE\\
\mE^{\Tr} \!\! &\epsilon \mI_k +\mE^{\Tr} \!\! \mE
\end{bmatrix}
\end{equation*}
The perturbation is added to the lower-right $k\times k$ block ($\epsilon=10^{-6}$ used here).
\vspace{0.3cm}
\begin{itemize}
    \item $\tA_p$ and $\tB_p$ are \alert{$SPD$} and TraceMin can be used to solve the generalized eigenvalue problem.
    \vspace{0.1cm}
    \item Purification (\alert{once only}) will be done once the trace is small enough.
\end{itemize}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Purification}
For the system $\tA_p\tx=\lambda\tB_p\tx$, we obtain the approx $(\mu,u)$(approximate true eigenpairs $\mA\vv=\lambda \vv$ ) after TraceMin iterations. Hence, we have:
\begin{equation}
    \mA(\vu+\delta \vu) = (\mu+\delta \mu)(\vu+\delta \vu)
    \label{eq:purturbation-equation}
\end{equation}
Also,
\begin{equation}
    \vu^{\Tr}\delta \mu \!=\! 0
    \label{eq:pertubation-orthognal}
\end{equation}
Combining \Cref{eq:purturbation-equation} and \Cref{eq:pertubation-orthognal}, we will get the linear system:
\begin{equation}
\begin{bmatrix}
    \mA-\mu \mI_n & -\vu \\
    -\vu^{\Tr} & 0
\end{bmatrix} \begin{bmatrix}
    \delta \vu\\
    \delta \mu
\end{bmatrix} = \begin{bmatrix}
    -(\mA\vu-\mu \vu) \\ 0
\end{bmatrix}
\end{equation}
Based on $\delta \vu$ and $\delta \mu$, we can update the approximation of the eigenpairs and continue the TraceMin procedure.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Fault Oblivious TraceMin}
\setlength{\intextsep}{0pt}
\begin{algorithm}[H]
\footnotesize
\caption{Fault Oblivious Trace Minimization}
\begin{algorithmic}[1]
\State Choose an $n\times s$ random matrix $V_1$ of full rank such that ${V_1}^{\Tr}\tilde{B_p}V_1=I$($s=2p$).
\For {$t=0,1,\ldots$ until convergence}
\State Compute $W_t=\tilde{A_p}V_t$ and the interaction matrix $H_t={V_t}^{\Tr}W_t$
\State Compute the eigenpairs of $(Y_t,{\Theta}_t)$ for $H_t$.
\State Do the purification if the purification condition is satisfied.
\State Sort the eigenvalue in ascending order and rearrange eigenvectors.
\State Compute the corresponding Ritz Vectors $X_t=V_tY_t$.
\State Compute the residue $R_t=\tilde{A_p}X_t-\tilde{B_p}X_t{\Theta}_t$.
\State Test for Convergence.
\State Solve the following linear system approximately via the CG to get $\Delta_t$.
\begin{equation*}
    \begin{bmatrix}
        \tilde{A_p} & \tilde{B_p}X_t\\
        {X_t}^{\Tr}\tilde{B_p} & 0
    \end{bmatrix} \begin{bmatrix}
        \Delta_t \\ L_t
    \end{bmatrix} = \begin{bmatrix}
        \tilde{A_p} X_t \\ 0
    \end{bmatrix} 
\end{equation*}
\State $\tilde{B_p}$-orthonormalize $X_t-\Delta_t$ into $V_{t+1}$.
\EndFor
\State \Return $\Theta.$
\end{algorithmic}
\end{algorithm}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}
 \frametitle{Implementation}
 \label{fteig-p9}
% \vspace{-0.3cm}
 %The augmented matrix $\tA_p$, $\tB_p$ and the augmented eigenvectors $\tX_k$are distributed among multiple processes by rows.  
 The operations affected by faults in a distributed
 environment are the aggregation operations -- the matrix-matrix and matrix-vector multiplication. 
% Let the index set associated with process $i$ be $I_i$,
% then $[n+k]=\bigcup_{i}I_i$ and the set of faulty indices is $F_t=\bigcup_{i\in P_t}I_i$.\\
 \begin{itemize}
     \item The Matrix-Matrix Operation: \begin{align*}
 (\tA_p,\tV_t) &= \left((\tA_p)_{[n+k]\backslash F_t},(\tV_t)_{[n+k]\backslash F_t}\right)\\
 \label{eq:mat-mat-fault-tolerant}
 (\tA_p,\tX_t) &= \left((\tA_p)_{[n+k]\backslash F_t},(\tV_t)_{[n+k]\backslash F_t}\right)\\
 (\tB_p,\tX_t) &= \left((\tB_p)_{[n+k]\backslash F_t},(\tX_t)_{[n+k]\backslash F_t}\right)
 \end{align*}
 \item The Matrix-Vector Operation in Step 10:
\begin{align*}
(\tA_p,\Delta_t) &= \left((\tA_p)_{[n+k]\backslash F_t},(\Delta_t)_{[n+k]\backslash F_t}\right)
\end{align*}
 \end{itemize}
 \end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Experimental Data}
We select two matrices from the University of Florida Matrix Collection.
\vspace{1em}\\
\begin{tabu} to \textwidth {*{3}{X[1,cm]}X[2,cm]}
\firstrow
Matrix & Rows & Nonzeros & Problem Type\\
\dataminsurfo & $40,806$ & $203,622$ & Optimization Problem\\
\datasdkq & $90,449$ & $4,427,725$ & Structural Problem\\ 
\end{tabu}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Experiment Setup}
\begin{itemize}
\item For validation of convergence, we monitor $\frac{||r_1||_2}{\lambda_1}$.%($r_1$ is the residue for the first eigenpairs and $\lambda_1$ is the first eigenvalue).
The stopping criteria is set as $10^{-08}$ for all the matrices.
\vspace{0.25cm}
\item Define $t_i =\frac{aug_{\lambda_i}-orig_{\lambda_i}}{orig_{\lambda_i}}$ and construct $t=[t_1,t_2,\cdots,t_{10}]$. Then final relative error $rtol=||t||_2$.
\vspace{0.25cm}
\item Augmented blocks with different sizes  are added to the original system. $K=0$ corresponds to the original system; $K=d$ corresponds to an augmented block size of $d$, and $d$ faults happen during the execution ($d=1,8,16$). 
%$orig_{\lambda_i}$ and $aug_{\lambda_i}$ are eigenvalues of original system and augmented system, respectively.
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Experiment Setup}
\begin{itemize}
\item Leverage score is used to sample a large matrix and can measure the importance of each row of $A$. For $A = U \Sigma V$ (SVD decomposition), the leverage score for each row is calculated as follows:
\[
    l(i)=\sum_{j=1}^n U(i,j)
\]
\item Two different fault arrival models, instantaneous and exponential, were tested.
\item For exponential fault model, failure rates ranging from $\dfrac{1}{\origiter}$ to $\dfrac{4}{\origiter}$ were tested. 
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Convergence for Random Case (\dataminsurfo)}
\includegraphics[height=0.8\textheight,center]{figures/minsurfo_basic_inst_rnd.pdf}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Convergence for Random Case (\datasdkq)}
\begin{figure}[H]
%\caption{Effectiveness of basic erasure coded eigensolver (\datasdkq)}
\includegraphics[height=0.8\textheight,center]{figures/s3dkq_basic_inst_rnd.pdf}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Convergence for Worst Case (\dataminsurfo)}
\begin{figure}[H]
\includegraphics[height=0.8\textheight,center]{figures/s3dkq_basic_inst_high.pdf}\\
%\centering \small Worst Case behavior of basic algorithm(\dataminsurfo)
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Convergence for Worst Case (\datasdkq)}
\begin{figure}[H]
\includegraphics[height=0.8\textheight,center]{figures/s3dkq_basic_inst_high.pdf}\\
%\centering \small Worst Case behavior of basic algorithm(\datasdkq)
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Adapative Coding Scheme}
Coding blocks are periodically updated using estimates of leverage scores from prior iteration. The coding matrix $\mE$ is adaptively updated as follows:
  \begin{equation*}
  E(i,:)=E(i,:)*\frac{l(i)}{\bar{l}}
  \end{equation*}
  Here $E(i,:)$ is the $i^{th}$ row of coding matrix $E$, $l(i)$ is the leverage score of $i^{th}$ row and $\bar{l}$ is the average leverage score of all rows.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Convergence of Updating Method (\dataminsurfo)}
\begin{figure}[H]
%\caption{Estimated Leverage Score Updating Method (\dataminsurfo)}
\includegraphics[height=0.8\textheight,center]{figures/minsurfo_leverage_inst_high.pdf}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Convergence of Updating Method (\datasdkq)}
\begin{figure}[H]
%\caption{Estimated Leverage Score Updating Method (\datasdkq)}
\includegraphics[height=0.8\textheight,center]{figures/s3dkq_leverage_inst_high.pdf}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Importance Results (\dataminsurfo)}
\begin{figure}[H]
\includegraphics[height=0.8\textheight,center]{figures/minsurfo_comparison.pdf}\\
%\centering \small Importance of Estimated Leverage Score Updating(\dataminsurfo)
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Importance Results (\datasdkq)}
\begin{figure}[H]
%\caption{Importance of Estimated Leverage Score Updating (\datasdkq)}
\includegraphics[height=0.8\textheight,center]{figures/s3dkq_comparison.pdf}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Comparison of Results (\dataminsurfo)}
\begin{figure}[H]
%\caption{Comparison of Exact and Estimated Leverage Score (\dataminsurfo)}
\includegraphics[height=0.8\textheight,center]{figures/minsurfo_scale.pdf}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Comparison of Results (\datasdkq)}
\begin{figure}[H]
%\caption{Comparison of Exact and Estimated Leverage Score (\datasdkq)}
\includegraphics[height=0.8\textheight,center]{figures/s3dkq_scale.pdf}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Different Fault Arrival Models (\dataminsurfo)}
\begin{figure}[H]
%\caption{Effectiveness on Different Fault Arrival Models (\dataminsurfo)}
\includegraphics[height=0.8\textheight,center]{figures/minsurfo_leverage_step_high.pdf}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]{Different Fault Arrival Models (\datasdkq)}
\begin{figure}[H]
%\caption{Effectiveness on Different Fault Arrival Models (\datasdkq)}
\includegraphics[height=0.8\textheight,center]{figures/s3dkq_leverage_step_high.pdf}
\end{figure}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Conclusion}
We have developed an \alert{Erasure Coded Fault Tolerant Eigensolver}, which can compute real eigenvalues in faulty environments. We show that our methods:
\begin{itemize}
\item Converge to real eigenvalues in both random and worst cases;
\vspace{0.25cm}
\item Utilize estimated leverage score to further improve the convergence for worst case;
\vspace{0.25cm}
\item Are robust to different fault arrival models including instantaneous and exponential fault model;
\end{itemize}
%The validation on different fault starting points and fault rates on different fault arrival models further prove our method's robustness.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Plan of Research}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Plan of Research}
\begin{itemize}
\item Developing sparse coding schemes for matrix computation.
\vspace{0.2cm}
\item Developing distributed fault tolerant linear solver.
\vspace{0.2cm}
\item Developing adaptive fault tolerant linear solver.
\vspace{0.2cm}
\item Developing erasure coded eigensolver.
\vspace{0.2cm}
\item \alert{Developing a distributed fault tolerant eigensolver.}
\vspace{0.2cm}
\item \alert{Developing erasure coded matrix computations for other linear algebraic methods.}
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%
\begin{frame}{ }
\centering
\vspace{2cm}
\Huge \textcolor{WildStrawberry}{Thanks for your time.}\\
\vspace{1cm}
\Huge \textcolor{OliveGreen}{$Q\& A?$}
\end{frame}
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%