Abstract
In this paper, we present an algorithm-based fault-tolerant technique, namely theMmedian-splitting strategy, for designing a reliable sorting algorithm. Combining the median-splitting strategy with bitonic sorting algorithm, a reliable sorting algorithm is proposed on the hypercube multicomputers. By the strategies of duplicating data and rollback, the proposed algorithm can detect transient faults and automatically correct errors without any hardware modication. We also implement our algorithm on NCUBE/7 MIMD hypercube machines with 64 processors. The simulation results show that our sorting algorithm is reliable and cost-eective.