BITONIC SORT ON A NETWORK COMPUTER WITH A NODE FAILURE

Massively parallel computers are being realized for aiming at high per formance. Bitonic sort is an efficient algorithm for network computers . But generally, it is impossible to use a bitonic sort algorithm on a network computer with a node failure. This paper presents a fault-tol erant scheme of bitonic sort algorithm for a network computer that mak es it possible to tolerate a node failure without an additional hardwa re cost. The method does not have hardware redundancy but has software redundancy. The method does not depend on the network topology. Howev er, the method takes about two times as many steps as that of original bitonic sort. This paper also shows that the method is applicable to a chordal ring connected computer as an example.