On Fault-Tolerant Networks for Sorting

DOI10.1137/0214009zbMath0557.68042OpenAlexW1988695498MaRDI QIDQ3221416

Andrew Chi-Chih Yao, F. Frances Yao

Publication date: 1985

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/2c2915fb1e1b4efd2472f6c27629c5425ce71448

zbMATH Keywords

reliabilityHamming distanceredundancymergingsorting networkcomparatorsunreliable componentsBatcher's network

Mathematics Subject Classification ID

Searching and sorting (68P10) Applications of graph theory to circuits and networks (94C15)

Related Items (10)

Braking the \(\Theta(n\log^ 2 n)\) barrier for sorting with faults ⋮ Reliable minimum finding comparator networks ⋮ Recursive merge sort with erroneous comparisons ⋮ Designing reliable algorithms in unreliable memories ⋮ On sorting in the presence of erroneous information ⋮ Searching games with errors -- fifty years of coping with liars ⋮ Sorting and searching in faulty memories ⋮ The price of resiliency: a case study on sorting with memory faults ⋮ Error-Correcting Tournaments ⋮ Optimal resilient sorting and searching in the presence of memory faults

This page was built for publication: On Fault-Tolerant Networks for Sorting