Reliable Minimum Finding Comparator Networks

Abstract

We consider the problem of constructing reliable comparator networks built from unreliable comparators. In case of a faulty comparator inputs are directly output without comparison. A trivial lower bound of Ω(logn + k) on the depth of n-input k-fault tolerant sorting network is well known. We are interested in establishing exact lower bounds on the depth of such networks. To this end we consider fairly simple minimum-finding networks. Our main result is the first nontrivial lower bound on depths of networks computing minimum among n > 2 items in the presence of k > 0 faulty comparators. We prove that the depth of any such network is at least max([logn] + 2k, logn + klog logn/k+1). We also describe a network whose depth nearly matches the lower bound.