FAULT-TOLERANCE IN A CLASS OF SORTING NETWORKS

The early study of fault tolerance in efficient sorting networks only achieved single-fault tolerance. By eliminating critical comparators, Rudolph presented a 1-fault tolerant design of the balanced sorting ne twork (BSN) at the cost of one redundant stage of N/2 comparators and two permuters external to the network. In this paper, we show, however , that 1-fault tolerance of BSN can be achieved without introducing re dundancy and external permuters. Furthermore, we provide solutions to the open question of how to achieve multiple-fault tolerance in BSN. W e analyze the problem from a higher-level by introducing a new concept of critical stages, and find that all stages in previous designs are critical. A 2-fault tolerant design of BSN is then discovered after el iminating its critical stages. The new design has a similar network ar chitecture (i.e., a multistage network with the output recirculated ba ck to the input) and the same hardware cost as Rudolph's, but it has m any distinguished features. 1) It becomes 3-fault tolerant by duplicat ing the redundant stage. 2) It can be generalized to a (k + 1)-fault t olerant design if 1 < k redundant stages are added; and the resulting network has no critical stages but critical (k + 1)-tuples of stages. Sorting would fail if and only if all stages of a critical (k + 1)-tup le are faulty. 3) It can be extended to new topologies with an arbitra ry number of stages, without external permuters, that may achieve an a rbitrary degree of fault tolerance. The performance analysis shows tha t the new designs achieve much higher probabilities of correct sorting in the presence of faulty comparators than the previous reported desi gns.