A Reliable Sorting Algorithm on Hypercube Multicomputers

In this paper, we present an algorithm-based fault-tolerant technique, namely themedian-splitting strategy, for designing a reliable sorting algorithm. Combining themedian-splitting strategy with bitonic sorting algorithm, a reliable sorting algorithmis proposed on the hypercube multicomputers. By the strategies of duplicating dataand rollback, the proposed algorithm can detect transient faults and automaticallycorrect errors without any hardware modification. We also implement our...