Article

Free access

Running algorithms efficiently on faulty hypercubes

Authors:

J. Bruck,

R. Cypher,

D. SorokerAuthors Info & Claims

SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architectures

Pages 37 - 44

https://doi.org/10.1145/97444.97455

Published: 01 May 1990 Publication History

PDF eReader

References

[1]

F. Annexstein. Fault tolerance of hypercube derivative networks. In Proc. 1st Annual A CM Syrup. on Parallel Algorithms and Architectures, pages 179-188, 1986.

Digital Library

Google Scholar

[2]

J. Bruck. Optimal broadcasting in.faulty hypevcubes via edge-disjoint embeddings. IBM Research Report, RJ7147, 1989.

Google Scholar

[3]

B. Becket and H. U. Simon. How robust is the n-cube? In Proc. 27th Annual IEEE Syrup. on Foundations of Computer Science, pages 283-291, 1986.

Google Scholar

[4]

M. Y. Chan and S. J. Lee. Fault-tolerant embeddings of complete binary trees and rings in hypercubes, University of Texas at Dallas Tech. Report, UTDCS-17-89.

Google Scholar

[5]

M. Y. Chan and S. J. Lee. Fault-tolerant permutation routing in hypercubes, University of Texas at Dallas Tech. Report, UTDCS-4-90.

Google Scholar

[6]

D. Dolev, J. Y. Halpern, B. Simons, and R. Strong. A new look at fault-tolerant network routing. Information and Computation, 72(3):180-196, March 1987.

Digital Library

Google Scholar

[7]

J. Hastad, T. Leighton, and M. Newman. Fast computation using faulty hypercubes, in Proc. 21st Annual A CM Symposium on Theory of Computing, pages 251-284, 1989.

Digital Library

Google Scholar

[8]

C. T. tIo and S. L. Johnsson. Embedding meshes in Boolean cubes by graph decomposition. Journal of Parallel and Distributed Computing, April 1990, to appear.

Digital Library

Google Scholar

[9]

D. Kleitman. On the problem by Yuzvinsky on separating the n-cube. Discrete Math. 60:207-213, 1986.

Digital Library

Google Scholar

[10]

T. Leighton and B. Maggs. Expanders might be practical" fast algorithms for routing around faults on multibutterflies. In Proc. 30th Annual IEEE Symp. on Foundations of Computer Science, pages 384-389, 1989.

Digital Library

Google Scholar

[11]

M. Livingston, Q. Stout, N. Graham, and F. Harary. Subcube Fault-Tolerance in Hypercubes. Technical Report CRL-TR-12-87, U. of Michigan Computing Research Laboratory, September 1987.

Google Scholar

[12]

M. Livingston and Q. Stout, Embeddings in Hypercubes. In Mathematical Computer Modelling Vol. 11, pages 222-227.

Digital Library

Google Scholar

[13]

F.P. Preparata and J. VuiUemin. The cubeconnected cylces: a versatile network for parallel computation. Communications of,he A CM, 24(5):300-309, May 1981.

Digital Library

Google Scholar

[14]

M.O. Rabin. Efficient dispersal of information for security, load balancing, and fault tolerance. Journal o} the A CM, 36(2):335-348, April 1989.

Digital Library

Google Scholar

Cited By

View all

de León EOchoa ASantana R(2020)A Genetic Algorithm for a Hamiltonian Path ProblemIndustrial and Engineering Applications of Artificial Intelligence and Expert Systems10.1201/9780429332197-3(13-19)Online publication date: 8-Jan-2020
https://doi.org/10.1201/9780429332197-3
Chan MChin FPoon C(2005)Optimal specified root embedding of full binary trees in faulty hypercubesISA'91 Algorithms10.1007/3-540-54945-5_68(241-250)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-54945-5_68
Parhami BChi-Hsiang Yeh (1998)The robust-algorithm approach to fault tolerance on processor arrays: fault models, fault diameter, and basic algorithmsProceedings of the First Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing10.1109/IPPS.1998.670010(742-746)Online publication date: 1998
https://doi.org/10.1109/IPPS.1998.670010
Show More Cited By

Index Terms

Running algorithms efficiently on faulty hypercubes

Recommendations

Running algorithms efficiently on faulty hypercubes (extended abstract)
Symposium on parallel algorithms and architectures

We examine the issue of running algorithms with a constant factor slowdown on a faulty hypercube in a worst case scenario. We present two sets of novel results related to this issue. We first consider edge faults and show how to tolerate faults with a ...
Various cycles embedding in faulty balanced hypercubes

Consider the balanced hypercube BH n with | F e | 2 n - 3 faulty edges.Prove that every edge of BH n - F e lies on fault-free cycles of even lengths from 6 to 22n.Prove that the lower limit of the length 6 is sharp. Quite a lot of interconnection ...
Embedding Cube-Connected Cycles Graphs into Faulty Hypercubes

We consider the problem of embedding a cube-connected cycles graph (CCC) into a hypercube with edge faults. Our main result is an algorithm that, given a list of faulty edges, computes an embedding of the CCC that spans all of the nodes and avoids all ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architectures

May 1990

417 pages

ISBN:0897913701

DOI:10.1145/97444

Chairman:
F. T. Leighton
Massachusetts Institute of Technology, Cambridge, MA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SPAA90

Sponsor:

Computer Tech Inst.
CTI
SIGACT
SIGARCH
EATCS
IEEE-CS

SPAA90: 2nd Annual ACM Symposium on Parallel Algorithms & Architecture

July 2 - 6, 1990

Island of Crete, Greece

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Upcoming Conference

SPAA '25

Sponsor:
sigact
sigact

37th ACM Symposium on Parallelism in Algorithms and Architectures

July 28 - August 1, 2025

Portland , OR , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
258
Total Downloads

Downloads (Last 12 months)42
Downloads (Last 6 weeks)4

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

de León EOchoa ASantana R(2020)A Genetic Algorithm for a Hamiltonian Path ProblemIndustrial and Engineering Applications of Artificial Intelligence and Expert Systems10.1201/9780429332197-3(13-19)Online publication date: 8-Jan-2020
https://doi.org/10.1201/9780429332197-3
Chan MChin FPoon C(2005)Optimal specified root embedding of full binary trees in faulty hypercubesISA'91 Algorithms10.1007/3-540-54945-5_68(241-250)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-54945-5_68
Parhami BChi-Hsiang Yeh (1998)The robust-algorithm approach to fault tolerance on processor arrays: fault models, fault diameter, and basic algorithmsProceedings of the First Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing10.1109/IPPS.1998.670010(742-746)Online publication date: 1998
https://doi.org/10.1109/IPPS.1998.670010
Yamada TUeno S(1997)Fault-tolerant hypercubes with small degreeProceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN'97)10.1109/ISPAN.1997.645090(179-185)Online publication date: 1997
https://doi.org/10.1109/ISPAN.1997.645090
Yamada TUeno S(1996)Fault-tolerant graphs for toriProceedings Second International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN'96)10.1109/ISPAN.1996.509018(408-414)Online publication date: 1996
https://doi.org/10.1109/ISPAN.1996.509018
Tseng YLai T(1996)On the Embedding of a Class of Regular Graphs in a Faulty HypercubeJournal of Parallel and Distributed Computing10.1006/jpdc.1996.012037:2(200-206)Online publication date: 15-Sep-1996
https://dl.acm.org/doi/10.1006/jpdc.1996.0120
Yamada TYamamoto KUeno S(1995)Fault-tolerant graphs for hypercubes and toriProceedings of the Twenty-Eighth Hawaii International Conference on System Sciences10.1109/HICSS.1995.375507(499-505)Online publication date: 1995
https://doi.org/10.1109/HICSS.1995.375507
Chan BChin FPoon C(1995)Optimal Simulation of Full Binary Trees on Faulty HypercubesIEEE Transactions on Parallel and Distributed Systems10.1109/71.3727766:3(269-286)Online publication date: 1-Mar-1995
https://dl.acm.org/doi/10.1109/71.372776
Yu-Chee Tseng Ten-Hwang Lai (1994)On the embedding of a class of regular graphs in a faulty hypercubeProceedings of 1994 International Conference on Parallel and Distributed Systems10.1109/ICPADS.1994.590360(488-495)Online publication date: 1994
https://doi.org/10.1109/ICPADS.1994.590360
Bruck JCypher RSoroker D(1994)Embedding Cube-Connected Cycles Graphs into Faulty HypercubesIEEE Transactions on Computers10.1109/12.32454643:10(1210-1219)Online publication date: 1-Oct-1994
https://dl.acm.org/doi/10.1109/12.324546
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Running algorithms efficiently on faulty hypercubes (extended abstract)

Various cycles embedding in faulty balanced hypercubes

Embedding Cube-Connected Cycles Graphs into Faulty Hypercubes