Coding theory, hypercube embeddings, and fault tolerance

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Coding theory, hypercube embeddings, and fault tolerance

Full text

Pdf (1.23 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the third annual ACM symposium on Parallel algorithms and architectures table of contents

Hilton Head, South Carolina, United States

Pages: 125 - 136

Year of Publication: 1991

ISBN:0-89791-438-4

Authors

Bill Aiello	Bellcore, Morristown, NJ
Tom Leighton	Mathematics Department and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 17, Citation Count: 20

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/113379.113391 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	B. Aiello , F. T. Leighton , B. Maggs , M. Newman, Fast algorithms for bit-serial routing on a hypercube, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.55-64, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97459]
	2	M. Baumslag, 1990. Personal communication.
	3	B. Becker and H. U. Simon. How robust is the n-cube? In Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pages 283-291, 1986.
	4	S. N. Bhatt and J. Cal. Take a walk, grow a tree. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 469- 478, 1988.
	5	S. N. Bhatt, F. R. K. Chung, F. T. Leighton, and A. L. Rosenberg. Optimal simulations of tree machines. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pages 274-282. IEEE, Oct. 1986.
	6	Sandeep Bhatt , David Greenberg , Tom Leighton , Pangfeng Liu, Tight bounds for on-line tree embeddings, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.344-350, January 28-30, 1991, San Francisco, California, United States
	7	J. Bruck , R. Cypher , D. Soroker, Running algorithms efficiently on faulty hypercubes, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.37-44, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97455]
	8	D. Greenberg , S. Bhatt, Routing multiple paths in hypercubes, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.45-54, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97457]
	9	R. W. Ilamming. Error detecting and error correcting codes. Bell System Technical Journal, 29:147-160, 1950.
	10	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]
	11	R. R. Koch. Increasing the size of a network by a constant factor can increase performance by more than a constant factor. In Proceedings of the 29th Annual Symposium on Foundations of Compuler Science, pages 221-230. IEEE, Oct. 1988.
	12	T. Leighton , M. Newman , A. G. Ranade , E. Schwabe, Dynamic tree embeddings in butterflies and hypercubes, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.224-234, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72959]
	13	M. Livingston, Q. Stout, N. Graham, and F. Hararay. Subcube fault-tolerance in hypercubes. Technical Report CRL-TR-12-87, U. of Michigan Computing Research Laboratory, Sept. 1987.
	14	David Peleg , Jeffrey D. Ullman, An optimal synchronizer for the hypercube, SIAM Journal on Computing, v.18 n.4, p.740-747, Aug. 1989 [doi>10.1137/0218050]
	15	W. Stahnke. Primitive binary polynomials. Mathematics of Computation, 27(124):977-980, Oct. 1973.

CITED BY 20

	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
	Sivan Toledo, Competitive fault-tolerance in area-universal networks, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.236-246, June 29-July 01, 1992, San Diego, California, United States
	Christos Kaklamanis , Danny Krizanc , Satish Rao, New graph decompositions and fast emulations in hypercubes and butterflies, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.325-334, June 30-July 02, 1993, Velen, Germany
	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
	Keqin Li, Maintenance of tree structured computations on parallel and distributed computer systems, Proceedings of the 1996 ACM symposium on Applied Computing, p.337-343, February 17-19, 1996, Philadelphia, Pennsylvania, United States
	William Aiello , Baruch Awerbuch , Bruce Maggs , Satish Rao, Approximate load balancing on dynamic and asynchronous networks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.632-641, May 16-18, 1993, San Diego, California, United States
	Anna R. Karlin , Greg Nelson , Hisao Tamaki, On the fault tolerance of the butterfly, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.125-133, May 23-25, 1994, Montreal, Quebec, Canada
	Satoshi Fujita , Arthur M. Farley, Sparse hypercube: a minimal k-line broadcast graph, Discrete Applied Mathematics, v.127 n.3, p.431-446, 01 May 2003
	Keqin Li, On dynamic tree growing in hypercubes, Proceedings of the 1997 ACM symposium on Applied computing, p.496-503, April 1997, San Jose, California, United States
	Keqin Li, Performance evaluation of probabilistic tree embedding in cube-connected cycles, Proceedings of the 1998 ACM symposium on Applied Computing, p.584-592, February 27-March 01, 1998, Atlanta, Georgia, United States
	Pei-Ji Yang , C. s. Raghavendra , Sing-Ban Tien, Free Dimensions-An Effective Approach to Achieving Fault Tolerance in Hypercubes, IEEE Transactions on Computers, v.44 n.9, p.1152-1157, September 1995
	Pei-Ji Yang , Sing-Ban Tien , C. S Raghavendra, Embedding of Rings and Meshes onto Faulty Hypercubes Using Free Dimensions, IEEE Transactions on Computers, v.43 n.5, p.608-613, May 1994
	Nian-Feng Tzeng , Guanghua Lin, Efficient Determination of Maximum Incomplete Subcubes in Hypercubes with Faults, IEEE Transactions on Computers, v.45 n.11, p.1303-1308, November 1996
	Jehoshua Bruck , Robert Cypher , Danny Soroker, Tolerating Faults in Hypercubes Using Subcube Partitioning, IEEE Transactions on Computers, v.41 n.5, p.599-605, May 1992
	Keqin Li, On the performance of randomized embedding of reproduction trees in static networks, International Journal of Parallel Programming, v.31 n.5, p.393-406, October 2003
	Keqin Li, Analysis of randomized load distribution for reproduction trees in linear arrays and rings, Theoretical Computer Science, v.321 n.2-3, p.195-214, 16 August 2004
	J. Bruck , R. Cypher , D. Soroker, Embedding Cube-Connected Cycles Graphs into Faulty Hypercubes, IEEE Transactions on Computers, v.43 n.10, p.1210-1219, October 1994
	Kieran T. Herley , Andrea Pietracaprina , Geppino Pucci, Deterministic parallel backtrack search, Theoretical Computer Science, v.270 n.1-2, p.309-324, January
	Keqin Li, Design and analysis of asymptotically optimal randomized tree embedding algorithms in static networks, Performance Evaluation, v.60 n.1-4, p.141-163, May 2005
	Jacques Bahi , Raphaël Couturier , Flavien Vernier, Synchronous distributed load balancing on dynamic networks, Journal of Parallel and Distributed Computing, v.65 n.11, p.1397-1405, November 2005