Reliable minimum finding comparator networks

• Autorzy: Denejko P. , Diks K. , Pelc A. , Piotrów M.
• Języki publikacji: EN

Abstrakty

EN

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 W(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 u+ 2k, logn + klog[logn/( k+1)]). We also describe a network whose depth nearly matches the lower bound.

Słowa kluczowe

EN

comparator networks; fault-tolerant networks; minimum-finding networks

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2000
• Tom: Vol. 42, nr 3,4
• Strony: 235--249
• Opis fizyczny: wykr., bibliogr. 13 poz.

Twórcy

autor

Denejko P.

autor

Diks K.

autor

Pelc A.

autor

Piotrów M.

• Instytut Informatyki, Uniwersytet Warszawski Banacha 2, 02-097 Warszawa, Poland,