\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{6895}

\begin{document}

\problems{Due: Wednesday, November 12th}{7}{11}

\begin{problem}
    In this problem we develop an alternative analysis for work
    stealing.  We use a potential-function argument rather than a
    delay-sequence argument.  The advantage is that we need not use
    the augmented DAG $G'$, but instead we use more mathematics.  Let
    $d(u)$ be the depth of $u$ in $G$.  Define the \emph{weight} of
    thread $u$ to be
    $$
    w(u) = T_{\infty} - d(u)\ .
    $$
    Define the \emph{potential} of thread $u$ to be
    $$
    \Phi(u) = 3^{w(u)}\ .
    $$
    Define the potential of a processor $p$ to be the sum of the
    potentials of the nodes on $p$ (i.e., in its deque or executing).
    That is:
    $$
    \Phi(p) = \sum_{\textrm{u on p}} \Phi(u)\ .
    $$
    Define the potential of the system to be the sum of the potentials of
    the processors.  That is,
    $$
    \Phi(S) = \sum_{i=1}^{p} \Phi(i)\ .
    $$
    Now divide the execution into \emph{rounds} as in class.
    \begin{problempart}
        Show that a \emph{constant fraction} of the potential on a processor is
        at the top of the deque.  What fraction?
    \end{problempart}
    \begin{problempart}
        Show that there is a \emph{constant probability} in each round that the
        potential decreases by at least a constant fraction.  Calculate
        the constants.
    \end{problempart}
    \begin{problempart}
        Assume you have a coin that comes up heads with probability
        $p$.  Show that with error probability exponentially small in
        $n$, if you flip $n$ times, there will be $\Theta(np)$ heads.
        Calculate constant.
    \end{problempart}
    \begin{problempart}
        Conclude that with probability at least $1-\epsilon$, only
        $(T_{\infty} +\log(1/\epsilon))$ rounds (where $\epsilon$ is
        polynomial in $P$) are necessary before all threads are
        complete.
    \end{problempart}

    \noindent Hint: You will need linearity of expectation, 0/1 random
        variables, and Markov's Inequality.  See CLRS.
\end{problem}

\begin{problem}
  For the Cilk scheduler, show that the \emph{expected} number of
  steals is $O(T_{\infty} \cdot P)$.
\end{problem}

\begin{problem}
    Show that the MESI protocol, as presented in Lecture 13,
    guarantees sequential consistency.
\end{problem}

\begin{problem}(Extra Credit)
  Show that the directory based protocol is correct.  Note that this
  involves more carefully specifying how the protocol works.
\end{problem}

\begin{problem}
  Recall from class the \textsc{Spin-Block Problem}: in order to
  acquire some resource, you can either \emph{spin}, which has cost
  proportional to how long you spin, or you can \emph{block}, which
  has fixed cost $c$.

  In class, we saw for the 1-Random-Choice Spin Block Problem that if
  we block at time $c/2$ with probability $p=2/5$, then the
  competitive ratio is 1.8.

  Suppose that we get to make one random choice at time $t=\beta \cdot
  c$ with probability $p$ to block.  (The rest of the protocol must be
  determinisitc.)  What are the optimal values of $\beta$ and $p$ that
  minimize the competitive ratio?  What is the resulting competitive
  ratio?
\end{problem}

\end{document}
