Reliable Computation in Computing Systems Designed from Unreliable Components

The objective of this paper is to show that it is possible for a computer, designed entirely from unreliable components, to perform operations reliably on information stored in stable memories. The concept of a stable memory is introduced in the paper preceding this, where it is shown that it is possible to store information reliably in memories constructed entirely from unreliable components. 1 Two different models for component malfunctions are considered. The first is based on the assumption that component malfunctions are statistically independent from one use of a particular component to another use. The second is based on the assumption that components * This work, which is based on part of a doctoral thesis submitted to the D e p a r t m e n t of Electrical Ennineering, M.I.T., September 1966, was supported by the National Aeronautics a n d Space Administration ( G r a n t NsG-334). 2339 2340 THE BELL SYSTEM TECHNICAL JOURNAL, DECEMBER 1968 fail permanently but t h a t the components which have failed are periodically replaced with good ones. In both cases component malfunctions are assumed to be statistically independent from one component to another. For both component malfunction models it is shown that there are types of memories, called "stable memories," that have a nonzero information storage capacity; that is, for certain fixed values of the memory's redundancy, the probability of a memory failure can be made arbitrarily small. A particular type of stable memory is considered in some detail.