{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T22:40:04Z","timestamp":1736116804728,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540634409"},{"type":"electronic","value":"9783540695493"}],"license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0002735","type":"book-chapter","created":{"date-parts":[[2005,11,23]],"date-time":"2005-11-23T12:29:42Z","timestamp":1132748982000},"page":"208-217","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On the fault tolerance of fat-trees"],"prefix":"10.1007","author":[{"given":"Sotiris","family":"Nikoletseas","sequence":"first","affiliation":[]},{"given":"Grammati","family":"Pantziou","sequence":"additional","affiliation":[]},{"given":"Panagiotis","family":"Psycharis","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Spirakis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,9,26]]},"reference":[{"issue":"1","key":"23_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02579276","volume":"2","author":"M. Ajtai","year":"1982","unstructured":"M. Ajtai, J. Komlos, and E. Szemeredi, \"Largest random component of a k-cube\", Combinatorica, 2(1):1\u20137, 1982.","journal-title":"Combinatorica"},{"key":"23_CR2","unstructured":"N. Alon and J. Spencer, \u201cThe Probabilistic Method\u201d, John Wiley, 1992."},{"key":"23_CR3","unstructured":"P. Bay and G. Bilardi, \u201cAn area-universal VLSI circuit\u201d, in Proc. of the Symp. on Integrated Systems, pp. 53\u201367, 1993."},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"A. Benczur, D. Karger, \u201cApproximating s \u2014 t Minimum Cuts in ~O(n2) time\u201d, in the Proc. of the Symp. on Theory of Computing (STOC'96), pp. 47\u201355, 1996.","DOI":"10.1145\/237814.237827"},{"key":"23_CR5","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/BFb0049427","volume-title":"Algorithms \u2014 ESA '94","author":"Gianfranco Bilardi","year":"1994","unstructured":"G. Bilardi and P. Bay, \u201cAn area lower bound for a class of fat-trees\u201d, in Proceedings of the European Symposium on Algorithms, pp. 413\u2013423, 1994."},{"issue":"3","key":"23_CR6","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1145\/210346.210417","volume":"42","author":"P. Bay","year":"1995","unstructured":"P. Bay and G. Bilardi, \u201cDeterministic on-line routing on area-universal networks\u201d, Journal of the ACM, 42(3): 614\u2013640, 1995.","journal-title":"Journal of the ACM"},{"key":"23_CR7","unstructured":"G. Bilardi, B. Codenotti, G. Del Corso, G. Pinotti and G. Resta, \u201cBroadcast and Associative Operators on Fat-Trees\u201d, to appear in the Proc. of EUROPAR'97."},{"key":"23_CR8","doi-asserted-by":"crossref","unstructured":"R. Cole, B. Maggs and R. Sitaraman, \u201cRouting on butterfly networks with random faults\u201d, in the Proc. of FOCS'95, pp. 558\u2013570, 1995.","DOI":"10.1109\/SFCS.1995.492586"},{"key":"23_CR9","first-page":"17","volume":"5","author":"P. Er\u00f6fis","year":"1960","unstructured":"P. Er\u00f6fis and A. Renyi, \u201cOn the evolution of random graphs\u201d, Publ. Math. Inst. Hungar. Acad. Sci., 5:17\u201361, 1960.","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"23_CR10","unstructured":"R. Greenberg and C. Leiserson, \u201cRandomized routing on fat-trees\u201d, in Randomness and Computation, pp. 345\u2013374, JAI Press, 1989."},{"issue":"12","key":"23_CR11","doi-asserted-by":"publisher","first-page":"1358","DOI":"10.1109\/12.338095","volume":"C-43","author":"R. Greenberg","year":"1994","unstructured":"R. Greenberg, \u201cThe fat-pyramid and universal parallel computation independent of wire delay\u201d, IEEE Transactions on Computers, C-43 (12): 1358\u20131364, 1994.","journal-title":"IEEE Transactions on Computers"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"A.R. Karlin, G. Nelson, and H. Tamaki, \u201cOn the Fault Tolerance of the Butterfly\u201d, in the Proc. of the Symp. on Theory of Computing (STOC'94), pp. 125\u2013133, 1994.","DOI":"10.1145\/195058.195117"},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF01197577","volume":"74","author":"H. Kesten","year":"1981","unstructured":"H. Kesten, \u201cThe critical probability of bond percolation on the square lattice equals \u00bd\u201d, Communication in Mathematical Physics, 74:41\u201359, 1981.","journal-title":"Communication in Mathematical Physics"},{"key":"23_CR14","doi-asserted-by":"crossref","unstructured":"T. Leighton, B. Maggs and R. Sitaraman, \u201cOn the Fault Tolerance of Some Popular Bounded-Degree Networks\u201d, In the Proc. of FOCS'92, pp. 542\u2013552.","DOI":"10.1109\/SFCS.1992.267797"},{"issue":"5","key":"23_CR15","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1109\/12.142684","volume":"41","author":"F. T. Leighton","year":"1992","unstructured":"F. T. Leighton and B. M. Maggs, \u201cFast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks\u201d, In IEEE Transactions on Computers, Vol. 41:5, pp. 578\u2013587, 1992.","journal-title":"IEEE Transactions on Computers"},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"C. Leiserson, Z. Abuharudeh, D. Douglas, C. Feyninan, M. Ganmukhi, J. Hill, W. Hillis, B. Kuszmaul, M. Pierre, D. Wells, M. Wong, S. Yang and R. Zak, \u201cThe network architecture of the Connection Machine CM-5\u201d, in Proc. of the 4th ACM Symp. on Parallel Algorithms and Architectures, pp. 272\u2013285, 1992.","DOI":"10.1145\/140901.141883"},{"issue":"10","key":"23_CR17","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1109\/TC.1985.6312192","volume":"C-34","author":"C. Leiserson","year":"1985","unstructured":"C. Leiserson, \u201cFat-trees: Universal networks for hardware-efficient supercomputing\u201d, IEEE Transactions on Computers, C-34 (10):892\u2013900, 1985.","journal-title":"IEEE Transactions on Computers"},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"T. Leighton, B. Maggs and S. Rao, \u201cUniversal packet routing algorithms\u201d, in Proceedings of the 29th Syrup. on the Foundations of Computer Science, 1988.","DOI":"10.1109\/SFCS.1988.21942"},{"key":"23_CR19","doi-asserted-by":"crossref","unstructured":"R. Motwani, P. Raghavan, \u201cRandomized Algorithms\u201d, Cambridge Univ. Press, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"23_CR20","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1007\/3-540-58201-0_94","volume-title":"Automata, Languages and Programming","author":"S. Nikoletseas","year":"1994","unstructured":"S. Nikoletseas, K. Palein, P. Spirakis and M. Yung, \u201cShort Vertex Disjoint Paths and Multiconnectivity in Random Graphs: Reliable Network Computing\u201d, 21st Col. on Automata, Languages and Programming (ICALP), pp. 508\u2013515, 1994."},{"key":"23_CR21","doi-asserted-by":"crossref","unstructured":"S. Nikoletseas, G. Pantziou, P. Psyclraris, P. Spirakis, \u201cOn the Fault Tolerance of Fat Trees\u201d, Computer Technology Institute Tech. Report, TR.97.05.24, 1996.","DOI":"10.1007\/BFb0002735"},{"key":"23_CR22","doi-asserted-by":"crossref","unstructured":"S. Nikoletseas and P. Spirakis, \u201cExpander Properties in Random Regular Graphs with Edge Faults\u201d, in the Proc. of STACS'95, pp. 421\u2013432, 1995.","DOI":"10.1007\/3-540-59042-0_93"},{"key":"23_CR23","doi-asserted-by":"crossref","unstructured":"H. Tamaki, \u201cEfficient self-embedding of butterfly networks with random faults\u201d, in the Proc. of IEEE FOCS, 1992, pp. 533\u2013541.","DOI":"10.1109\/SFCS.1992.267798"},{"key":"23_CR24","doi-asserted-by":"crossref","unstructured":"S. Toledo, \u201cCompetitive Fault-Tolerance in Area-Universal Networks\u201d, n the Proc. of SPAA'92, 1992, pp. 236\u2013246","DOI":"10.1145\/140901.141873"}],"container-title":["Lecture Notes in Computer Science","Euro-Par'97 Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0002735","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T22:03:47Z","timestamp":1736114627000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0002735"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540634409","9783540695493"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/bfb0002735","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]},"assertion":[{"value":"26 September 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}