Conditional-Fault Diagnosability of Multiprocessor Systems with an Efficient Local Diagnosis Algorithm under the PMC Model

檔案

日期

2011-10-01

類型

期刊名稱

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS

卷期與頁次

第 22 卷第 10 期,頁 1669–1680

ISSN

1045-9219

語言

英文

摘要

Diagnosis is an essential subject for the reliability of multiprocessor systems. Under the PMC diagnosis model, Dahbura and Masson [12] proposed a polynomial-time algorithm with time complexity O(N(2.5)) to identify all the faulty processors in a system with N processors. In this paper, we present a novel method to diagnose a conditionally faulty system by applying the concept behind the local diagnosis, introduced by Somani and Agarwal [30], and formalized by Hsu and Tan [18]. The goal of local diagnosis is to identify the fault status of any single processor correctly. Under the PMC diagnosis model, we give a sufficient condition to estimate the local diagnosability of a given processor. Furthermore, we propose a helpful structure, called the augmenting star, to efficiently determine the fault status of each processor. For an N-processor system in which every processor has an O(log N) degree, the time complexity of our algorithm to diagnose any given processor is O((log N)(2)), provided that each processor can construct an augmenting star structure of full order in time O((log N)(2)) and the time for a processor to test another one is constant. Therefore, the time totals to O(N(log N)(2)) for diagnosing the whole system.

所屬典藏

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

引用此條目

Lin, C.-K., Kung, T.-L., & Tan, J. J. M. (2011). Conditional-Fault Diagnosability of Multiprocessor Systems with an Efficient Local Diagnosis Algorithm under the PMC Model. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 22(10), 1669–1680. https://doi.org/10.1109/TPDS.2011.46

BibTeX RIS

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

分享

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