Fault tolerant arrays

We investigate the existence and computability of a fault cover for a configuration architecture; that is, a setting of switches that achieves an array despite the presence of faulty elements and broken interconnect. The switches may be stuck open or closed. For a preponderance of architectures these questions are NP-complete. This is not the case with local sparing, a fundamental approach that can, in fact, be applied to any nominal architecture. We give an algorithm that decides and computes a fault cover in time that is subcubic in the size of a locally spared array whose neighboring blocks of h elements each can be connected in any of h x h ways.We measure scaling in terms of the probability of a fault cover (coverage), the fraction of faults we can tolerate (tolerance), and the ratio of the size of the architecture to the size of the nominal array (redundancy). We establish a threshold tolerance to faults such that, for arbitrary coverage less than 1, a local spares fault cover exists. We prove that the stochastic tolerance of a two-dimensional array spared by local blocks is much better than when spares are arranged by rows and columns. As to the latter, we treat two architectures: homogeneous and dedicated spares, the worst-case tolerance of which is much better than that of local spares. The fault tolerance of each of these architectures is inferior to the general grid scheme of (Leighton and Leiserson 1985). However, the longest wire in an array configured from a general grid is almost never shorter than that of an array configured by local spares.Although it is not the most tolerant configuration architecture, the combined test and configuration tolerance of local spares is essentially the same as the configuration tolerance alone. Moreover, the stochastic test redundancy of local spares matches the lower bound of (Scheinerman 1987) and (Blough 1988).We show that convergent hypergeometric and binomial distributions of faults do not imply convergent coverage. We characterize homogeneous spares whose complementary external graph consists of a vertex-disjoint packing of star graphs; this solves exactly a subset of the problem of Zarankiewicz