FAULT-TOLERANT NETWORKS FOR SORTING.

This 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 J. von Neumann and E. F. Moore and C. 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.