An Algorithmic Approach to Conditional-Fault Local Diagnosis of Regular Multiprocessor Interconnected Systems under the PMC Model

ASIAIR > College of Computer Science > Department of Computer Science and Information Engineering > Journal Artical > Item 310904400/25398

Please use this identifier to cite or link to this item: http://asiair.asia.edu.tw/ir/handle/310904400/25398

Title:	An Algorithmic Approach to Conditional-Fault Local Diagnosis of Regular Multiprocessor Interconnected Systems under the PMC Model
Authors:	Cheng-Kuan, L;Lin, Cheng-Kuan;龔自良;Kung, Tzu-Liang;Kueng, Tz-Liang;Jimmy, J.M.T;Jimmy, J.M.Tan
Contributors:	資訊工程學系
Date:	2013-03
Issue Date:	2013-07-11 06:19:45 (UTC+0)
Abstract:	System-level diagnosis is a crucial subject for maintaining the reliability of multiprocessor interconnected systems. Consider a system composed of N independent processors, each of which tests a subset of the others. Under the PMC diagnosis model, Dahbura and Masson proposed an O(N^{2.5}) algorithm to identify the set of faulty processors in a t-diagnosable system, in which at most t processors are permanently faulty. In this paper, we establish some sufficient conditions so that a t-regular system can be conditionally (2t-1)-diagnosable, provided every fault-free processor has at least one fault-free neighbor. Because any t-regular system is no more than t-diagnosable, the approached diagnostic capability is nearly double the classical one-step diagnosability. Furthermore, a correct and complete method is given which exploits these conditions and the presented branch-of-tree architecture to determine the fault status of any single processor. The proposed method has time complexity O(t^2), and thus can diagnose the whole system in time O(t^2 N). In short, not only could the diagnostic capability be proved theoretically, but also it is feasible from an algorithmic perspective.
Relation:	IEEE TRANSACTIONS ON COMPUTERS,V.62 N.3 : 439-451.
Appears in Collections:	[Department of Computer Science and Information Engineering] Journal Artical

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	555	View/Open

Loading...