Fault tolerant communication algorithms on the star network using disjoint paths

	This Article
	PDF RSS feed
	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 P. Fragopoulou Articles by S.G. Akl

28th Hawaii International Conference on System Sciences (HICSS'95)

Fault tolerant communication algorithms on the star network using disjoint paths (PDF)

Hawaii, USA

January 04-January 07

ISBN: 0-8186-6935-7

	ASCII Text	x
	P. Fragopoulou, S.G. Akl, "Fault tolerant communication algorithms on the star network using disjoint paths," Hawaii International Conference on System Sciences, pp. 4, 28th Hawaii International Conference on System Sciences (HICSS'95), 1995.

	BibTex	x
	@article{ 10.1109/HICSS.1995.375483, author = {P. Fragopoulou and S.G. Akl}, title = {Fault tolerant communication algorithms on the star network using disjoint paths}, journal ={Hawaii International Conference on System Sciences}, volume = {0}, year = {1995}, issn = {1060-3425}, pages = {4}, doi = {http://doi.ieeecomputersociety.org/10.1109/HICSS.1995.375483}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Hawaii International Conference on System Sciences TI - Fault tolerant communication algorithms on the star network using disjoint paths SN - 1060-3425 SP EP A1 - P. Fragopoulou, A1 - S.G. Akl, PY - 1995 KW - multiprocessor interconnection networks; fault tolerant computing; trees (mathematics); broadcasting; fault-tolerant communication algorithms; star network; disjoint paths; interconnection networks; node pairs; graph; directed edge-disjoint spanning trees; single-node broadcasting; multinode broadcasting; single-node scattering problem; all-port communication assumption; message transmission; faulty nodes; faulty edges; multinode scattering problem VL - 0 JA - Hawaii International Conference on System Sciences ER -

P. Fragopoulou, Dept. of Comput. & Inf. Sci., Queen's Univ., Kingston, Ont., Canada

S.G. Akl, Dept. of Comput. & Inf. Sci., Queen's Univ., Kingston, Ont., Canada

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/HICSS.1995.375483

One way to achieve fault-tolerant communication on interconnection networks is by exploiting and effectively utilizing the disjoint paths that exist between pairs of source and destination nodes. We construct a graph that consists of n-1 directed edge-disjoint spanning trees on the star network. This graph is used to derive fault-tolerant algorithms for the single-node and multinode broadcasting, and for the single-node and multinode scattering problems under the all-port communication assumption. Fault tolerance is achieved by transmitting the same messages through a number of edge-disjoint spanning trees. These algorithms operate successfully in the presence of up to n-2 faulty nodes or edges in the network.

Index Terms:

multiprocessor interconnection networks; fault tolerant computing; trees (mathematics); broadcasting; fault-tolerant communication algorithms; star network; disjoint paths; interconnection networks; node pairs; graph; directed edge-disjoint spanning trees; single-node broadcasting; multinode broadcasting; single-node scattering problem; all-port communication assumption; message transmission; faulty nodes; faulty edges; multinode scattering problem

Citation:

P. Fragopoulou, S.G. Akl, "Fault tolerant communication algorithms on the star network using disjoint paths," hicss, pp.4, 28th Hawaii International Conference on System Sciences (HICSS'95), 1995

Peer Review Notice | Give Us Feedback

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