Scalable expanders

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Scalable expanders: exploiting hierarchical random wiring

Full text

Pdf (941 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: 144 - 152

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Eric A. Brewer	MIT Laboratory for Computer Science, MIT Artificial Intelligence Laboratory, MIT Department of Mathematics
Frederic T. Chong	MIT Laboratory for Computer Science, MIT Artificial Intelligence Laboratory, MIT Department of Mathematics
Tom Leighton	MIT Laboratory for Computer Science, MIT Artificial Intelligence Laboratory, MIT Department of Mathematics

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): 14, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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.195120 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.

	ALM90	S. Arora , T. Leighton , B. Maggs, On-line algorithms for path selection in a nonblocking network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.149-158, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100232]
	BP74	L. A Bassalygo and M. S. Pinsker. Complexity of optimum nonblocking switching networks without reconnections. Problems oj Information Transmtsston, 9:64-66, 1974.
	CED92	E T. Chong, E. Egozy, and A. DeHon. Fault tolerance and performance of multipath multistage interconnection networks. In T. E Knight Jr. and J. Savage, editors, Advanced Research in VLSI and Parallel Systems 1992, pages 227-242. MIT Press, March 1992.
	CFKA90	David Chaiken , Craig Fields , Kiyoshi Kurihara , Anant Agarwal, Directory-Based Cache Coherence in Large-Scale Multiprocessors, Computer, v.23 n.6, p.49-58, June 1990 [doi>10.1109/2.55500]
	CK92	Frederic T. Chong , Thomas F. Knight, Jr., Design and performance of multipath MIN architectures, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.286-295, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141890]
	Lei85	Charles E. Leiserson, Fat-trees: universal networks for hardware-efficient supercomputing, IEEE Transactions on Computers, v.34 n.10, p.892-901, Oct. 1985
	Lei92	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	LM89	E T. Leighton and B. Maggs. Expanders might be practical: Fast algorithms for routing around faults on multibutterflies. In IEEE 30th Annual Symposium on Foundations o} Computer Sctence, 1989.
	LM92	F. Thomson Leighton , Bruce M. Maggs, Fast Algorithms for Routing Around Faults in Multibutterflies and Randomly-Wired Splitter Networks, IEEE Transactions on Computers, v.41 n.5, p.578-587, May 1992 [doi>10.1109/12.142684]
	MDK91	H. Minsky, A. DeHon, and T. E Kmght Jr. RN 1: Low-latency, dilated, crossbar router In Hot Chips Symposium III, 1991.
	Pip93	Nicholas Pippenger, Self-routing superconcentrators, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.355-361, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167195]
	TMC91	Thinking Machine# Corporation. Cambridge. MA. CM5 Technical Summary, October 1991.
	Upf89	E. Upfal, An O(logN) deterministic packet routing scheme, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.241-249, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73030]
	WZ93	Avi Wigderson , David Zuckerman, Expanders that beat the eigenvalue bound: explicit construction and applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.245-251, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167163]