\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