\problemdata                                                             
        {Failure analysis} % latex-friendly label for the prob.
        {Mean time to failure, Bernoulli processes} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 13, 2} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Suppose we have a calculation that will require $n$~operations to
complete, and our computer has an mean time to failure of
$f$~operations where the failure process is memoryless.  When the
computer fails, it loses all state, so the calculation has to be
restarted from the beginning.

\begin{problemparts}

\problempart Louis Reasoner decides to just run the calculation over and
over until it eventually completes without failing. If the calculation
ever fails, Louis restarts the entire calculation. Give a lower bound
on the time that Louis can expect to wait for his code to complete
successfully on a typical gigahertz processor, with $n = 10^{13}$ and
$f = 10^{12}$? (Hint: $(1-p)^n \leq e^{-pn}$ for all $p \in [0,1]$ and
$(1-p)^n \geq e^{-(p-p^2)n}$ for all $p \in [0,1/\sqrt{2}]$.)

\solution{ From Lecture 22, we know that the MTTF in a Bernoulli process is
  $1/p$, where~$p$ is the probability of a failure on a given trial.
  Therefore, $p = 1/f = 10^{-12}$ in our case. From Lecture 23, we
  know that we can calculate the expected number of operations required
  to complete the system
  \begin{eqnarray*} \Ex(T) & = & \Ex(Q) \cdot \Ex(R) \\
    & = & \frac{1}{(1-p)^n} \cdot \frac{1 - (1-p)^n}{p} \\
    & = & \frac{1 - (1-p)^n}{p (1-p)^n} \\
    & = & \frac{1}{p}\biggl(\frac{1}{(1-p)^n} - 1\biggr)
  \end{eqnarray*}
  The hint now tells us that
  \begin{displaymath}
    \Ex(T) \geq \frac{e^{pn}-1}{p} = 10^{12} \cdot (e^{10} - 1),
  \end{displaymath}
  so the expected \emph{time} to complete the task is at least $e^{10}
  - 1$ seconds, or roughly 6~hours. Since the operation should only
  take 10~seconds in the absence of failures, this is quite a penalty.
  }

\problempart Alyssa P. Hacker decides to divide the Louis's calculation into
10 equal-length parts, and has each part save its state when it
completes successfully. Saving state takes time~$s$. When a failure
occurs, Alyssa restarts the program from the latest saved state. How
long can Alyssa expect to wait for her code to complete successfully
on Louis's system? You can assume that $s < 10^{-4}$~seconds.

\solution{ Now we have to do 10 calculations each of which can be computed
  without regard to previous failures. So by the previous analysis,
  Alyssa expects the $i$th component to take
  \begin{displaymath}
    \Ex(T_i) \geq \frac{e^{pn}-1}{p} = 10^{12} (e - 1)
  \end{displaymath}
  operations (note that $n = 10^{12}$). So, the expected number of
  operations for the entire computation is
  \begin{displaymath}
    \Ex\biggl(\sum_{i=1}^{10} T_i\biggr) = 
    \sum_{i=1}^{10} \Ex(T_i) = 10^{13} (e - 1),
  \end{displaymath}
  giving an expected total computing time of roughly 17~seconds. The
  state saves take negligible time. }

\problempart Alyssa tries to further optimize the expected total computing
time by dividing the calculation into 10\,000 parts instead of~10.
How long can Alyssa expect to wait for her code to complete
successfully? (Hint $e^x = 1 + x + O(x^2)$.)

\solution{
 As before,
  \begin{displaymath}
    \Ex(T_i) \geq \frac{e^{pn}-1}{p} = \frac{1 + pn + O((pn)^2) - 1}{p}
    = n(1 + O(pn))
  \end{displaymath}
  with $n = 10^{13} / 10000 = 10^9$. So, the expected number of
  operations for the entire computation, excluding state saves, is
  roughly $10^{13}$ (since $p = 10^{-12}$ and $n = 10^9$, we ignore
  the $O(pn)$ term). The state saves take more or less one second,
  giving a total time of 11~seconds.
}
\end{problemparts}
\end{problem}
                                 