Fault tolerant sorting network
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 262, 275-284
- https://doi.org/10.1109/fscs.1990.89546
Abstract
A general technique for enhancing the reliability of sorting networks and other comparator-based networks is presented. The technique converts any network that uses unreliable comparators to a fault-tolerant network that produces the correct output with overwhelming probability, even if each comparator is faulty with some probability smaller than 1/2, independently of other comparators. The depth of the fault-tolerant network is only a constant times the depth of the original network, and the width of the network is increased by a logarithmic factor.Keywords
This publication has 6 references indexed in Scilit:
- Eigenvalues and expandersCombinatorica, 1986
- A Robust Sorting NetworkIEEE Transactions on Computers, 1985
- On Fault-Tolerant Networks for SortingSIAM Journal on Computing, 1985
- On networks of noisy gatesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Sorting inc logn parallel stepsCombinatorica, 1983
- Probabilistic Logics and the Synthesis of Reliable Organisms From Unreliable ComponentsPublished by Walter de Gruyter GmbH ,1956