Fault-tolerant broadcasting in wormhole-routed torus networks

Seungjin Park; S. Seidel; Jong Hoon Youn

doi:10.1109/IPDPS.2002.1015517

Fault-tolerant broadcasting in wormhole-routed torus networks

Seungjin Park, S. Seidel, Jong Hoon Youn

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Scopus citations

Abstract

This paper describes a fault-tolerant broadcast algorithm for wormhole-routed torus networks for which there is only local knowledge of faulty components. This algorithm tolerates tip to k-1 faulty nodes in a k-ary n-cube provided the faults do not cause the network to be disconnected. Based on the fault-tolerant dimension-order unicast communication, this algorithm is deadlock-free and no additional virtual channels are needed. The first stage of this algorithm is itself an optimal broadcast algorithm for a torus if no faults are present. The second stage overcomes the presence of up to k-1 faults with a fixed number of additional message transmissions. Thus, the cost of this algorithm is within a constant factor of the cost of optimal non-fault-tolerant broadcast algorithms.

Original language	English (US)
Title of host publication	Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	371-376
Number of pages	6
ISBN (Electronic)	0769515738, 9780769515731
DOIs	https://doi.org/10.1109/IPDPS.2002.1015517
State	Published - 2002
Externally published	Yes
Event	16th International Parallel and Distributed Processing Symposium, IPDPS 2002 - Ft. Lauderdale, United States Duration: Apr 15 2002 → Apr 19 2002

Publication series

Name	Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002

Other

Other	16th International Parallel and Distributed Processing Symposium, IPDPS 2002
Country/Territory	United States
City	Ft. Lauderdale
Period	4/15/02 → 4/19/02

ASJC Scopus subject areas

Computer Networks and Communications
Modeling and Simulation

Access to Document

10.1109/IPDPS.2002.1015517

Cite this

Park, S., Seidel, S., & Youn, J. H. (2002). Fault-tolerant broadcasting in wormhole-routed torus networks. In Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002 (pp. 371-376). Article 1015517 (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/IPDPS.2002.1015517

Fault-tolerant broadcasting in wormhole-routed torus networks. / Park, Seungjin; Seidel, S.; Youn, Jong Hoon.
Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002. Institute of Electrical and Electronics Engineers Inc., 2002. p. 371-376 1015517 (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Park, S, Seidel, S & Youn, JH 2002, Fault-tolerant broadcasting in wormhole-routed torus networks. in Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002., 1015517, Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002, Institute of Electrical and Electronics Engineers Inc., pp. 371-376, 16th International Parallel and Distributed Processing Symposium, IPDPS 2002, Ft. Lauderdale, United States, 4/15/02. https://doi.org/10.1109/IPDPS.2002.1015517

Park S, Seidel S, Youn JH. Fault-tolerant broadcasting in wormhole-routed torus networks. In Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002. Institute of Electrical and Electronics Engineers Inc. 2002. p. 371-376. 1015517. (Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002). doi: 10.1109/IPDPS.2002.1015517

@inproceedings{2720ea5895524ed18969b06797211dac,

title = "Fault-tolerant broadcasting in wormhole-routed torus networks",

abstract = "This paper describes a fault-tolerant broadcast algorithm for wormhole-routed torus networks for which there is only local knowledge of faulty components. This algorithm tolerates tip to k-1 faulty nodes in a k-ary n-cube provided the faults do not cause the network to be disconnected. Based on the fault-tolerant dimension-order unicast communication, this algorithm is deadlock-free and no additional virtual channels are needed. The first stage of this algorithm is itself an optimal broadcast algorithm for a torus if no faults are present. The second stage overcomes the presence of up to k-1 faults with a fixed number of additional message transmissions. Thus, the cost of this algorithm is within a constant factor of the cost of optimal non-fault-tolerant broadcast algorithms.",

author = "Seungjin Park and S. Seidel and Youn, {Jong Hoon}",

note = "Funding Information: This work is partially supported by NSF grant MRI-9871133. Publisher Copyright: {\textcopyright} 2002 IEEE.; 16th International Parallel and Distributed Processing Symposium, IPDPS 2002 ; Conference date: 15-04-2002 Through 19-04-2002",

year = "2002",

doi = "10.1109/IPDPS.2002.1015517",

language = "English (US)",

series = "Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "371--376",

booktitle = "Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002",

}

TY - GEN

T1 - Fault-tolerant broadcasting in wormhole-routed torus networks

AU - Park, Seungjin

AU - Seidel, S.

AU - Youn, Jong Hoon

PY - 2002

Y1 - 2002

N2 - This paper describes a fault-tolerant broadcast algorithm for wormhole-routed torus networks for which there is only local knowledge of faulty components. This algorithm tolerates tip to k-1 faulty nodes in a k-ary n-cube provided the faults do not cause the network to be disconnected. Based on the fault-tolerant dimension-order unicast communication, this algorithm is deadlock-free and no additional virtual channels are needed. The first stage of this algorithm is itself an optimal broadcast algorithm for a torus if no faults are present. The second stage overcomes the presence of up to k-1 faults with a fixed number of additional message transmissions. Thus, the cost of this algorithm is within a constant factor of the cost of optimal non-fault-tolerant broadcast algorithms.

AB - This paper describes a fault-tolerant broadcast algorithm for wormhole-routed torus networks for which there is only local knowledge of faulty components. This algorithm tolerates tip to k-1 faulty nodes in a k-ary n-cube provided the faults do not cause the network to be disconnected. Based on the fault-tolerant dimension-order unicast communication, this algorithm is deadlock-free and no additional virtual channels are needed. The first stage of this algorithm is itself an optimal broadcast algorithm for a torus if no faults are present. The second stage overcomes the presence of up to k-1 faults with a fixed number of additional message transmissions. Thus, the cost of this algorithm is within a constant factor of the cost of optimal non-fault-tolerant broadcast algorithms.

UR - http://www.scopus.com/inward/record.url?scp=84966659600&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84966659600&partnerID=8YFLogxK

U2 - 10.1109/IPDPS.2002.1015517

DO - 10.1109/IPDPS.2002.1015517

M3 - Conference contribution

AN - SCOPUS:84966659600

T3 - Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002

SP - 371

EP - 376

BT - Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 16th International Parallel and Distributed Processing Symposium, IPDPS 2002

Y2 - 15 April 2002 through 19 April 2002

ER -

Fault-tolerant broadcasting in wormhole-routed torus networks

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this