Fault Tolerant Sorting Network

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. >

Authors

• Shay Assaf
• Eli Upfal

Keywords

• Fault tolerance
• Sorting
• Registers
• Mathematics
• Computer networks
• Large-scale systems
• Algorithm design and analysis
• Career development
• Merging
• Stochastic processes
• Fault-tolerant
• Sorting Network
• Fault-tolerant Network
• Original Network
• Network Depth
• Correct Output
• Network Width
• Part Of Network
• Correct Value
• Probability Of Failure
• Value Network
• Probability 1
• Network Comparison
• N Log N