A local diagnosability measure for multiprocessor systems

檔案

日期

2007-05-01

類型

期刊名稱

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS

卷期與頁次

第 18 卷第 5 期,頁 598–607

ISSN

1045-9219

語言

英文

摘要

The problem of fault diagnosis has been discussed widely and the diagnosability of many well-known networks has been explored. Under the PMC model, we introduce a new measure of diagnosability, called local diagnosability, and derive some structures for determining whether a vertex of a system is locally t-diagnosable. For a hypercube, we prove that the local diagnosability of each vertex is equal to its degree under the PMC model. Then, we propose a concept for system diagnosis, called the strong local diagnosability property. A system G(V; E) is said to have a strong local diagnosability property if the local diagnosability of each vertex is equal to its degree. We show that an n-dimensional hypercube Q(n) has this strong property, n >= 3. Next, we study the local diagnosability of a faulty hypercube. We prove that Q(n) keeps this strong property even if it has up to n - 2 faulty edges. Assuming that each vertex of a faulty hypercube Q(n) is incident with at least two fault-free edges, we prove Q(n) keeps this strong property even if it has up to 3(n - 2) - 1 faulty edges. Furthermore, we prove that Q(n) keeps this strong property no matter how many edges are faulty, provided that each vertex of a faulty hypercube Q(n) is incident with at least three fault-free edges. Our bounds on the number of faulty edges are all tight.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Hsu, G.-H., & Tan, J. J. M. (2007). A local diagnosability measure for multiprocessor systems. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 18(5), 598–607. https://doi.org/10.1109/TPDS.2007.1022

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/10871