Fault-tolerant schemes for some systolic systems
Karel Čulík, Sheng Yü · International Journal of Computer Mathematics · 1987
Fault-tolerant schemes for several types of systolic systems are proposed. By a fault-tolerant scheme for a certain type of systems, say undirectional rings, we mean an algorithm that converts any given system of this type into an equivalent fault-tolerant system of the same type. We consider a specific type of fault tolerance introduced by Kung and Lam. It is assumed that the faulty cells of a given system can be detected and “switched” so that each of them passes its inputs to its outputs in a specified order. To specify the degree of fault tolerance we introduce the notion of fault tolerance with respect to a collection Ω of subsets of the cells of a system. To be fault tolerant, the system must tolerate the failure of all the cells of any of the subset in Ω We devise fault-tolerant schemes for trellis networks, one-way (unidirectional) cellular automata, one-way rings and two-way cellular automata and iterative arrays.