Sparse Networks Tolerating Random Faults

Fremantle, Australia June 23-June 25

DOI Bookmark:

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

1999 International Symposium on Paral ...

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

	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

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.