東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Fault-tolerant broadcasting algorith...

Lo, Nai-Wei.

Linked to FindBook

Google Book

Amazon

博客來

Fault-tolerant broadcasting algorithms for interconnection networks.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Fault-tolerant broadcasting algorithms for interconnection networks./
Author:	Lo, Nai-Wei.
Description:	121 p.
Notes:	Source: Dissertation Abstracts International, Volume: 60-01, Section: B, page: 0301.
Contained By:	Dissertation Abstracts International60-01B.
Subject:	Engineering, Electronics and Electrical. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=9917476
ISBN:	059916378X

Fault-tolerant broadcasting algorithms for interconnection networks.
Lo, Nai-Wei.

Fault-tolerant broadcasting algorithms for interconnection networks. - 121 p.

Source: Dissertation Abstracts International, Volume: 60-01, Section: B, page: 0301.

Thesis (Ph.D.)--State University of New York at Stony Brook, 1998.

In this dissertation we devote ourselves to generate new concepts and develop new methods for fault tolerant broadcasting in the interconnection networks of multicomputer systems. With their numerous attractive features star graph network and two dimensional tori are selected as the target networks to demonstrate our concepts for fault tolerant broadcasting.

ISBN: 059916378XSubjects--Topical Terms:

626636
Engineering, Electronics and Electrical.

Fault-tolerant broadcasting algorithms for interconnection networks.
LDR:03783nmm 2200301 4500 001 1816469
005 20060717100339.5
008 130610s1998 eng d
020 $a 059916378X
035 $a (UnM)AAI9917476
035 $a AAI9917476
040 $a UnM $c UnM
100 1 $a Lo, Nai-Wei. $3 1905847
245 1 0 $a Fault-tolerant broadcasting algorithms for interconnection networks.
300 $a 121 p.
500 $a Source: Dissertation Abstracts International, Volume: 60-01, Section: B, page: 0301.
500 $a Adviser: Bradley S. Carlson.
502 $a Thesis (Ph.D.)--State University of New York at Stony Brook, 1998.
520 $a In this dissertation we devote ourselves to generate new concepts and develop new methods for fault tolerant broadcasting in the interconnection networks of multicomputer systems. With their numerous attractive features star graph network and two dimensional tori are selected as the target networks to demonstrate our concepts for fault tolerant broadcasting.
520 $a For k-star network fault tolerant broadcasting is achieved by constructing an isomorphism of the star network such that the faulty nodes minimally disrupt the message passing sequence. It is shown that in the presence of r (1 ≤ r ≤ k - 2) faults at most r extra steps are required by our algorithm to perform a one-to-all broadcasting in the k-star network. Our algorithm has the same time complexity as an optimal broadcasting algorithm, and since it takes advantage of the hierarchical nature of the star graph network, it can be implemented easily. Our algorithm can also be used to perform all-to-all broadcasting in a faulty star graph.
520 $a For a small-scale multicomputer system in which the number of processors is less than one thousand new optimal fault tolerant broadcasting algorithms are developed to tolerate a small amount of faults and at the same time minimally degrade the performance of broadcast operation. In the presence of up to three faults in a 5p x 5p (p ∈ Z+) two dimensional torus network the proposed algorithms can perform one-to-all broadcasting to all fault-free processors using a minimum number of additional broadcasting steps.
520 $a For a multicomputer system with a large number of processors the probability of having 10 faulty ones is very high in any two-day mission time. Existing fault-tolerant broadcasting algorithms for two dimensional tori/meshes tend to tolerate only a few faults. Unfortunately this level of fault tolerance cannot guarantee the success of executions for time-consuming computational tasks in a large-scale multicomputer system. To achieve such a goal we propose simple broadcasting algorithms to tolerate 98% or more processor failures in a reasonable mission time in a 5p x 5 p torus network. A stochastic fault model for a multicomputer system is applied to further analyze the fault distribution in a two dimensional torus network. According to the analysis a novel one-to-all fault-tolerant broadcasting algorithm for a two dimensional torus network to tolerate up to 24 faults is developed. It is shown in the experimental measurements of the new fault-tolerant broadcasting algorithm that in a 125 x 125 torus the failure possibility of a one-to-all broadcast is less than 2% in a two-day mission time. To the best of our knowledge we are the first to directly address the problem of fault tolerance for broadcasting in an interconnection network with a large number of processor failures. (Abstract shortened by UMI.)
590 $a School code: 0771.
650 4 $a Engineering, Electronics and Electrical. $3 626636
690 $a 0544
710 2 0 $a State University of New York at Stony Brook. $3 1019194
773 0 $t Dissertation Abstracts International $g 60-01B.
790 1 0 $a Carlson, Bradley S., $e advisor
790 $a 0771
791 $a Ph.D.
792 $a 1998
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=9917476