A multiple-fault tolerant sorting network

Fault tolerance of balanced sorting networks (BSNs), which have the same performance bound as the Batcher efficient sorting networks, is discussed. Preliminary studies of fault tolerance in a BSN which demonstrated 1-fault tolerance with and without redundant comparators and external permuters and 2-fault tolerance requiring redundancy are reviewed. The present study further develops a k-fault-tolerant BSN design, where k>or=2 can be arbitrary in principle, even without redundancy. The performance analysis shows that the new designs achieve much higher probabilities of correct sorting in the presence of faulty comparators than the previously reported designs.<>