On the fault tolerance of the butterfly

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the fault tolerance of the butterfly

Full text

Pdf (826 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 125 - 133

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Anna R. Karlin	DEC Systems Research Center, 130 Lytton Ave., Palo Alto, CA
Greg Nelson	DEC Systems Research Center, 130 Lytton Ave., Palo Alto, CA
Hisao Tamaki	IBM T.J. Watson Research Center, P. O.Box 218 Yorktown Heights, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 15, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/195058.195117 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AKS82	M. Ajtai, j. Koml6s, and E. Szemer#di. Largest random component of a k-cube. Combinatorica, 2(1):1-7, 1982.
	AL91	Bill Aiello , Tom Leighton, Coding theory, hypercube embeddings, and fault tolerance, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.125-136, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113391]
	AS92	N. Alon and J. H. Spencer. The probabilistic method. John Wiley & Sons, New York, 1992.
	ER60	P. Erd6s and A. R#nyi. On the evolution of random graphs. Publ. Math. inst. Hungar. Acad. Sci., 5:17-61, 1960. known from {80185}.
	ES79	P. ErdSs and J. Spencer. Evolution of the n-cube. Computers and Math. with Appli. cations, 5:33-40, 1979.
	HLN87	J. Hastad , T. Leighton , M. Newman, Reconfiguring a hypercube in the presence of faults, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.274-284, January 1987, New York, New York, United States [doi>10.1145/28395.28425]
	HLN89	J. Hastad , T. Leighton, Fast computation using faulty hypercubes, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.251-263, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73031]
	Kes80	H. Kesten. The critical probability of bond percolation on the square lattice equals 1/2. Communication in Mathematical Physics, 74:41-59, 1980.
	KKL+90	C. Kaklamanis, A.R. Karlin, F.T. Leighton, V. Milenkovic, P. Raghavan, S. Rao, C. Thomborson, and A. Tsantilas. Asymptotically tight bounds for computing with faulty arrays of processors. In Proceedings of #he 31s# Annual Symposium on Roundations of Computer Science, pages 285-296. IEEE, 1990.
	LMR	F.T. Leighton, B.M. Maggs, and S.B. Rao. Packet routing and job-shop scheduling in O(congestion + dilation) steps. Combinatorica, to appear.
	LMS92	F. T. Leighton, B. Maggs, and R. Sitaraman. On the unexpected fault-tolerance of some popular bounded-degree networks. In Proceedings of the 33d Annual Symposium on Foundations of Computer Science, pages 542-552. IEEE, 1992.
	Mat92	Thomas R. Mathies, Percolation theory and computing with faulty arrays of processors, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.100-103, September 1992, Orlando, Florida, United States
	Pip92	Nicholas Pippenger, The asymptotic optimality of spider-web networks, Discrete Applied Mathematics, 37-38, p.437-450, July 15, 1992 [doi>10.1016/0166-218X(92)90150-9 ]
	Rag89	P. Raghavan, Robust algorithms for packet routing in a mesh, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.344-350, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72972]
	Tam92	H. Tamaki. Efficient self-embedding of butterfly networks with random faults. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 533-541, 1992.
	Tam93	Hisao Tamaki, Structural robustness of the butterfly and related networks against random faults, University of Toronto, Toronto, Ont., Canada, 1993

CITED BY 6

	Amos Fiat , Jared Saia, Censorship resistant peer-to-peer content addressable networks, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.94-103, January 06-08, 2002, San Francisco, California
	Andreas Goerdt, Random regular graphs with edge faults: expansion through cores, Theoretical Computer Science, v.264 n.1, p.91-125, 08/06/2001
	Hisao Tamaki, Construction of the mesh and the torus tolerating a large number of faults, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.268-277, June 27-29, 1994, Cape May, New Jersey, United States
	Amitabha Bagchi , Ankur Bhargava , Amitabh Chaudhary , David Eppstein , Christian Scheideler, The effect of faults on network expansion, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Ludek Kucera, Wait-Free Deflection Routing of Long Messages, IEEE Transactions on Parallel and Distributed Systems, v.12 n.5, p.476-488, May 2001
	Omer Angel , Itai Benjamini , Eran Ofek , Udi Wieder, Routing complexity of faulty networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA