\documentclass{article}
\usepackage{scribe}
\usepackage{mathpazo}
\usepackage{alltt}
\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}{Answers to Problem Set 1}{}{}{\today}
\begin{problem}
\begin{problempart}
Regular, not atomic.
\end{problempart}
\begin{problempart}
None of the above.
\end{problempart}
\begin{problempart}
Atomic.
\end{problempart}
\end{problem}
\begin{problem}
Consider the transformation from binary MRSW safe registers to binary MRSW
regular registers, given in class.
\begin{problempart} Prove that the transformation does
\textbf{not} generate
multi-valued MRSW regular registers (by providing a counterexample that breaks
regularity).
\end{problempart}
If the registers are multi-valued, then two consecutive reads on the safe
register $\id{Reg}$ may return arbitrary values, breaking regularity of the
register implementation. Since the safe register is binary in the correct
implementation (and thus limited to two values), this does not occur in the
transformation given in class.
\begin{problempart}
Also, prove that the resulting registers are not binary atomic (by
providing a counterexample that breaks atomicity).
\end{problempart}
The counterexample can be easily built by scheduling two distinct reads during
a \lit{write}($1$) operation on the register. Since the underlying register is
safe, we can ensure that the first operation returns $1$, while the second
(non-overlapping) operation returns $0$, contradicting atomicity.
\end{problem}
\begin{problem}
Consider the transformation from binary regular to M-valued MRSW regular
registers given in class. Prove that:
\begin{problempart} The resulting registers are regular.
For this, please follow the steps of the proof as outlined in class. In
particular, prove that any \lit{read} operation starting after a \lit{write}
must return the last written value, and that any concurrent read operation must
either return the current value, or the previous value.
\end{problempart}
\begin{problempart} The transformation would not work if the \lit{Write}
operation would
first write $0$, and then $1$. (You should provide a counterexample that breaks
regularity.)
For this, notice that if the writer first clears the array by writing $0$'s, it
is possible for the value of the array to be all $0$'s, which is not a valid
state (in particular, it might cause a reader to read forever).
\end{problempart}
\begin{problempart} The resulting registers are not atomic. (You should provide
a counterexample execution that breaks atomicity.)
Please see Chapter $3$ of the lecture notes on the website, page $14$
(paragraph entitled ``\emph{A counterexample for atomicity}").
\end{problempart}
\end{problem}
\end{document}