Fault tolerant sorting network

Abstract

A general technique for enhancing the reliability of sorting networks and other comparator-based networks is presented. The technique converts any network that uses unreliable comparators to a fault-tolerant network that produces the correct output with overwhelming probability, even if each comparator is faulty with some probability smaller than 1/2, independently of other comparators. The depth of the fault-tolerant network is only a constant times the depth of the original network, and the width of the network is increased by a logarithmic factor.