Affiliations: Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097 Warszawa, Poland. Email: [email protected] | Département d'Informatique, Université du Québec à Hull, Hull, Québec J8X 3X7, Canada. Email: [email protected] | Instytut Informatyki, Uniwersytet Wrocławski, Przesmyckiego 20, 51-151 Wrocław, Poland. Email: [email protected]
Note: [] Address for correspondence: Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097 Warszawa, Poland
Note: [] Address for correspondence: Instytut Informatyki, Uniwersytet Warszawski, Banacha 2, 02-097 Warszawa, Poland Research supported in part by NSERC International Fellowship and by grant KBN 2-2043-92-03.
Note: [] Research supported in part by NSERC grant OGP 0008136. Address for correspondence: Département d'Informatique, Université du Québec à Hull, Hull, Québec J8X 3X7, Canada
Note: [] Research supported in part by grant KBN 8 T11C 032 15. Adderss for correspondence: Instytut Informatyki, Uniwersytet Wrocławski, Przesmyckiego 20, 51-151 Wrocław, Poland
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.
