{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:08Z","timestamp":1787337488701,"version":"build-2736575974"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    We study the embedding of the butterfly network in its faulty version, where each node is independently faulty with some constant probability p. We give a method of such self-embedding of the N-node butterfly with O(1) load, O((log log N)\n                    <jats:sup>2.6<\/jats:sup>\n                    ) dilation, and O((log log N)\n                    <jats:sup>c<\/jats:sup>\n                    ) congestion, which succeeds with probability at least 1 - N\n                    <jats:sup>-1<\/jats:sup>\n                    if p &lt; 1 - \\sqrt{2\/3} \\simeq 0.1835$, where c is a constant that depends on p; c is about 8.84 for p = 0.1 and approaches log\n                    <jats:sub>2<\/jats:sub>\n                    40 \\simeq 5.32$ as $p \\rightarrow 0$. The method is constructive and in fact yields an N log\n                    <jats:sup>O(1)<\/jats:sup>\n                    N time deterministic algorithm to construct the claimed embedding with the claimed success probability when given the random faulty butterfly. We also show that we can make the dilation as low as O(log log N), although at the cost of log\n                    <jats:sup>O(1)<\/jats:sup>\n                    N congestion. These embeddings are level-preserving in the sense that each node is mapped to a node in the same level of the butterfly as the original node. We also derive a lower bound of log log N - o(log log N) on the dilation of a level-preserving embedding with $N^\\alpha$ load, for any constant $\\alpha &lt; 1\/3$ and any constant node-failure probability p &gt; 0. Thus, the bounds on dilation are tight up to a constant factor, as far as level-preserving embeddings are concerned.\n                  <\/jats:p>","DOI":"10.1137\/s0097539794270364","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"614-636","source":"Crossref","is-referenced-by-count":4,"title":["Efficient Self-Embedding of Butterfly Networks with Random Faults"],"prefix":"10.1137","volume":"27","author":[{"given":"Hisao","family":"Tamaki","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"B. Aiello and F. T. Leighton,\n                      Coding theory, hypercube embeddings, and fault tolerance\n                      , in Proceedings of the 3rd ACM Annual Symposium on Parallel Algorithms and Architectures, 1991.","DOI":"10.1145\/113379.113391"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Michael Molloy, The probabilistic method, Algorithms Combin., Vol. 16, Springer, Berlin, 1998, 1\u2013352001a:05135","DOI":"10.1007\/978-3-662-12788-9_1"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"F. Annexstein,\n                      Fault tolerance in hypercube\u2010derivative networks\n                      , in Proceedings of the 1st ACM Annual Symposium on Parallel Algorithms and Architectures, 1989, pp. 179\u2013188.","DOI":"10.1145\/72935.72955"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"K. B Athreya and P. E. Ney,\n                      Branching Processes\n                      , Springer\u2010Verlag, Berlin, 1972.","DOI":"10.1007\/978-3-642-65371-1"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"R. Cole, B. Maggs, and R. Sitaraman,\n                      Routing on butterfly networks with random faults\n                      , in Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995, pp. 558\u2013570.","DOI":"10.1109\/SFCS.1995.492586"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"J. Hastad, F. T. Leighton, and M. Newman,\n                      Fast computation using faulty hypercubes\n                      , in Proceedings of the 21st ACM Annual Symposium on Theory of Computing, 1989, pp. 251\u2013263.","DOI":"10.1145\/73007.73031"},{"key":"R7","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 Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990, pp. 285\u2013296.","DOI":"10.1109\/FSCS.1990.89547"},{"key":"R8","unstructured":"A. Karlin and G. Nelson,\n                      On the existence of the ocean in a faulted butterfly\n                      , Unpublished note, 1989."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"A. Karlin, G. Nelson, and H. Tamaki,\n                      On the fault tolerance of the butterfly\n                      , in Proceedings of the 26th ACM Annual Symposium on Theory of Computing, 1994, pp. 125\u2013133.","DOI":"10.1145\/195058.195117"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"R. Koch, T. Leighton, B. Maggs, S. Rao, and A. Rosenberg,\n                      Work\u2010preserving emulations of fixed\u2010connection networks\n                      , in Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, pp. 227\u2013240.","DOI":"10.1145\/73007.73029"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"F. T. Leighton, B. Maggs, and R. Sitaraman,\n                      On the unexpected fault\u2010tolerance of some popular bounded\u2010degree networks\n                      , in Proceedings of the 33d Annual Symposium on Foundations of Computer Science, 1992, pp. 542\u2013552.","DOI":"10.1109\/SFCS.1992.267797"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215349"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan,\n                      Randomized Algorithms\n                      , Cambridge University Press, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90150-9"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"H. Tamaki,\n                      Efficient self\u2010embedding of butterfly networks with random faults\n                      , in Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992, pp. 533\u2013541.","DOI":"10.1109\/SFCS.1992.267798"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"H. Tamaki,\n                      Robust bounded\u2010degree networks with small diameters\n                      , in Proceedings of the 4th ACM Annual Symposium on Parallel Algorithms and Architectures, 1992, pp. 247\u2013256.","DOI":"10.1145\/140901.141866"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794270364","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:13:32Z","timestamp":1787336012000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794270364"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794270364"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794270364","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}