{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T22:55:48Z","timestamp":1762296948982},"reference-count":26,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Inter. Net."],"published-print":{"date-parts":[[2005,3]]},"abstract":"<jats:p> Extensive experiments and experience have shown that the well-known hypercube networks are highly fault tolerant. What is frustrating is that it seems very difficult to properly formulate and formally prove this important fact, despite extensive research efforts in the past two decades. Most proposed fault tolerance models for hypercube networks are only able to characterize very rare extreme situations thus significantly underestimating the fault tolerance power of hypercube networks, while for more realistic fault tolerance models, the analysis becomes much more complicated. In this paper, we develop new techniques that enable us to analyze a more realistic fault tolerance model and derive lower bounds for the probability of hypercube network fault tolerance in terms of node failure probability. Our results are both theoretically significant and practically important. From the theoretical point of view, our method offers very general and powerful techniques for formally proving lower bounds on the probability of network connectivity, while from the practical point of view, our results provide formally proven and precisely given upper bounds on node failure probabilities for manufacturers to achieve a desired probability for network connectivity. Our techniques are also useful and powerful for analysis of the performance of routing algorithms, and applicable to the study of other hierarchical network structures and to other network communication problems. <\/jats:p>","DOI":"10.1142\/s0219265905001290","type":"journal-article","created":{"date-parts":[[2005,5,18]],"date-time":"2005-05-18T08:08:47Z","timestamp":1116403727000},"page":"17-34","source":"Crossref","is-referenced-by-count":17,"title":["Hypercube Network Fault Tolerance: A Probabilistic Approach"],"prefix":"10.1142","volume":"06","author":[{"given":"JIANER","family":"CHEN","sequence":"first","affiliation":[{"name":"Department of Computer Science, Texas A&amp;M University, College Station, TX 77843-3112, USA"},{"name":"College of Information Science and Engineering, Central-South University, ChangSha, Hunan 410083, P.R. China"}]},{"given":"IYAD A.","family":"KANJ","sequence":"additional","affiliation":[{"name":"School of Computer Science, Telecommunications and Information Systems, DePaul University, 243 S. Wabash Avenue, Chicago, IL 60604, USA"}]},{"given":"GUOJUN","family":"WANG","sequence":"additional","affiliation":[{"name":"College of Information Science and Engineering, Central-South University ChangSha, Hunan 410083, P.R. China"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090402"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1109\/12.21148"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1109\/12.61061"},{"key":"rf5","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"1992"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1109\/12.42131"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1109\/12.506426"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1998.1483"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/39.7.626"},{"key":"rf11","first-page":"1042","volume":"46","author":"Gu Q.-P.","journal-title":"IEEE Transactions on Computers"},{"key":"rf12","first-page":"964","volume":"10","author":"Gu Q.-P.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(99)00069-1"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1109\/12.192211"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1109\/12.262126"},{"key":"rf18","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes","author":"Leighton F. T.","year":"1992"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1109\/12.45203"},{"key":"rf23","volume-title":"Fault-Tolerant Computing: Theory and Techniques","author":"Pradhan D. K.","year":"1986"},{"key":"rf24","volume-title":"Fault-Tolerant Computer System Design","author":"Pradhan D. K.","year":"1996"},{"key":"rf25","first-page":"863","volume":"31","author":"Pradhan D. K.","journal-title":"IEEE Transactions on Computers"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1145\/62044.62050"},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1109\/12.2234"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1145\/2465.2467"},{"key":"rf30","first-page":"3051","volume":"42","author":"Stamoulis G. D.","journal-title":"IEEE Transactions on Computers"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1109\/71.242151"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1137\/0211027"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1137\/0219038"},{"key":"rf35","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/12.707589","volume":"47","author":"Wu J.","journal-title":"IEEE Transactions on Computers"}],"container-title":["Journal of Interconnection Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219265905001290","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T23:34:10Z","timestamp":1565134450000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219265905001290"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,3]]},"references-count":26,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2005,3]]}},"alternative-id":["10.1142\/S0219265905001290"],"URL":"https:\/\/doi.org\/10.1142\/s0219265905001290","relation":{},"ISSN":["0219-2659","1793-6713"],"issn-type":[{"value":"0219-2659","type":"print"},{"value":"1793-6713","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,3]]}}}