\documentstyle[11pt,handout]{article}
\begin{document}
\input{localmacros}
\input{macros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{3390}{Analysis of Algorithms}{21 October 1998}{13}

\begin{center}
\Large{\bf Problem of the Week -- 6}
\end{center}

This exercise is a follow-up to Problem~1 of Problem Set~2, in which a set of
$n$ users attempt to access a shared resource $R$.  Recall that the resouce
$R$ has the property that if two or more users attempt to access $R$
simultaneously, then there is a collision and none of the users is granted
access.  Problem~1(b) of Problem Set~2 analyzes a ``naive'' protocol and shows
that the expected number of steps the protocol takes for some user to be
granted access to $R$ is $2^n/n$.

In this exercise, we analyze a somewhat more sophisticated (yet still simple)
protocol, which is based on the {\em exponential backoff protocol}\/ used in
Ethernet local-area networks.  In this protocol, unlike the naive protocol,
each user does not attempt to access $R$ in every time step with a certain
probability.  Instead, it picks its next time step to access based on how many
times it has failed so far.  Formally, each user $u$ executes the following
procedure.
\begin{Enumerate}
\item[1.]
In time step $1$, $u$ attempts to access the resource.
\item[2.]
Immediately after the $i$th failure of $u$, where $i \ge 1$, $u$ selects a
random time step $t$ in the interval $[2^i, 2^{i+1} - 1]$ and attempts to
access $R$ during time step $t$.  (Thus, $u$ waits until time step $t$ to make
its $(i+1)$st attempt.)
\end{Enumerate}
Consider an arbitrary user $u$.  Prove that the expected number of steps taken
for $u$ to get access to $R$ is $O(n)$.  

\junk{
In the
following, we derive an upper bound on the expectation of $X$.

\begin{Enumerate}
\item[(c)]
Let us suppose that $u_1$ has failed $i$ times.  Show that the probability
that $u_1$ will fail the $(i + 1)$st time is at most $e^{-n/2^i}$.  Hence,
infer that the probability that $u_1$ fails at least $i$ times is at most
$e^{-n/2^i}$.

\item[(d)]
Show that if $u_1$ succeeds after exactly $i$ attempts, then $u_1$ succeeds
before time slot $2^i$.

\item[(e)]
Show that $E[X] \le \sum_{i} (2^i - 1) \cdot \Pr[X \ge 2^{i-1}]$.  Now, using
part~(d), infer that $E[X] \le \sum_{i} (2^i - 1) \cdot \Pr[u_1 \mbox{ fails
at least } i \mbox{ times}]$.

\item[(f)]
Using parts~(b) and~(e), prove that $E[X]$ is $O(n)$.
\end{Enumerate}
}
\end{document}