Sparse Networks Tolerating Random Faults

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Toshinori Yamada Articles by Shuichi Ueno

1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99)

Fremantle, Australia

June 23-June 25

ISBN: 0-7695-0231-8

	ASCII Text	x
	Toshinori Yamada, Shuichi Ueno, "Sparse Networks Tolerating Random Faults," Parallel Architectures, Algorithms, and Networks, International Symposium on, pp. 114, 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), 1999.

	BibTex	x
	@article{ 10.1109/ISPAN.1999.778926, author = {Toshinori Yamada and Shuichi Ueno}, title = {Sparse Networks Tolerating Random Faults}, journal ={Parallel Architectures, Algorithms, and Networks, International Symposium on}, volume = {0}, year = {1999}, issn = {1087-4089}, pages = {114}, doi = {http://doi.ieeecomputersociety.org/10.1109/ISPAN.1999.778926}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Parallel Architectures, Algorithms, and Networks, International Symposium on TI - Sparse Networks Tolerating Random Faults SN - 1087-4089 SP EP A1 - Toshinori Yamada, A1 - Shuichi Ueno, PY - 1999 KW - Circulant Graphs KW - Hypercubic Graphs KW - Random-Fault-Tolerant Graphs KW - Multi-processor Systems KW - Interconnection Networks VL - 0 JA - Parallel Architectures, Algorithms, and Networks, International Symposium on ER -

Toshinori Yamada, Tokyo Institute of Technology

Shuichi Ueno, Tokyo Institute of Technology

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.1999.778926

This paper proposes a general method to construct a fault-tolerant network G* for any network G with N processors such that G* has O(N) processors and contains a fault-free isomorphic copy of G with high probability even if processors fail independently with constant probability. Based on the construction, we also show that we can construct such fault-tolerant networks with O(N) processors and O(M log N) communication links for a circulant network, hypercube, de Bruijn network, shuffle-exchange network, and cube-connected-cycles with N processors and M communication links.

Index Terms:

Circulant Graphs, Hypercubic Graphs, Random-Fault-Tolerant Graphs, Multi-processor Systems, Interconnection Networks

Citation:

Toshinori Yamada, Shuichi Ueno, "Sparse Networks Tolerating Random Faults," ispan, pp.114, 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), 1999

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.