Combinatorial algorithms in the presence of random errors - II

In the present study, we consider a computational model similar to the classical RAM machine, except that each instruction performed by the machine may fail with probability $q< 1/ 6e.$ The failures are transient and independent of each other. The definition of this model (which we call ERRAM) follows a previous work \cite{lp}, where we did not allow for addressing errors. We show how an arbitrary RAM program may be transformed into an ERRAM program, working with assigned probability $1- \delta,$ provided that we know the number $T$ of instructions that are executed by the original program, or an upper bound to it. One major tool that we use is redundancy, namely, each operation is repeated a certain number of times, and each stored value is kept in several copies. We derive upper bounds on the amount of redundancy that is needed to achieve the desired confidence. This allows us to bound both the space complexity and the expected time complexity of the resulting ERRAM program, in terms of $T$, $\delta$ and $q.