Abstract
In this paper, we present an algorithm-based fault-tolerant technique, namely the median-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 modification. We also implement our algorithm on nCUBE/1 hypercube machines with 64 processors. The simulation results show that our sorting algorithm is reliable and cost-effective.