\documentclass[landscape]{slides}

\usepackage{graphicx}
\usepackage{color}
%\usepackage{amsmath}
%\usepackage{amsfonts}
%\usepackage{array}
%\usepackage{url}
\usepackage{stepslid}
%\def\step\relax
 
\oddsidemargin=+1cm
\textheight=1.2\textheight
\textwidth=1.1\textwidth
\topmargin=-2.0cm

\definecolor{backgroundcolor}{rgb}{0,0,.113}
\definecolor{textcolor}{rgb}{1,1,1}
\definecolor{headcolor}{rgb}{1,1,0}
\definecolor{emphcolor}{rgb}{1,.7,.7}
\definecolor{boldcolor}{rgb}{0,1,0}

\newcommand{\slidetitle}[2]{\raggedleft{\bfseries\textcolor{headcolor}{\Large{#1}}}\par\raggedright{\Large\bfseries#2}\vfill\par}
\newcommand{\cont}{\setbox0=\hbox{\small\space continued}%
	          \smash{\lower1.5\ht0\hbox{\kern-\wd0\box0}}}
\newcommand{\contp}{{\small\space(continued)}}
%\def\abovecaptionskip{5ex}

\let\saveendslide=\endslide
\let\saveendoverlay=\endoverlay
\renewcommand{\endslide}{\vfill\saveendslide}
\renewcommand{\endoverlay}{\vfill\saveendoverlay}
\let\saveslide=\slide
\renewcommand{\slide}{\saveslide\flushright}
\let\saveoverlay=\overlay
\renewcommand{\overlay}{\saveoverlay\flushright}

\let\oldem\em
\def\em{\oldem\color{emphcolor}}
\let\oldbfseries\bfseries
\def\bfseries{\oldbfseries\color{boldcolor}}

\newtheorem{claim}{Claim}
\newtheorem{proposition}{Proposition}
\newtheorem{hunch}{Hunch}
\newtheorem{definition}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{theorem}{Theorem}
\newcommand{\pr}{\tt}
\newcommand{\bpr}{\tt}
\newcommand{\type}{\tt}
\newcommand{\ev}{\em}
\newcommand{\RC}{Crash}
\newcommand{\rc}{crash}
\newcommand{\RO}{Omission}
\newcommand{\ro}{omission}
\newcommand{\RA}{Arbitrary}
\newcommand{\ra}{arbitrary}
\newcommand{\nrc}{NR-crash}
\newcommand{\nro}{NR-omission}
\newcommand{\nra}{NR-arbitrary}
\newcommand{\NRC}{NR-Crash}
\newcommand{\NRO}{NR-Omission}
\newcommand{\NRA}{NR-Arbitrary}

\hyphenation{imple-men-ta-tion imple-men-ta-tions self-imple-men-ta-tion}
\title{\Huge\bfseries\color{headcolor}
	Fault-Tolerant Wait-Free Shared Objects
}
\author{\color{textcolor}\LARGE
	\Large
	JAYANTI, CHANDRA {\normalsize AND} TOUEG\\
	(1998)\\[6ex]
	\color{boldcolor}
	{\tiny A presentation by}\\
	Behdad Esfahbod \\
	\texttt{behdad@cs.toronto.edu}
}

\date{\color{boldcolor}CSC2415, April 14 2004}

\color{textcolor}
\begin{document}
\color{textcolor}
\pagecolor{backgroundcolor}

\maketitle

\slide
\slidetitle{Problem Statement}{}
\begin{itemize}
\item Concurrent asynchronous processes
\item Typed linearizable shared objects
\step
\item Wait-free implementations
\item Failure of processes
\step
\item Failure of base objects \emph{(new)}
\end{itemize}
\endslide


\slide
\slidetitle{Object Failures}{}
\begin{center}
\begin{tabular}{p{.40\textwidth}p{.45\textwidth}}
\ifstep{>0}{{\LARGE\bfseries Responsive}}
\begin{itemize}
\ifstep{>1}{\item{\Large\RC}}
\ifstep{>3}{\item {\Large\RO}}
\ifstep{>2}{\item {\Large\RA}}
\end{itemize}
&
\ifstep{>4}{{\LARGE\bfseries Non-responsive}}
\begin{itemize}
\ifstep{>5}{\item {\Large\NRC}}
\ifstep{>7}{\item {\Large\NRO}}
\ifstep{>6}{\item {\Large\NRA}}
\end{itemize}
\end{tabular}
\end{center}
\endslide


\slide
\slidetitle{Some Terminology}{}
\begin{itemize}
{\LARGE A $t$-tolerant implementation $\cal I$ for failure mode $\cal F$}
\large
\begin{itemize}
\item Wait-free
\item Correct
\item At most $t$ base objects fail by $\cal F$
\end{itemize}
\endslide


\slide
\slidetitle{More Terminology}{}
\Large
\begin{itemize}
\item {Resource complexity}
\step
\item {Self-implementation}
\step
\item {\bf{Gracefully degrading}}
\end{itemize}
\endslide


\slide
\slidetitle{Organization}{}
\large
\begin{itemize}
\item Model and Definitions \emph{(12 pages)}
\item Tolerating responsive failures \emph{(11 pages)}
\item Tolerating non-responsive failures \emph{(5 pages)}
\item Feasibility of graceful degradation \emph{(15 pages)}
\end{itemize}
\endslide


\slide
\slidetitle{The Model}{I/O Automata}
\large
\begin{itemize}
\item Non-deterministic automaton
\item Finite/infinite set of states, including starting state\emph{s}
\item Sets of input/output/internal events
\item Transition relation $(s,e,s')$, the \emph{step}s
\end{itemize}
\endslide


\slide
\slidetitle{The Model\cont}{I/O Automata\contp}
\large

\emph{Enabled} event $e$ at state $s$:\\
$\exists s': (s,e,s') \in$ transition relation.

\emph{Execution} of automaton $A$:
$s_0, e_1, s_1, e_2, s_2, \ldots$.

\emph{History} of an execution: $e_1, e_2, \ldots$.
\endslide


\slide
\slidetitle{The Model\cont}{I/O Automata\contp}
\large

A new automaton $A$ can be constructed by \emph{composing}
a set of ``compatible'' automata $A_1, A_2, \ldots, A_k$.

The \emph{history of a component} $A_i$ is denoted by
$H|A_i$.
\endslide


\slide
\slidetitle{The Model\cont}{Object Type}
\large
\emph{Type} $T$ is a tuple $(OP, RES, G, \tau)$
\begin{itemize}
\vspace{-2ex}
\item $OP$ is the set of \emph{operations}
\vspace{-2ex}
\item $RES$ is the set of \emph{responses}
\vspace{-2ex}
\item $G$ is the \emph{sequential specification} of $T$
\vspace{-2ex}
\item $\tau$, the \emph{transformation functions} is explained later!
\end{itemize}
\endslide
\begin{note}
$T$ is deterministic...

$T$ is total... We only deal with total types.

$T$ is finite...
\end{note}


\slide
\slidetitle{The Model\cont}{Object Type\contp}
\large
\begin{center}
\includegraphics{consensus.eps}\\
Sequential specification of {\type consensus}
\end{center}
\endslide


\slide
\slidetitle{The Model\cont}{Objects and Processes}

Both are modeled as automata
\step

{\large Obect $O$:}
\begin{itemize}
\vspace{-2ex}
\item type $T$
\vspace{-2ex}
\item initial state $s$ of $T$
\vspace{-2ex}
\end{itemize}
\step

{\large Processes}
\begin{itemize}
\vspace{-2ex}
\item can be made to crash
\vspace{-2ex}
\item are deterministic, unless mentioned otherwise
\vspace{-2ex}
\end{itemize}
\endslide



\slide
\slidetitle{The Model\cont}{Concurrent System}
Is the automaton composed from
\begin{itemize}
\item Processes $P_1, P_2, \ldots, P_n$, and
\item Objects $O_1, O_2, \ldots, O_m$.
\end{itemize}
shown by $(P_1, P_2, \ldots, P_n;O_1,\ldots,O_m)$.
\step

For each $P_i$ and $O_j$ and object operation $op$:
\begin{itemize}
\item \emph{$invoke(P_i,op,Oj)$}
\item \emph{$respond(P_i,op,Oj)$}
\end{itemize}
\endslide
\begin{note}
Matching response $r$ and invocation $i$.

An operation is an invocation and its matching response.

Incomplete operation: no matching response.

Operation $p$ precedes $q$...

Concurrent operations.

Sequential history $H$: no concurrent operation.
\end{note}


\slide
\slidetitle{The Model\cont}{Well-formed History}
\Large
\begin{itemize}
\item No prefix of $H|P_i$ has more than one incomplete operation
\item $(H|P_i)|O_j$ begins with an invocation and has alternating invocation
and responses
\end{itemize}
\endslide


\slide
\slidetitle{The Model\cont}{Fairness}
\Large
Execution $E$ is \emph{fair}:
\large
\begin{itemize}
\item 
If $E$ is finite, no internal or output event is enabled in the final
state of $E$
\step
\item
If $E$ is infinite, for each internal or output event $e$,
$E$ contains either infinitely many occurrences of $e$ or
infinitely many states in which $e$ is not enabled
\end{itemize}
\endslide


\slide
\slidetitle{The Model\cont}{Linearizability}
\large
A \emph{linearization} of $H$ with respect to $(T,s)$ is a sequential history
$S$ which:
\normalsize
\vspace{-2ex}
\begin{itemize}
\item is legal from state $s$ of $T$
\vspace{-2ex}
\item includes every complete operation in $H$
\item either does not include incomplete invokes, or includes them with an
arbitrary response.
\vspace{-2ex}
\item includes no other operation
\vspace{-2ex}
\item if $oper<_Hoper'$ then $oper<_Soper'$
\end{itemize}
\endslide


\slide
\slidetitle{The Model\cont}{Well-Behavedness}
\large Linearizablity looks like a good measure for well-behavedness.
\step But not all objects are linearizable:
{\type safe register}\step,
{\type consensus with safe-reset}\step,
{\type 1-reader 1-writer register}\step,
{\type 1-reader 1-writer safe register}.
\step

\Large
For object $O$ of type $T=(OP,RES,G,\tau)$ initialized to state $s$, 
and history $H$ in execution $E$, we say that $O$ is \emph{well behaved} in
$E$ if $\tau(H)$ is linearizable with respect to $(T,s)$.
\endslide


\slide
\slidetitle{The Model\cont}{Implementation}
\large
Let $T$ be a type and $s$ be a state of $T$.

$\cal L=(T_1, T_2, \dots)$ is a list of base types.

$\Sigma=(s_1, s_2, \dots)$ is a list of initial states for $T_i$'s.

$\cal I(O_1, O_2, \dots)$ is an \emph{implementation of $(T, s)$ from $({\cal
    L}, \Sigma)$ for processes $P_1, P_2, \dots, P_N$}.
\endslide

\slide
\slidetitle{The Model\cont}{Implementation\contp}
An implementation is \emph{wait-free} if every derived object $\cal O$ has
this property:  if $E$ is an execution of 
$(P_1,P_2,\dots,P_n;\cal O)$ in which all base objects of $\cal O$ are
wait-free, then $\cal O$ is wait-free in $E$.

An implementation is \emph{$k$-bounded wait-free} if it is wait-free and every derived object $\cal O$ has
this property:  if $E$ is an execution of 
$(P_1,P_2,\dots,P_n;\cal O)$ and for all $P_i$, between an invocation on $\cal
O$ by $P_i$ and its matching response, $P_i$ has \emph{no more than $k$ invocations
on all base objects of $\cal O$} put together.
\endslide

\slide
\slidetitle{Failure Modes}{}
\Large
A failed object may return special response $\perp$

A process does not invoke operations on $\cal O$ anymore after it receives $\perp$ from
$\cal O$
\endslide


\slide
\slidetitle{Failure Modes\cont}{Responsive Failure Modes}
\Large
\begin{itemize}
\item \RC
\item \RO
\item \RA
\end{itemize}
\endslide


\slide
\slidetitle{Failure Modes\cont}{\RC}
{\large
\emph{Object $\cal O$ fails in execution $E$ by crash} if it is not well-behaved,
but:}
\begin{itemize}
\item
$\cal O$ is wait-free in $E$.
\vspace{-2ex}

\item
Responses from $\cal O$ belong to $RES\cup {\perp}$.
An operation that returns $\bot$ is an {\em aborted\/} operation.
\vspace{-2ex}

\item\label{rcrash-once-bot-always}
For operations $op$ and $op'$ in the history $\cal H$,
if $op$ precedes $op'$ and $op$ is an aborted operation,
	then $op'$ is also an aborted operation.
\vspace{-2ex}
\item\label{rcrash-correct-until-failure}
Let ${\cal H}'$ be the history obtained by removing all aborted operations in ${\cal H}$.
Then, $\tau ({\cal H}')$ is linearizable with respect to $(T,s)$.
\end{itemize}
\endslide


\slide
\slidetitle{Failure Modes\cont}{\RO}
{\large
\emph{Object $\cal O$ fails in execution $E$ by omission} if it is not well-behaved,
but:}
\begin{itemize}
\item
$\cal O$ is wait-free in $E$.

\item
Responses from $\cal O$ belong to $RES\cup {\perp}$.

\item
Let ${\cal H}'$ be the history obtained by removing the response events
associated with the aborted operations in ${\cal H}$.
Then, $\tau ({\cal H}')$ is linearizable with respect to $(T,s)$.
\end{itemize}
\endslide


\slide
\slidetitle{Failure Modes\cont}{\RA}
\Large
\emph{Object $\cal O$ fails in execution $E$ by the arbitrary failure mode} if
it is not well-behaved, but is \emph{wait-free} in $E$.
\endslide


\slide
\slidetitle{Failure Modes\cont}{Non-responsive Failure Modes}
\Large
\begin{itemize}
\item \NRC
\item \NRO
\item \NRA
\end{itemize}
\endslide


\slide
\slidetitle{Failure Modes\cont}{\NRC}
{\Large
\emph{Object $\cal O$ fails in execution $E$ by \nrc} if it is not wait-free,
but:}\large
\begin{itemize}
\item
$\cal O$ is well behaved in $E$.

\item
The number of responses from $\cal O$ is finite.
\end{itemize}
\endslide

\slide
\slidetitle{Failure Modes\cont}{\NRO}
\Large
\emph{Object $\cal O$ fails in execution $E$ by the \nro} if
it is not wait-free, but is \emph{well behaved} in $E$.
\endslide


\slide
\slidetitle{Failure Modes\cont}{\NRA}
\Large
\emph{Object $\cal O$ fails in execution $E$ by the \nra} if
it \emph{fails} in $E$.
\endslide


\slide
\slidetitle{Fault-Tolerance}{}
\large
Implementation $\cal I$ is called \emph{$t$-tolerant} if the derived object
${\cal O=\cal I}(O_1,O_2,\dots)$, for every execution $E$ of the concurrent
system $(P_1,P_2,\dots,P_N;\cal O)$, if at most $t$ objects among
$O_1,O_2,\dots$ fail, and they fail by $\cal F$, then $\cal O$ is correct.
\endslide


\slide
\slidetitle{Graceful Degradation}{}
\large
Implementation $\cal I$ is called \emph{gracefully degrading for failure mode
$\cal F$} if the derived object
${\cal O=\cal I}(O_1,O_2,\dots)$, for every execution $E$ of the concurrent
system $(P_1,P_2,\dots,P_N;\cal O)$, if all faulty objects among
$O_1,O_2,\dots$ fail by $\cal F$, then either $\cal O$ is correct or $\cal O$
fails by $\cal F$.
\endslide


\slide
\slidetitle{Fault-Tolerance \& Graceful Degradation}{Compositional Lemma}
Suppose that $T$ has a $t$-tolerant implementation
	from ${\cal L}$ for failure mode $\cal F$, 
	where ${\cal L} = (T_1, T_2, \ldots, T_n)$ is a list of types.
Furthermore, suppose that each $T_i$ has a $t_i$-tolerant gracefully degrading implementation
	from ${\cal L}_i$ for failure mode $\cal F$.
Then we have:
\step
\begin{enumerate}
\item
$T$ has a \emph{$t'$-tolerant} implementation from ${\cal L}'$
	for failure mode $\cal F$, where
% line break
	${\cal L}' = {\cal L}_1 \cdot {\cal L}_2 \cdot \ldots \cdot {\cal
	  L}_n$ and\\
	$t' = \mbox{\it MinSum}(t+1, \langle t_1+1, t_2+1, \ldots , t_n+1 \rangle) - 1$.
\step
\item
If the $t$-tolerant implementation of $T$ from $\cal L$ is gracefully degrading for $\cal F$,
	then $T$ has a $t'$-tolerant \emph{gracefully degrading} implementation from ${\cal L}'$ 
	for failure mode $\cal F$.
\end{enumerate}
\endslide


\slide
\slidetitle{Fault-Tolerance \& Graceful Degradation}{Corollary --- Introducing
Fault-Tolerance}
Suppose that $T$ has a \emph{(0-tolerant)} implementation
        from $(T_1, T_2, \ldots, T_n)$.
Furthermore, suppose that each $T_i$ has a $t$-tolerant gracefully degrading implementation
        from ${\cal L}_i$ for failure mode $\cal F$, where ${\cal L}_i$ is some list of types.
Then we have:
\begin{enumerate}
\item
$T$ has a \emph{$t$-tolerant} implementation from
	${\cal L}_1 \cdot {\cal L}_2 \cdot \ldots \cdot {\cal L}_n$
	for failure mode $\cal F$.
\item
If the (0-tolerant) implementation of $T$ from $(T_1, T_2, \ldots, T_n)$
	is gracefully degrading for $\cal F$, then
	$T$ has a $t$-tolerant \emph{gracefully degrading} implementation from
	${\cal L}_1 \cdot {\cal L}_2 \cdot \ldots \cdot {\cal L}_n$
	for failure mode $\cal F$.
\end{enumerate}
\endslide


\slide
\slidetitle{Fault-Tolerance \& Graceful Degradation}{Corollary --- Self
Implementation}
If $T$ has a $t$-tolerant gracefully degrading \emph{self-implementation}
        $\cal I$ of resource complexity $n$ for failure mode $\cal F$,
        then $T$ has a \emph{$(t^2+2t)$-tolerant} gracefully degrading
        self-implementation ${\cal I'}$ of resource complexity \emph{$n^2$} for $\cal F$.

\step
\slidetitle{}{Corollary --- Booster Lemma}
If $T$ has a \emph{$1$-tolerant} gracefully degrading self-imple\-men\-ta\-tion
        of resource complexity $k$ for failure mode $\cal F$,
        then $T$ has a $t$-tolerant gracefully degrading
        self-implementation of resource complexity \emph{$O(t^{\log_2 k})$} for
	  $\cal F$.
\endslide


\slide
\slidetitle{Fault-Tolerance \& Graceful Degradation}{Lemma --- Graceful
  Degradation for Arbitrary Failures}
\large
If $T$ has a $t$-tolerant \emph{$k$-bounded} implementation from $\cal L$ for \ra\ failures,
	then $T$ has a $t$-tolerant \emph{gracefully degrading} $k$-bounded implementation
	from $\cal L$ for (responsive) \ra\ failures.
\endslide


\slide
\slidetitle{Tolerating Responsive Failures}{}
\Large
\step
\begin{itemize}
\item {\type consensus}
\item {\type register}
\item Universal implementation
\end{itemize}
\endslide


\slide
\slidetitle{Consensus}{}
\large
\begin{itemize}
\item \emph{Integrity:} all responses are either 0 or 1
\item \emph{Weak integrity:} all responses are either 0, 1, or $\bot$
\item \emph{Validity:} if there is a response $v\in\{0,1\}$, then there has
been an
invocation of $propose\ v$
\item \emph{Agreement:} for any two responses $v_1,v_2\in\{0,1\}$, $v_1=v_2$
\end{itemize}
\endslide


\slide
\slidetitle{Consensus\cont}{Proposition --- Correctness}
\large
Object $\cal O$ of type {\type consensus} is \emph{correct} in $E$ iff it:
\begin{itemize}
\item is wait-free,
\vspace{-2ex}
\item satisfies integrity,
\vspace{-2ex}
\item satisfies validity,
\vspace{-2ex}
\item satisfies agreement.
\end{itemize}
\endslide

\slide
\slidetitle{Consensus\cont}{Proposition --- Omission}
\large
Object $\cal O$ of type {\type consensus} \emph{fails by omission} in $E$ iff
it fails in $E$ and it:
\vspace{-2ex}
\begin{itemize}
\item is wait-free,
\vspace{-2ex}
\item satisfies \emph{weak} integrity,
\vspace{-2ex}
\item satisfies validity,
\vspace{-2ex}
\item satisfies agreement.
\end{itemize}
\endslide


\slide
\slidetitle{Fault-Tolerant Consensus}{\RC\ and \RO}
\begin{center}
\def\em{\color{emphcolor}}
\begin{tabbing}
$O_1, O_2, \ldots, O_{t+1}$ :\\consensus objects, initialized to the uncommitted state\\
\\
{\bf Procedure} {{\bpr Propose}($p$, $v_p$, $\cal O$)} 
	\hspace{0.3in} /* $v_p \in \{0,1\}$ */ \\
\hspace{0.2in} \= ${\em estimate_p, w, k}$ : {\type integer} local to $p$ \\
{\bf begin} \\
\> ${\em estimate_p\/}$ := $v_p$ \\
\> {\bf for} $k$ := 1 to $t+1$ \\
\> \hspace{0.2in} \= $w$ := {\pr propose}($p$, $estimate_p$, $O_k$) \\
\> \> {\bf if} $w \not = \bot$ {\bf then} ${\em estimate_p}$ := $w$ \\
\> return(${\em estimate_p}$) \\
{\bf end}
\end{tabbing}
$t$-tolerant self-implementation of {\type consensus} for omission
\end{center}
\endslide
\begin{note}
Self-implementation.

$t+1$ base objects, resource optimal.

Not trivial, all work done is in synchronous message passing systems.

We are in asynchronous shared-memory systems.

Is not gracefully degrading.

There is a gracefully degrading consensus for OMISSION, by $2t+1$ which is
optimal.

There is NO gracefully degrading consensus for CRASH.
\end{note}


\slide
\slidetitle{Fault-Tolerant Consensus}{\RA\ Failures}
Using divide-and-conquer:
\begin{itemize}
\item $O_1$, a $\lceil(t-1)/2\rceil$-tolerant consensus object
\item $O_2$, a $\lfloor(t-1)/2\rfloor$-tolerant consensus object
\item $10t+3$ (0-tolerant) consensus objects:
	$A_0[1\dots3t+1],A_1[1\dots3t+1],B[1\dots4t+1]$
\end{itemize}
\endslide


\slide
\slidetitle{Fault-Tolerant Consensus\cont}{\RA\ Failures}
\large
Efficient $t$-tolerant self-implementation of {\type consensus} for arbitrary
farilures.
\begin{center}
\def\em{\color{emphcolor}}
\small
\begin{tabbing}
$A_0$[$1 \ldots 3t+1$], $A_1$[$1 \ldots 3t+1$], 
	$B$[$1 \ldots 4t+1$] : (0-tolerant) consensus objects, \\
	\hspace{0.4in} initialized to the uncommitted state \\
$O_1$ : $\lceil \frac{t-1}{2} \rceil$-tolerant consensus objects, initialized to the uncommitted state\\
$O_2$ : $\lfloor \frac{t-1}{2} \rfloor$-tolerant consensus objects, initialized to the uncommitted state \\
\\
\hspace{.2in} \= {\bf Procedure} {\bpr Propose}($p, v_p, {\cal O}$) \\
\> \hspace{0.2in} \= $count_p$[0..1], $\mbox{{\em WitnessCount}}_p$[0..1],
	$\mbox{\it belief}_p, ans1_p, \, ans2_p, \, v'_p, \, i, \, w$ : {\type integer} local to $p$ \\
\end{tabbing}
\end{center}
\endslide


\slide
\begin{center}
\def\em{\color{emphcolor}}
\small
\vspace{-2ex}
\begin{tabbing}
1\phantom{0} \= \= $count_p$[0..1], $\mbox{{\em WitnessCount}}_p$[0..1] := (0,0) \\
\\
2 \> \> {\bf Phase} 1: \= {\bf for} $i$ := 1 to $3t+1$ \\
3 \>\> \> \hspace{0.2in} \= $w$ := {\pr f-propose}($p, v_p, A_{v_p}$[$i$]) \\
4 \> \> \> \> {\bf if} $w = v_p$ {\bf then} $count_p$[$v_p$] := $count_p$[$v_p$]+1 \\
\\
5 \> \> {\bf Phase} 2: \> $ans1_p$ := {\pr f-propose}($p, v_p, O_1$) \\
\\
6 \> \> {\bf Phase} 3: \> {\bf for} $i$ := 1 to $4t+1$ \\
7 \> \> \> \> $w$ := {\pr f-propose}($p, ans1_p, B$[$i$]) \\
8 \> \> \> \> $\mbox{{\em WitnessCount}}_p$[$w$] := $\mbox{{\em WitnessCount}}_p$[$w$]+1 \\
\\
9 \> \> {\bf Phase} 4: \> {\bf for} $i$ := 1 to $3t+1$ \\
10 \> \> \> \> $w$ := {\pr f-propose}($p, v_p, A_{\overline{v_p}}$[$i$]) \\
11 \>\> \> \> {\bf if} $w = \overline{v_p}$ {\bf then} 
	$count_p$[$\overline{v_p}$] := $count_p$[$\overline{v_p}$]+1 \\
\\
12 \> \> {\bf Phase} 5: \> Choose $\mbox{\it belief}_p$ s.~t.~ 
	$\mbox{{\em WitnessCount}}_p$[$\mbox{\it belief}_p$] $>$ 
	$\mbox{{\em WitnessCount}}_p$[$\overline{\mbox{\it belief}_p}$] \\
13 \> \> \> {\bf if} $\mbox{{\em WitnessCount}}_p$[$\mbox{\it belief}_p$] $\ge$ $3t+1$
	and $count_p$[$\mbox{\it belief}_p$] $\ge$ $2t+1$ {\bf then} \\
14 \> \> \> \> return($\mbox{\it belief}_p$) \\
15 \> \> \> {\bf if} $\mbox{{\em WitnessCount}}_p$[$\mbox{\it belief}_p$] $\ge$ $2t+1$
        and $count_p$[$\mbox{\it belief}_p$] $\ge$ $t+1$ {\bf then} \\
16 \> \> \> \> $v'_p$ := $\mbox{\it belief}_p$ \\
 \> \> \> {\bf else}  \\
17 \> \> \> \> $v'_p$ := $v_p$ \\
18 \> \> \> $ans2_p$ := {\pr propose}($p, v'_p, O_2$) \\
19 \> \> \> return($ans2_p$) \\
\end{tabbing}
\end{center}
\endslide


\slide
\slidetitle{Fault-Tolerant Consensus}{Theorem}
\large
The algorithm on the previous page presents a $t$-tolerant gracefully degrading self-implementation of
{\type consensus} for \ra\ failures
of resource complexity $O(t \log t)$.
\endslide


\slide
\slidetitle{Adding Reset Capability}{}
\begin{center}
\def\em{\color{emphcolor}}
\begin{tabbing}
\hspace{0.2in} \= \hspace{0.2in} \= \hspace{0.2in} \= \\
\> {\bf Procedure} {\pr Reset}$(p, {\cal O})$ \\
\> \> $i$ : {\type integer} local to $p$ \\
\> {\bf begin} \\
\> \> {\pr reset}$(p, O_1)$ \\
\> \> {\pr reset}$(p, O_2)$ \\
\> \> {\bf for} $i$ := 1 to $3t+1$ \\
\> \> \> {\pr reset}$(p, A_0[i])$ \\
\> \> \> {\pr reset}$(p, A_1[i])$ \\
\> \> {\bf for} $i$ := 1 to $4t+1$ \\
\> \> \> {\pr reset}$(p, B[i])$ \\
\> \> return$(\mbox{{\em ack}})$ \\
\> {\bf end}
\end{tabbing}

Reset procedure of the $t$-tolerant self-implementation of {\type consensus}
with {\type safe-reset} for arbitrary failures.
\end{center}
\endslide


\slide
\slidetitle{Register}{}
\Large
\begin{itemize}
\item {\em read} and {\em write} operations
\item {\type unbounded register} = {\type $\infty$-valued register}
\item {\type boolean register} = {\type 2-valued register}
\end{itemize}
\endslide


\slide
\begin{center}
\def\em{\color{emphcolor}}
\begin{tabbing}
\hspace{0.8in} \= $R_1, R_2, \cdots, R_{2t+1}$: \=1-reader 1-writer safe registers, initialized to \\
\> \> the initial value of the derived register \\
\\
\end{tabbing}

\begin{tabbing}
\underline{{\pr Apply}$(P_r, \mbox{{\em read\/}}, {\cal R})$} \hspace{2.1in} \=
\underline{{\pr Apply}$(P_w, \mbox{{\em write }}v, {\cal R})$} \\

\hspace{0.2in} $val$, $i$ : integers, local to $P_r$ \>
\hspace{0.2in} $i$ : integer, local to $P_w$ \\

\hspace{0.2in} $S$ : multi-set of integers, local to $P_r$ \>
\\

{\bf begin} \>
{\bf begin} \\

\hspace{0.2in} $S$ := $\emptyset$ \>
\hspace{0.2in} {\bf for} $i$ := 1 to $2t+1$ \\

\hspace{0.2in} {\bf for} $i$ := 1 to $2t+1$ \>
\hspace{0.2in} \hspace{0.2in} {\pr apply}$(P_w, \mbox{{\em write }}v, R_i)$ \\

\hspace{0.2in} \hspace{0.2in} $val$ := {\pr apply}$(P_r, \mbox{{\em read\/}}, R_i)$ \>
\hspace{0.2in} return $ack$ \\

\hspace{0.2in} \hspace{0.2in} $S$ := $S \cup \{val\}$ \>
{\bf end} \\

\hspace{0.2in} return $\mbox{{\em mode\/}}(S)$ \>
\\

{\bf end} \>
\\
\end{tabbing}
\large
{$t$-tolerant self-implementation of {\tt 1-reader 1-writer safe register}
	for \mbox{\ra} failures.}
\end{center}
\endslide


\slide
\slidetitle{Fault-Tolerant Register}{Theorem}
\Large
{\type register} has a $t$-tolerant gracefully degrading self-implementation for 
\ra\ failures.
\endslide


\slide
\large
\slidetitle{Universality Results}{Theorem --- Herlihy (1991)}
\vspace{-3ex}
For all types $T$, there is a $k$ such that
	 $T$ has a $($0-tolerant$)$ 
	 \linebreak $k$-bounded implementation from
	$\{${\type consensus with safe-reset}, {\type \emph{unbounded} register}$\}$.

\slidetitle{}{Theorem --- Plotkin (1989)}
\vspace{-3ex}
For all \emph{finite} types $T$,
	there is a $k$ such that $T$ has a $($0-tolerant$)$ $k$-bounded implementation from 
	$\{${\type consensus with safe-reset}, {\type \emph{boolean} register}$\}$.
\endslide


\slide
\slidetitle{Fault-Tolerant Impl.~of Generic Types}{}

{\Large
\textbf{for} $x$ \textbf{in} $\{${\type boolean}$,$ {\type unbounded}$\}$
}
\begin{quotation}
\slidetitle{}{Corollary}
Let $T$ be any (\textbf{if} $x=$ {\type boolean} $\rightarrow$ finite) type.
\begin{itemize}
\item
$T$ has a $t$-tolerant gracefully degrading implementation from
	\newline $\{${\type consensus with safe-reset}, {\type $x$ register}$\}$ for \ra\ failures.
	
\item 
If each of {\type consensus with safe-reset} and $\,$ {\type $x$ register} has 
	a \emph{0-tolerant} gracefully degrading implementation from $T$ 
	for \ra\ failures, then
	$T$ has a \emph{$t$-tolerant} gracefully degrading self-implementation for \ra\ failures.
\end{itemize}
\end{quotation}
\endslide


\slide
\slidetitle{Fault-Tolerant Impl.~of Common Types}{Corollary}
{
\large
{\type compare\&swap}, {\type move}, and {\type m-m swap} have
	$t$-tolerant self-implementations for \mbox{\ra} failures.
	}

\slidetitle{}{Corollary}
\large
{\type queue}, {\type stack}, {\type test\&set}, and {\type fetch\&add}
have $t$-tolerant self-implementations for \mbox{\ra} failures.
These implementations are for two processes.
\endslide


\slide
\slidetitle{Tolerating Non-responsive Failures}{}
\Large
\begin{itemize}
\item \emph{parallel} access to objects
\item {\type consensus}, \emph{impossible!}
\item {\type register}
\item Universal \emph{randomized} implementation
\end{itemize}
\endslide


\slide
\large
\slidetitle{Consensus Revisited}{Theorem}
\vspace{-3ex}
There is \emph{no} 1-tolerant implementation of {\type consensus}, even for
two processes, for \nrc (or for \emph{unfairness to a known process}).
\step

\vspace{-3ex}
\slidetitle{}{Theorem --- \small Loui, Abu-Amara, Dolev, Dwork, and Stockmeyer}
\vspace{-3ex}
The consensus problem for $n$ processes has \emph{no} solution if processes may communicate only
        via registers and at most one process may crash.
\endslide


\slide
\large
\slidetitle{Consensus Revisited\cont}{Corollary}
\vspace{-3ex}
If a type $T$ implements {\type consensus} for two processes, then
	$T$ has \emph{no} 1-tolerant implementation,
	for two processes, for \nrc\ or for unfairness to a known
	  process.
\step

\vspace{-3ex}
\slidetitle{}{Corollary --- Common Types}
\vspace{-3ex}
None of the following types has a 1-tolerant implementation, for two processes, 
	for \nrc\ or for unfairness to a known process:
	{\type compare\&swap},
	{\type fetch\&add}, {\type move},
    {\type queue}, {\type stack}, {\type sticky-bit}, {\type m-m swap}, and {\type test\&set}.
\endslide


\slide
\slidetitle{Fault-Tolerant Register Revisited}{}
\large
Present a $t$-tolerant self-implementation of {\type 1-reader 1-writer safe
  register}
\step

It uses $5t+1$ base registers.  To apply an operation, it applies the same
operation on the base registers asynchronously and waits for $4t+1$ responses.

The mode of the responses is returned as the response.
\endslide


\slide
\slidetitle{Fault-Tolerant Register}{\NRA Failures}
{\large $t$-tolerant self-implementation of {\type 1-reader 1-wrtier safe
  register} for \nra failures.}
\begin{center}
\begin{tabbing}
\hspace{0.6in} \= $R_1, R_2, \cdots, R_{5t+1}$: \=1-reader 1-writer safe registers, initialized to  \\
\> \> the initial value of the derived register \\
\\
\> $\mbox{{\em Pending}}_r$: set, local to the reader process $P_r$, initialized to $\emptyset$ \\
\> $\mbox{{\em Pending}}_w$: set, local to the writer process $P_w$, initialized to $\emptyset$ \\
\end{tabbing}
\end{center}
\endslide


\slide
\begin{center}
\small
\begin{tabbing}
\underline{{\pr Apply}$(P_r, \mbox{{\em read\/}}, {\cal R})$} \hspace{2.8in} \=
\underline{{\pr Apply}$(P_w, \mbox{{\em write }}v, {\cal R})$} \\ 

\hspace{0.1in} $\mbox{{\em Invoked}}_r$: set, local to $P_r$ \>
\hspace{0.1in} $\mbox{{\em Invoked}}_w$: set, local to $P_w$ \\

\hspace{0.1in} $\mbox{{\em Responses}}_r$: multi-set, local to $P_r$ \>
\hspace{0.1in} $\mbox{{\em Responses}}_w$: multi-set, local to $P_w$ \\

\hspace{0.1in} $val$, $i$ : integers, local to $P_r$ \>
\hspace{0.1in} $val$, $i$ : integers, local to $P_w$ \\


{\bf begin} \>
{\bf begin} \\

\hspace{0.1in} $\mbox{{\em Invoked}}_r$ := $\emptyset$ \>
\hspace{0.1in} $\mbox{{\em Invoked}}_w$ := $\emptyset$ \\

\hspace{0.1in} $\mbox{{\em Responses}}_r$ := $\emptyset$ \>
\hspace{0.1in} $\mbox{{\em Responses}}_w$ := $\emptyset$ \\

\hspace{0.1in} $i$ := 0 \>
\hspace{0.1in} $i$ := 0 \\

\hspace{0.1in} {\bf Loop} \>
\hspace{0.1in} {\bf Loop} \\

\hspace{0.1in} \hspace{0.1in} $i$ := $(i \bmod {5t+1}) +1$ \>
\hspace{0.1in} \hspace{0.1in} $i$ := $(i \bmod {5t+1}) +1$ \\

\hspace{0.1in} \hspace{0.1in} {\bf if} $R_i \in \mbox{{\em Pending}}_r$ {\bf then} \>
\hspace{0.1in} \hspace{0.1in} {\bf if} $R_i \in \mbox{{\em Pending}}_w$ {\bf then} \\

\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} Check if $R_i$ responded \>
\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} Check if $R_i$ responded \\

\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} {\bf if} $(${\em yes}$)$ {\bf then} \>
\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} {\bf if} $(${\em yes}$)$ {\bf then} \\

\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} \hspace{0.1in} 
	$\mbox{{\em Pending}}_r$ := $\mbox{{\em Pending}}_r - \{R_i\}$ \>
\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} \hspace{0.1in}
	$\mbox{{\em Pending}}_w$ := $\mbox{{\em Pending}}_w - \{R_i\}$ \\

\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} \hspace{0.1in} Let $val$ be the response \>
\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} \hspace{0.1in} Let $val$ be the response \\

\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} \hspace{0.1in} {\bf if} $R_i \in \mbox{{\em Invoked}}_r$ {\bf then} \>
\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} \hspace{0.1in} {\bf if} $R_i \in \mbox{{\em Invoked}}_w$ {\bf then} \\

\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} \hspace{0.1in} \hspace{0.1in} $\mbox{{\em Responses}}_r$ := 
	$\mbox{{\em Responses}}_r \cup \{val\}$ \>
\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} \hspace{0.1in} \hspace{0.1in} $\mbox{{\em Responses}}_w$ := 
        $\mbox{{\em Responses}}_w \cup \{val\}$ \\

\hspace{0.1in} \hspace{0.1in} {\bf if} $(R_i \not \in \mbox{{\em Pending}}_r) \wedge 
	(R_i \not \in \mbox{{\em Invoked}}_r)$ {\bf then} \>
\hspace{0.1in} \hspace{0.1in} {\bf if} $(R_i \not \in \mbox{{\em Pending}}_w) \wedge 
        (R_i \not \in \mbox{{\em Invoked}}_w)$ {\bf then} \\

\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} Invoke {\em read} on $R_i$ \>
\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} Invoke {\em write $v$} on $R_i$ \\

\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} 
        $\mbox{{\em Invoked}}_r$ := $\mbox{{\em Invoked}}_r \cup \{R_i\}$ \>
\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} 
        $\mbox{{\em Invoked}}_w$ := $\mbox{{\em Invoked}}_w \cup \{R_i\}$ \\

\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} 
	$\mbox{{\em Pending}}_r$ := $\mbox{{\em Pending}}_r \cup \{R_i\}$ \>
\hspace{0.1in} \hspace{0.1in} \hspace{0.1in} 
        $\mbox{{\em Pending}}_w$ := $\mbox{{\em Pending}}_w \cup \{R_i\}$ \\

\hspace{0.1in} {\bf Until} $| \mbox{{\em Responses}}_r | = 4t+1$ \>
\hspace{0.1in} {\bf Until} $| \mbox{{\em Responses}}_w | = 4t+1$ \\

\hspace{0.1in} return $\mbox{{\em mode}}(\mbox{{\em Responses}}_r)$ \>
\hspace{0.1in} return $ack$ \\

{\bf end} \>
{\bf end}
\end{tabbing}
\end{center}
\endslide


\slide
\slidetitle{Fault-Tolerant Register}{Theorem}
\Large
{\type register} has a $t$-tolerant self-implementation for 
\nra\ failures.
\endslide


\slide
\slidetitle{Randomized Fault-Tolerant Implementations of Generic Types}{}
\large
\begin{itemize}
\item Processes have access to \emph{fair coins}
\item Finite \emph{expected} complexity
\item 
Every type has a \emph{randomized} implementation
	from {\type register}! [Herlihy 1991]
\end{itemize}
\endslide


\slide
\slidetitle{Randomized Fault-Tolerant Implementations of Generic
\vspace{-3ex}
  Types\cont}{Theorem}
\large
Every finite (infinite) type has a $t$-tolerant randomized implementation
        from {\type boolean (unbounded) register} for \nra\ failures.
\step

\vspace{-3ex}
\slidetitle{}{Corollary --- Common Types}
\vspace{-3ex}
	Each of {\type test\&set}, {\type compare\&swap}, {\type move}, 
	{\type m-m swap},
	{\type fetch\&add}, {\type queue}, and {\type stack}
	has a $t$-tolerant randomized self-implementation
	even for \nra\ failures.
\endslide


\slide
\hbox{}
\vfill
\begin{center}
\Huge{\textbf{\textcolor{red}{Tired?}}}
\end{center}
\vfill
\vfill
\endslide


\slide
\slidetitle{Graceful Degradation for Crash}{Theorem}
\Large
There is \emph{no} 1-tolerant gracefully degrading implementation of any
order-sensitive type for crash.
\endslide


\slide
\slidetitle{Graceful Degradation for Omission}{Theorem}
\Large
Every type has a $t$-tolerant gracefully degrading implementation from every
universal set of types for omission.
\endslide


\slide
\slidetitle{Graceful Degradation for Omission}{Proof}
\large
\vspace{-4.5ex}
\begin{enumerate}
\item Every 0-tolerant implementation can be transformed into
	a 0-tolerant implementation which is gracefully degrading for \ro.
\vspace{-4ex}
\step
\item
{\type register} has a $t$-tolerant gracefully degrading self-implementation for \ro.
\vspace{-4ex}
\step
\item
{\type consensus with safe-reset} has a $t$-tolerant gracefully degrading 
	implementation from $\{${\type consensus with safe-reset}, {\type register}$\}$ for \ro.
\end{enumerate}
\endslide


\slide
\slidetitle{Graceful Degradation for Register}{}
\Large
Again, we present a 1-tolerant gracefully degrading self-implementation of
{\type 1-reader 1-writer safe register}.

Combining this with other results like before, we obtain a 1-tolerant
gracefully degrading self-implementation of {\type register}.
\endslide


\slide
\begin{center}
\small
\begin{tabbing}
\hspace{0.7in} \= $R_1,R_2,R_3,R_4$: \={\type 1-reader 1-writer safe register}, initialized to \\
\> \> \hspace{0.2in} the same value as the initial value of the derived register \\
\> $\mbox{{\em FAILED\/}}_w$: set, local to the writer process $P_w$, initialized to $\emptyset$ \\
\> $\mbox{{\em FAILED\/}}_r$: set, local to the reader process $P_r$, initialized to $\emptyset$ \\
\> $\mbox{{\em ValuesRead\/}}$: multi-set, local to $P_r$ \\
\end{tabbing}
\begin{tabbing}
\hspace{0.2in} \= \hspace{0.12in} \= \hspace{0.12in} \= \hspace{0.12in} \= \hspace{4.6in} \=
        \hspace{0.12in} \= \hspace{0.12in} \= \hspace{0.12in} \= \\
\> \underline{{\pr Apply}$(P_r, \mbox{{\em read\/}}, {\cal R})$} \> \> \> \>
        \underline{{\pr Apply}$(P_w, \mbox{{\em write }}v, {\cal R})$} \\ \\
\> $\mbox{{\em ValuesRead\/}}$ := $\emptyset$ \> \> \> \>
        {\bf for} $i$ := 1 to 4 \\
\> {\bf for} $i$ := 1 to 4 \> \> \> \>
        \> {\bf if} $R_i \not \in \mbox{{\em FAILED}}_w$ {\bf then} \\
\> \> {\bf if} $R_i \not \in \mbox{{\em FAILED}}_r$ {\bf then} \> \> \>
        \> \> $resp$ := {\pr write}$(P_w, v, R_i)$ \\
\> \> \> $resp$ := {\pr read}$(P_r, R_i)$ \> \>
        \> \> {\bf if} $resp = \bot $ {\bf then} \\
\> \> \> {\bf if} $resp = \bot $ {\bf then} \> \>
        \> \> \> $\mbox{{\em FAILED}}_w$ := $\mbox{{\em FAILED}}_w \cup \{R_i\}$ \\
\> \> \> \> $\mbox{{\em FAILED}}_r$ := $\mbox{{\em FAILED}}_r \cup \{R_i\}$ \>
        {\bf if} $| \mbox{{\em FAILED}}_w | \ge 2 $ {\bf then} \\
\> \> \> {\bf else} $\mbox{{\em ValuesRead}}$ := $\mbox{{\em ValuesRead}} \cup \{resp\}$ \> \>
        \> return $\bot$ \\
\> {\bf if} $| \mbox{{\em FAILED}}_r | \ge 2 $ {\bf then} \> \> \> \>
        {\bf else} return $ack$ \\
\> \> return $\bot$ \\
\> {\bf else} return $mode(\mbox{{\em ValuesRead}})$ \\
\end{tabbing}

{1-tolerant gracefully degrading self-implementation of
        {\type 1-reader 1-writer safe register} for \ro}
\end{center}
\endslide


\slide
\slidetitle{Graceful Degradation for Consensus}{}
{\large
We present a \emph{$t$-tolerant} gracefully degrading implementation of
{\type consensus with safe reset} from $\{${\type boolean register, 0-tolerant
  consensus with safe reset}$\}$.
}

\noindent
${\cal R}_1, {\cal R}_2, \ldots , {\cal R}_{2t+1}$: $t$-tolerant gracefully degrading 
	boolean registers, initialized to 0 \\
$O_1, O_2, \ldots, O_{2t+1}$: (0-tolerant) consensus-with-safe-reset objects 
\endslide

\topmargin=-3cm

\begin{center}
\small
\parbox{\textwidth}{
\begin{tabbing}
\hspace{-0.0in} \= \hspace{0.16in} \= \hspace{0.16in} \= \hspace{0.16in} \= \hspace{0.16in} \= \hspace{4.1in} \=
        \hspace{0.16in} \= \hspace{0.16in} \= \hspace{0.16in} \=
        \hspace{0.16in} \= \hspace{0.16in} \= \hspace{0.16in} \= \\
\> {\bf Procedure} {\pr Propose}$(P_i, v_i, {\cal O})$
        \> \> \> \> \>
        {\bf Procedure} {\pr Reset}$(P_i, {\cal O})$ \\
\> \> $V_i[1\ldots 2t+1]$, $\mbox{{\em estimate}}_i$, {\em resp}, $k$,
        \> \> \> \>
        \> $\mbox{{\em set-of-failed}}$, $\mbox{{\em resp}}$, $k$: local to $P_i$ \\
\> \> {\em set-of-failed}: local to $P_i$
        \> \> \> \>
        {\bf begin} \\
\> {\bf begin}
        \> \> \> \> \>
        \> $\mbox{{\em set-of-failed}}$ := $\emptyset$ \\
\> \> $\mbox{{\em estimate}}_i$ := $v_i$
        \> \> \> \>
        \> {\bf for} $k$ := 1 to $2t+1$ \\
\> \> {\em set-of-failed} := $\emptyset$
        \> \> \> \>
        \> \> $\mbox{{\em resp}}$ := {\pr Read}$(P_i, {\cal R}_k)$ \\
\> \> {\bf for} $k$ := 1 to $2t+1$
        \> \> \> \>
        \> \> {\bf if} $\mbox{{\em resp}} = \bot$ {\bf then} \\
\> \> \> {\em resp} := {\pr Read}$(P_i, {\cal R}_k)$
        \> \> \>
        \> \> \> return $\bot$ \\
\> \> \> {\bf if} $\mbox{{\em resp}} = \bot$ {\bf then}
        \> \> \>
        \> \> {\bf else if} $\mbox{{\em resp}} = 1$ {\bf then} \\
\> \> \> \> return $\bot$
        \> \>
        \> \> \> $\mbox{{\em set-of-failed}}$ := $\mbox{{\em set-of-failed}} \cup \{O_k\}$ \\
\> \> \> {\bf else if} $\mbox{{\em resp}} = 1$ {\bf then}
        \> \> \>
        \> {\bf for} $k$ := 1 to $2t+1$ \\
\> \> \> \> {\em set-of-failed} := $\mbox{{\em set-of-failed}}\, \cup \, \{O_k \}$
        \> \>
        \> \> {\bf if} $O_k \not \in \mbox{{\em set-of-failed}}$ {\bf then} \\
\> \> {\bf for} $k$ := 1 to $2t+1$
        \> \> \> \>
        \> \> \> $\mbox{{\em resp}}$ := {\pr reset}$(P_i, O_k)$ \\
\> \> \> {\bf if} $O_k \in \mbox{{\em set-of-failed}}$ {\bf then}
        \> \> \>
        \> \> \> {\bf if} $\mbox{{\em resp}} = \bot$ {\bf then} \\
\> \> \> \> $V_i[k]$ := $\bot$
        \> \>
        \> \> \> \> $\mbox{{\em resp}}$ := {\pr Write}$(P_i, 1, {\cal R}_k)$ \\
\> \> \> {\bf else}
        \> \> \>
        \> \> \> \> {\bf if} $\mbox{{\em resp}} = \bot$ {\bf then} \\
\> \> \> \> {\em resp} := {\pr propose}$(P_i, \mbox{{\em estimate}}_i, O_k)$
        \> \>
         \> \> \> \> \> return $\bot$ \\
\> \> \> \> {\bf if} $\mbox{{\em resp}} = \bot$ {\bf then}
        \> \>
        \> return {\em ack} \\
\> \> \> \> \> {\em resp} := {\pr Write}$(P_i, 1, {\cal R}_k)$
        \>
        {\bf end}\\
\> \> \> \> \> {\bf if} $\mbox{{\em resp}} = \bot$ {\bf then} \\
\> \> \> \> \> \hspace{0.16in} return $\bot$ \\
\> \> \> \> {\bf else if} $\mbox{{\em resp}} \not = \mbox{{\em estimate}}_i$ {\bf then} \\
\> \> \> \> \> $\mbox{{\em estimate}}_i$ := {\em resp} \\
\> \> \> \> \> $V_i [ 1\ldots (k-1)]$ := $(\bot , \bot , \ldots , \bot )$ \\
\> \> {\bf if} $V_i$ has more than $t$ $\bot$'s {\bf then} \\
\> \> \> return $\bot$ \\
\> \> {\bf else} return $\mbox{{\em estimate}}_i$ \\
\> {\bf end}
\end{tabbing}
}
\end{center}


\slide
\hbox{}
\vfill
\begin{center}
\bfseries
\textcolor{headcolor}{\Huge Q?}
\end{center}
\vfill
\vfill
\endslide


\end{document}

\slide
\slidetitle{}{}
\begin{itemize}
\item
\item
\item
\end{itemize}
\endslide

