On Fault-Tolerant Networks for Sorting

The study of constructing reliable systems from unreliable components goes back to the work of von Neumann, and of Moore and Shannon. The present paper studies the use of redundancy to enhance reliability for sorting and related networks built from unreliable comparators. Two models of fault-tolerant networks are discussed. The first model patterns after the concept of error-correcting codes in information theory, and the other follows the stochastic criterion used by von Neumann and Moore–Shannon. It is shown, for example, that an additional k (2n - 3) comparators are sufficient to render a sorting network reliable, provided that no more than k of its comparators may be faulty.