{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:30:33Z","timestamp":1787340633854,"version":"build-2736575974"},"reference-count":9,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,2]]},"abstract":"<jats:p>The study of constructing reliable systems from unreliable components goes back to the work of von Neumann, and of Moore and Shannon. The present paper studies the use of redundancy to enhance reliability for sorting and related networks built from unreliable comparators. Two models of fault-tolerant networks are discussed. The first model patterns after the concept of error-correcting codes in information theory, and the other follows the stochastic criterion used by von Neumann and Moore\u2013Shannon. It is shown, for example, that an additional $k(2n - 3)$ comparators are sufficient to render a sorting network reliable, provided that no more than k of its comparators may be faulty.<\/jats:p>","DOI":"10.1137\/0214009","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"120-128","source":"Crossref","is-referenced-by-count":52,"title":["On Fault-Tolerant Networks for Sorting"],"prefix":"10.1137","volume":"14","author":[{"given":"Andrew C.","family":"Yao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F. Frances","family":"Yao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Komlos, E. Szemeredi,  An  O(nlogn) sorting network,  Proc. 15th Annual ACM Symposium on Theory of Computing, Boston,  1983,  1\u20139, April","DOI":"10.1145\/800061.808726"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"K. E. Batcher,  Sorting networks and their application,  Proc. AFIPS 1968 SJCC, Vol. 32, AFIPS Press, Montvale, NJ,  307\u2013314","DOI":"10.1145\/1468075.1468121"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"D. J. Kleitman, A. R. Meyer, R. L. Rivest, J. Spencer, K. Winklemann,  Coping with errors in binary search procedures,  Proc. 10th Annual Symposium on Theory of Computing, San Diego, CA,  1978,  227\u2013232","DOI":"10.1145\/800133.804351"},{"key":"R4","volume-title":"The art of computer programming. Vol. 1: Fundamental algorithms","author":"Knuth Donald E.","year":"1969"},{"key":"R5","volume-title":"The Art of Computer Programming, Vol. 3","author":"Knuth D. E.","year":"1975"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(56)90044-8"},{"key":"R7","unstructured":"Proceedings of the IEEE, special issue on fault-tolerant digital systems, 66 (1978), pp. 1105\u20131300"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1515\/9781400882618-003"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321976"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214009","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:15Z","timestamp":1787337735000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214009"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,2]]},"references-count":9,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,2]]}},"alternative-id":["10.1137\/0214009"],"URL":"https:\/\/doi.org\/10.1137\/0214009","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,2]]}}}