{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:22Z","timestamp":1787337502359,"version":"build-2736575974"},"reference-count":57,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    In this paper, we analyze the fault tolerance of several bounded-degree networks that are commonly used for parallel computation. Among other things, we show that an N-node butterfly network containing $N^{1-\\epsilon}$ worst-case faults (for any constant $\\epsilon &gt; 0$) can emulate a fault-free butterfly of the same size with only constant slowdown. The same result is proved for the shuffle-exchange network. Hence, these networks become the first connected bounded-degree networks known to be able to sustain more than a constant number of worst-case faults without suffering more than a constant-factor slowdown in performance. We also show that an N-node butterfly whose nodes fail with some constant probability p can emulate a fault-free network of the same type and size with a slowdown of 2\n                    <jats:sup>\n                      O(log\n                      <jats:sup>*<\/jats:sup>\n                      N)\n                    <\/jats:sup>\n                    . These emulation schemes combine the technique of redundant computation with new algorithms for routing packets around faults in hypercubic networks. We also present techniques for tolerating faults that do not rely on redundant computation. These techniques tolerate fewer faults but are more widely applicable because they can be used with other networks such as binary trees and meshes of trees.\n                  <\/jats:p>","DOI":"10.1137\/s0097539793255163","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1303-1333","source":"Crossref","is-referenced-by-count":26,"title":["On the Fault Tolerance of Some Popular Bounded-Degree Networks"],"prefix":"10.1137","volume":"27","author":[{"given":"F. Thomson","family":"Leighton","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bruce M.","family":"Maggs","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ramesh K.","family":"Sitaraman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1676021"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"W. Aiello and T. Leighton,\n                      Coding theory, hypercube embeddings, and fault tolerance\n                      , in Proc. 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, July 1991, pp. 125\u2013136.","DOI":"10.1145\/113379.113391"},{"key":"R3","unstructured":"W. A. Aiello, personal communication, July 1992."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"M. Ajtai, N. Alon, J. Bruck, R. Cypher, C. T. Ho, M. Naor, and E. Szemer\u00e9di,\n                      Fault tolerant graphs, perfect hash functions and disjoint paths\n                      , in Proc. 33rd Annual Symposium on Foundations of Computer Science, Oct. 1992, pp. 693\u2013702.","DOI":"10.1109\/SFCS.1992.267781"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/121956.121959"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791221499"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Shay Assaf, Eli Upfal, Fault tolerant sorting network, IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, 275\u20132841150703","DOI":"10.1109\/FSCS.1990.89546"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Y. Aumann and M. Ben\u2010Or,\n                      Asymptotically optimal PRAM emulation on faulty hypercubes\n                      , in Proc. 32nd Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Piscataway, NJ, Oct. 1991, pp. 440\u2013457.","DOI":"10.1109\/SFCS.1991.185404"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Sandeep Bhatt, Fan Chung, F. Leighton, Arnold Rosenberg, Tolerating faults in synchronization networks, Lecture Notes in Comput. Sci., Vol. 634, Springer, Berlin, 1992, 1\u2013121249069","DOI":"10.1007\/3-540-55895-0_391"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1109\/12.241598"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794274994"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/121956.121966"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1109\/12.142686"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255011"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"R. Cole, B. Maggs, and R. Sitaraman,\n                      Routing on butterfly networks with random faults\n                      , in Proc. 36th Annual Symposium on Foundations of Computer Science, Oct. 1995, pp. 558\u2013570.","DOI":"10.1109\/SFCS.1995.492586"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1109\/12.54842"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(91)90129-W"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"S. Even and A. Litman,\n                      Layered cross product\u2014A technique to construct interconnection networks\n                      , in Proc. 4th Annual ACM Symposium on Parallel Algorithms and Architectures, July 1992, pp. 60\u201369.","DOI":"10.1145\/140901.140908"},{"key":"R19","unstructured":"M. R. Fellows,\n                      Encoding Graphs in Graphs\n                      , Ph.D. thesis, Department of Computer Science, University of California, San Diego, CA, 1985."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090766"},{"key":"R21","unstructured":"R. I. Greenberg and C. E. Leiserson,\n                      Randomized routing on fat\u2010trees\n                      , in Randomness and Computation, Advances in Computing Research, Vol. 5, S. Micali, ed., JAI Press, Greenwich, CT, 1989, pp. 345\u2013374."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/1634.2377"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"J. Hastad, T. Leighton, and M. Newman,\n                      Reconfiguring a hypercube in the presence of faults\n                      , in Proc. 19th Annual ACM Symposium on Theory of Computing, May 1987, pp. 274\u2013284.","DOI":"10.1145\/28395.28425"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"J. Hastad, T. Leighton, and M. Newman,\n                      Fast computation using faulty hypercubes\n                      , in Proc. 21st Annual ACM Symposium on Theory of Computing, May 1989, pp. 251\u2013263.","DOI":"10.1145\/73007.73031"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"C. Kaklamanis, A. R. Karlin, F. T. Leighton, V. Milenkovic, P. Raghavan, S. Rao, C. Thomborson, and A. Tsantilas,\n                      Asymptotically tight bounds for computing with faulty arrays of processors\n                      , in Proc. 31st Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Piscataway, NJ, Oct. 1990, pp. 285\u2013296.","DOI":"10.1109\/FSCS.1990.89547"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1145\/256292.256299"},{"key":"R27","volume-title":"Introduction to parallel algorithms and architectures","author":"Leighton F.","year":"1992"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1109\/12.142684"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1030"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215349"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1985.1676584"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1470"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1985.6312192"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"G. Lin,\n                      Fault tolerant planar communication networks\n                      , in Proc. 24th Annual ACM Symposium on the Theory of Computing, May 1992, pp. 133\u2013139.","DOI":"10.1145\/129712.129726"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1010"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090403"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"B. M. Maggs and R. K. Sitaraman,\n                      Simple algorithms for routing on butterfly networks with bounded queues\n                      , in Proc. 24th Annual ACM Symposium on the Theory of Computing, May 1992, pp. 150\u2013161; SIAM J. Comput., to appear.","DOI":"10.1145\/129712.129728"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1007\/BF00265559"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1137\/0215008"},{"key":"R40","doi-asserted-by":"crossref","unstructured":"Friedhelm Meyer auf der Heide, Rolf Wanka, Time\u2010optimal simulations of networks by universal parallel computers, Lecture Notes in Comput. Sci., Vol. 349, Springer, Berlin, 1989, 120\u20131311027395","DOI":"10.1007\/BFb0028978"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1971.tb02570.x"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"N. Pippenger,\n                      Telephone switching networks\n                      , in Proc. Symposia in Applied Mathematics, Vol. 26, American Mathematical Society, Providence, RI, 1982, pp. 101\u2013133.","DOI":"10.1090\/psapm\/026\/9888"},{"key":"R43","doi-asserted-by":"crossref","unstructured":"N. Pippenger and G. Lin,\n                      Fault\u2010tolerant circuit\u2010switching networks\n                      , in Proc. 4th Annual ACM Symposium on Parallel Algorithms and Architectures, June 1992, pp. 229\u2013235.","DOI":"10.1145\/140901.141867"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1145\/62044.62050"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"R46","unstructured":"P. Raghavan,\n                      Lecture Notes on Randomized Algorithms\n                      , Research Report RC 15340 (#68237), IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY, Jan. 1990."},{"key":"R47","doi-asserted-by":"crossref","unstructured":"E. J. Schwabe,\n                      On the computational equivalence of hypercube\u2010derived networks\n                      , in Proc. 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, July 1990, pp. 388\u2013397.","DOI":"10.1145\/97444.97706"},{"key":"R48","unstructured":"E. J. Schwabe,\n                      Efficient Embeddings and Simulations for Hypercubic Networks\n                      , Ph.D. thesis, Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, June 1991."},{"key":"R49","unstructured":"S. Sowrirajan and S. M. Reddy,\n                      A design for fault\u2010tolerant full connection networks\n                      , in Proc. International Conference on Science and Systems, IEEE Computer Society Press, Piscataway, NJ, Mar. 1980, pp. 536\u2013540."},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970074"},{"key":"R51","doi-asserted-by":"crossref","unstructured":"H. Tamaki,\n                      Efficient self\u2010embedding of butterfly networks with random faults\n                      , in Proc. 33rd Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Piscataway, NJ, Oct. 1992, pp. 533\u2013541.","DOI":"10.1109\/SFCS.1992.267798"},{"key":"R52","doi-asserted-by":"crossref","unstructured":"H. Tamaki,\n                      Robust bounded\u2010degree networks with small diameters\n                      , in Proc. 4th Annual ACM Symposium on Parallel Algorithms and Architectures, June 1992, pp. 247\u2013256.","DOI":"10.1145\/140901.141866"},{"key":"R53","doi-asserted-by":"crossref","unstructured":"S. Toledo,\n                      Competitive fault\u2010tolerance in area\u2010universal networks\n                      , in Proc. 4th Annual ACM Symposium on Parallel Algorithms and Architectures, June 1992, pp. 236\u2013246.","DOI":"10.1145\/140901.141873"},{"key":"R54","doi-asserted-by":"publisher","DOI":"10.1137\/0211027"},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.1145\/321439.321449"},{"key":"R56","unstructured":"A. Wang and R. Cypher,\n                      Fault\u2010Tolerant Embeddings of Rings, Meshes and Tori in Hypercubes\n                      , Tech. report IBM RJ 8569, IBM Almaden Research Center, San Jose, CA, Jan. 1992."},{"key":"R57","doi-asserted-by":"crossref","unstructured":"A. Wang, R. Cypher, and E. Mayr,\n                      Embedding complete binary trees in faulty hypercubes\n                      , in Proc. 3rd IEEE Symposium on Parallel and Distributed Processing, IEEE Computer Society Press, Piscataway, NJ, Dec. 1991, pp. 112\u2013119.","DOI":"10.1109\/SPDP.1991.218290"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793255163","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:13Z","timestamp":1787336053000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793255163"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":57,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539793255163"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793255163","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}