3
$\begingroup$

Probabilistic algorithms often have a parameter that allows one to tune the error rate, typically by running the algorithm repeatedly. This often gives an error rate of something like $2^{-k}$ for $k$ iterations. This is a fine situation to be in, because $2^{-k}$ can be made as close to $1$ as you like without having to make $k$ very big at all. At this point, the theoretician sits back contentedly, his or her job done.

In practical terms, though, are there any guidelines as to which value of $k$ should one choose? Obviously, there's no universal answer, since the answer in any particular situation will be a trade-off depending on the importance of avoiding errors and the cost of doing more iterations.

For example, choosing $k=10$ gives an error rate of about one in a thousand, which seems rather high for most purposes; choosing $k=60$ means the expected number of errors would still be less than one even if you'd run the algorithm once a second since the big bang.

$\endgroup$
2
  • $\begingroup$ I don't have the time right now to do a full research, but there seems to be ample work on soft errors, as they are called. (Also this.) Unsurprisingly, the runtime of the algorithm (in seconds) plays a role since enviromental effects happen, statistically, with some frequency in real time. The type of hardware you use is also crucial; is it hardened? Is it HPC-grade or consumer-throw-away-phone-grade? $\endgroup$
    – Raphael
    Aug 12, 2014 at 19:25
  • 1
    $\begingroup$ actually a lot of study of probabilistic algorithms is largely theoretical and leans away from implementations. a notable exception is primality testing for RSA. havent heard of many others, eg some are apparently used in analyzing graphs for big data. another huge area of related theory here is quantum computing. it might make an interesting question to learn more about applications & maybe lead to more info on how the error terms are chosen in practice. re cosmic rays vs RAM, there was a neat article on that in sci am many years ago that also went into hamming codes for error correction. $\endgroup$
    – vzn
    Aug 13, 2014 at 18:03

2 Answers 2

6
$\begingroup$

As you say, this is application or situation dependant in general. However, a guideline I have encountered is "making the error probability smaller than the probability of a hardware failure". If I remember correctly, this is at least mentioned in the Mitzenmacher-Upfal book.

Say you wanted to replace a deterministic algorithm with a probabilistic algorithm, and still be confident (enough) it works. How often do hardware failures happen then?

Nightingale, Douceur, and Orgovan [1] analyzed hardware failure rates on a million consumer PCs. For instance, bus errors, microcode bugs, and parity errors in CPU caches issue a machine-check exception (MCE), indicating a detected violation of an internal invariant. Roughly, a CPU running for at least 5 days has a 1 in 330 chance of crashing due to an MCE (see Figure 2). They also observed laptops are more reliable than desktop machines, and underclocking helps as well.

In short, one guideline could be this: know the hardware you are running your algorithm on, and analyze how often the hardware makes critical mistakes (or take a good guess e.g. based on [1]).


[1] Nightingale, Edmund B., John R. Douceur, and Vince Orgovan. "Cycles, cells and platters: an empirical analysis of hardware failures on a million consumer PCs." Proceedings of the sixth conference on Computer systems. ACM, 2011.

$\endgroup$
1
  • $\begingroup$ Can we derive a rough, upper-boundish rule of thumb from available data? Something like, "start with $k=50$ and increase by $5$ for every processor-hour your algorithm runs", I don't know. $\endgroup$
    – Raphael
    Aug 12, 2014 at 19:27
8
$\begingroup$

This is the arithmetic for Juho's answer. (Run it for the length of time it takes to make the algorithm failure probability equal the hardware failure probability).

Suppose it takes time $t$ seconds to perform one computation, and thus time $kt$ to get the algorithm error probability down to $2^{-k}$.

Suppose that the hardware probability of failure per second is $p$. Then the probability of a hardware failure is approximately $ktp$ (see lemma below). So you want the $k$ that is the solution to

$$ \frac{1}{2^k} = ktp. $$

Lemma

Assume a memoryless failure process with a failure rate per time period of $p$. Let $P=1/p$ (makes the arithmetic easier). Then for very small $p$ (large $P$) the probability of success in $k$ time periods is

$$ 1 - (\frac{P-1}{P})^k = \frac{P^k - (P-1)^k}{P^k}.$$

By the binomial theorem this is

$$ \frac{P^k - P^k +kP^{k-1} + \frac{k(k-1)}{2}P^{k-2} + \cdots }{P^k} \approx \frac{k}{P} = kp.$$

Value of $p$

Also assuming memorylessness and independence and all that good stuff, the numbers in the paper that Juho provided give a failure rate (memory, disk and cpu) of about $1/180$ in 5 days, which is 432000 seconds, so the probability of failure in 1 second is something like $p = 1/77543800 \approx 2^{-26}$, but you want a lower probability than that, so you should probably use $2^{-27}.$

Thus you want k such that

$$ 2^{27-k} \lt kt$$ $$ 27-k \lt \log_2 k + \log_2 t $$ $$ 27 - \log_2 k - \log_2 t \lt k.$$

But for $k > 1$, $\log_2 k > 0$ so choose

$$ k > 27 - \log_2 t. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.