\documentclass{article}
\usepackage{scribe}
\usepackage{mathpazo}
\usepackage{alltt}
%\usepackage{algorithm2e}
%\usepackage[lined,boxed,nofillcomment]{algorithm2e}
\newcommand{\ind}{\hspace{2em}}
\newcommand{\sfont}[1]{$\mathsf{#1}$}
\newcommand{\putval}{\gets}
\newcommand{\true}{\textit{true}}
\newcommand{\false}{\textit{false}}
\newcommand{\ok}{\textit{ok}}
\newcommand{\idlow}[1]{\mathord{\mathcode`\-="702D\it #1\mathcode`\-="2200}}
\newcommand{\litlow}[1]{\mathord{\mathcode`\-="702D\sf #1\mathcode`\-="2200}}
\newcommand{\lit}[1]{\ensuremath{\litlow{#1}}}
\begin{document}
\handout{p}{Exercise 4}{}{}{\today}
\begin{problem}
The \emph{consensus number} of an object is the \emph{maximum} number of
processes for which any number of instances
of the object, together with atomic MWMR registers, can solve consensus. Your
task is to prove the following
statements, based on what you have seen in class.
\begin{enumerate}
\item Prove that the consensus number of atomic registers is $1$.
\item Prove that the consensus number of a compare-and-swap object is $\infty$.
\item Prove that the consensus number of a queue is $2$. For this, you will have
to prove that (a) a queue can
implement consensus for two processes (already done in class), and (b) that it
is impossible to implement a consensus
object using only
queues and atomic registers in a system of 3 processes. (This is slightly
harder. Hint: try to re-do FLP. One of the papers
listed on the class website will help if you get stuck.)
\end{enumerate}
\end{problem}
\begin{problem}
Devise an algorithm that implements a consensus object using (any
number of) queues that are \emph{initially empty} (uninitialized) and atomic
registers
in a system of 2 processes.
\end{problem}
\end{document}