BREAKING THE THETA(NLOG(2)N) BARRIER FOR SORTING WITH FAULTS

In this paper, we study the problem of constructing a sorting circuit, network, or PRAM algorithm that is tolerant to faults. For the most p art, we focus on fault patterns that are random, i.e., where the resul t of each comparison is independently faulty with probability upper bo unded by some constant. All previous fault-tolerant sorting circuits, networks, and parallel algorithms require Omega(log(2) n) depth and/or Omega(n log(2) n) comparisons to sort n items. In this paper, we cons truct: a passive-fault-tolerant sorting circuit with O(n log n log log n) comparators, thereby answering a question posed by Yao and Yao in 1985. a reversal-fault-tolerant sorting network with O(n log(log2 3) n ) comparators, thereby answering a question posed by Assaf and Upfal i n 1990, and a deterministic O(log n)-step O(n)-processor EREW PRAM fau lt-tolerant sorting algorithm, thereby answering a question posed by F eige, Peleg, Raghavan, and Upfal in 1990. The results are based on a n ew analysis of the AKS circuit, which uses a much weaker notion of exp ansion that can be preserved in the presence of faults. Previously, th e AKS circuit was not believed to be fault-tolerant because the expans ion properties that were believed to be crucial for the performance of the circuit are destroyed by random faults. Extensions of our results for worst-case faults are also presented. (C) 1997 Academic Press.