Multi-scale self-simulation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Multi-scale self-simulation: a technique for reconfiguring arrays with faults

Full text

Pdf (1.43 MB)

Source

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

San Diego, California, United States

Pages: 561 - 572

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

Richard Cole
Bruce Maggs
Ramesh Sitaraman

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 19, Citation Count: 7

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/167088.167235 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.

	1	M. Ajtai, N. Alon, J. Bruck, R. Cypher, C. T. Ho, M. Naor, and E. Szemer6di. Fault tolerant graphs, perfect hash functions and disjoint paths. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 693-702, October 1992.
	2	Yonatan Aumann , Michael Ben-Or, Computing with faulty arrays, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.162-169, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129729]
	3	Jehoshua Bruck , Robert Cypher , Ching-Tien Ho, Fault-tolerant meshes with small degree, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.1-10, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165232]
	4	M. R. Fellows. Encoding Graphs in Graphs. PhD thesis, Department of Computer Science, University of California, San Diego, CA, 1985.
	5	Jonathan W. Greene , Abbas El Gamal, Configuration of VLSI Arrays in the Presence of Defects, Journal of the ACM (JACM), v.31 n.4, p.694-717, Oct. 1984 [doi>10.1145/1634.2377]
	6	C. Kaklamanis, A. R. Karfin, 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 the 31st Annual Symposium on Foundations of Computer Science, pages 285-296. IEEE Computer Society Press, October 1990.
	7	R. Koch , T. Leighton , B. Maggs , S. Rao, Work-preserving emulations of fixed-connection networks, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.227-240, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73029]
	8	T. Leighton, B. Maggs, and S. Rao. Universal packet routing algorithms. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 256-271. IEEE Computer Society Press, October 1988.
	9	T. Leighton, B. Maggs, and R. Sitaraman. On the fault tolerance of some popular bounded-degree networks. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pages 542-552, October 1992.
	10	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
	11	Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
	12	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]
	13	E. Schwabe, On the computational equivalence of hypercube-derived networks, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.388-397, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97706]
	14	H. Tamaki. Efficient self-embedding of butterfly networks with random faults. In Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, October 1992. 533-541.
	15	Hisao Tamaki, Robust bounded-degree networks with small diameters, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.247-256, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141866]

CITED BY 7

	Matthew Andrews , Tom Leighton , P. Takis Metaxas , Lisa Zhang, Automatic methods for hiding latency in high bandwidth networks (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.257-265, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	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
	Matthew Andrews , Tom Leighton , P. Takis Metaxas , Lisa Zhang, Improved methods for hiding latency in high bandwidth networks (extended abstract), Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.52-61, June 24-26, 1996, Padua, Italy
	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
	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
	Christos Kaklamanis , Danny Krizanc , Manuela Montangero , Giuseppe Persiano, Efficient automatic simulation of parallel computation on networks of workstations, Discrete Applied Mathematics, v.154 n.10, p.1500-1509, 15 June 2006
	Omer Angel , Itai Benjamini , Eran Ofek , Udi Wieder, Routing complexity of faulty networks, Random Structures & Algorithms, v.32 n.1, p.71-87, January 2008