\documentclass[12pt]{article}
%\usepackage{amssymb,euscript}
\headheight=0in
\headsep=0in
\textheight=9in
\leftmargin=0in
\textwidth=6.5in
\oddsidemargin=0in
\let\noind=\noindent
\def\Pr{\textbf{Pr}}
\def\unknown {\textrm{unknown}}

\begin{document}
\pagestyle{empty}
\begin{center}
{\bf \large  Computer Science \hfill Homework 1 Answers}\\[3mm]
{\bf \large Behdad Esfahbod \hfill Student \# 993505827}\\
\hrulefill
\end{center}

\begin{enumerate}
\item  Consider that both $p$ and $q$ start with 0, and all
messages are lost, then by \textit{Termination} and
\textit{Strong Validity} rules, we conclude that they both decide
0.  Now consider the case that both start with 1, and again all
messages are lost, then they have to both decide 1.

Now, if $p$ starts with 0, and $q$ with 1, and all messages are
lost, from the viewpoint of $p$, it is the same scenario as the
first consideration above, so it would decide 0, and for $q$, it
is the same as second case above, so it would decide 1, which
contradicts the \textit{Uniform Agreement} rule.

\item It can be solved by the following simple protocol:

{Round 1:} Each process sends its input value to the other process.

{Round 2:} For every process: 

\begin{enumerate}
\item  If received something from the other process, then deciede
the logical AND of the received number and your own input value.

\item Otherwise do not decide.
\end{enumerate}

\noindent\textit{proof\space\space} If any of the processes
decides, it has done it based on the input value of both of them,
and the rule to decide satisfies both \textit{Uniform Agreement}
and \textit{Validity}.  For \textit{Weak Termination}, we observe
that if no failures happen, then both of them would decide in the
second run.

\item We give an impossibility proof.  The idea is that the same
impossiblity proof that was presented in the class works here:
Lets $A$ be an algorithm which guarantees to solve the problem
with \textit{Unanimous Termination}.  Then if no failures happen,
they both should decide.  Now we start removing the last message,
and since one of them would not feel different, it would still
decide, so the other one should decide as before, but with one
fewer message transfered.  Repeating the same technique, we would
see that they should decide even if all messages are lost.  Now
we can easily show that if $p$ starts with 0 and $q$ with 1, and
all messages are lost, then $p$ should decide 0, and $q$ should
decide 1, which is a contradiction with the fact that algorithm
$A$ satisfies \textit{Agreement}.  So no such algorithm exists.

\item
\begin{enumerate}
\item  The following algorithm solves the problem:

In each round $i$ do: 
\begin{enumerate}
\item If not decided yet, send a \textit{request} message to the
other process.
\item If received a \textit{request} message from the other
process, send your input value to the other process.
\item If received from the other process its input value, decide
and logical AND of your own input value and the received value.
\end{enumerate}

\textit{proof\space\space}
\textit{Validity} and \textit{Agreement} are obviously satisfied,
as they both decide the logical AND of their input values, which
would be the same for both os them, and satisfies
\textit{Validity}.

For \textit{Termination}, what happens is that each process
repeats sending the other one \textit{request} messages.  As the
links are fair, this \textit{request} message would eventually
arrive.  Moreover, we can assume that the message is arrived as
many times as we want, as the sender can continue sending it, and
it should arrive again by the hypothesis.  So, the other process,
receives the \textit{request} message, and replies with its
input value.  This scenario repeats, until the first process
receives the input value of the other process.  And it would
eventually happen.  So each one would terminate.  And after both
have decided, they would become quiet.

\item  In that impossiblity proof, we assumed that we can lose
all messages after a certain time, and the processes have to
decide the same way they were doing.  Now with fair links, we
cannot do that.  For example in the algorithm above, if we break
the link, they would send \textit{request} messages infinitly
many times, and would never decide.

\item We go to prove that no such \textit{halting} algorithm
exists.  The proof is pretty like the one presented in the class,
with the difference that we cut the links up to a certain time.

Suppose there exists and algorithm solving the problem.  So
considering a scenario that both $p$ and $q$ start with 0, and
they finally decide 0 and halt.  Now assume that the last message
is sent by $q$ to $p$, and $q$ halts in time $t$.  So now we
decide that this last message and all messages after that until
time $t$ are going to be lost.  Now, $q$ do not feel any
difference, and halts as before, as $p$ cannot send any messages
to $q$ before time $t$.  So $p$ should decide 0 and halt too, and
we have one fewer message.  Continuing the argument, we can show
that with all messages lost until a certain time $t$, the should
both decide 0 and halt before $t$.

Not again, doing the same discussion with 1, shows that they
should decide 1, with all messages lost before $t$.  Combining
the too, $p$ starting with 0, and $q$ with 1, means that $p$
should decide 0, and $q$ should decide 1, which is a
contradiction.  So no such algorithm exists.
\end{enumerate}
\end{enumerate}
\end {document}