Reliable Minimum Finding Comparator Networks

Abstract We consider the problem of constructing reliable minimum finding networks built from unreliable comparators. In case of a faulty comparator inputs are directly output without comparison. 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([log n ] + 2 k, log n + k log log n/k +1). We also describe a network whose depth nearly matches the lower bound. The lower bounds should be compared with the first nontrivial upper bound O (log n + k log log n /log k ) on the depth of k -fault tolerant sorting networks that was recently derived by Leighton and Ma [6].

Authors

• Piotr Denejko
• Krzysztof Diks
• Andrzej Pelc
• Marek Piotrów

Keywords

No keywords are indexed for this paper.