Browsing by Author "Chiang, Chieh-Feng"

Now showing 1 - 5 of 5

A novel approach to comparison-based diagnosis for hypercube-like systems
(2008-01-01)
Chiang, Chieh-Feng
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
Interconnection network has been an active research area for parallel and distributed computer systems. The diagnosability is one of the important issues in the reliability of interconnection networks. In this paper, a novel idea on system diagnosis called local diagnosability is presented. The concept of local diagnosability is strongly related to the traditional global one. For this local sense, the status of every particular processor can be correctly identified. A sufficient condition is also proposed to determine the local diagnosability of a given processor. Following this local sense, we prove that the diagnosability of an n-dimensional hypercube-like network HLn is n for n >= 5, and show that in HLn with up to n - 2 faulty links, the local diagnosability of each processor equals to the connection links incident with it.
Conditional diagnosability of hypercubes under the comparison diagnosis model
(2009-02-01)
Hsu, Guo-Huang
;
Chiang, Chieh-Feng
;
Shih, Lun-Min
;
Hsu, Lih-Hsing
;
Tan, Jimmy J. M.
Processor fault diagnosis plays an important role in multiprocessor systems for reliable computing, and the diagnosability of many well-known networks has been explored. Lai et al. proposed a novel measure of diagnosability, called conditional diagnosability, by adding an additional condition that any faulty set cannot contain all the neighbors of any vertex in a system. We make a contribution to the evaluation of diagnosability for hypercube networks under the comparison model and prove that the conditional diagnosability of n-dimensional Hypercube Q(n) is 3(n - 2) + 1 for n >= 5. The conditional diagnosability of Q. is about three times larger than the classical diagnosability of Q(n). (C) 2008 Elsevier B.V. All rights reserved.
Diagnosability of star graphs with missing edges
(2012-04-01)
Chiang, Chieh-Feng
;
Hsu, Guo-Huang
;
Shih, Lun-Min
;
Tan, Jimmy J. M.
;
資訊工程學系
In this paper, we study the system diagnosis on an n-dimensional star under the comparison model. Following the concept of local diagnosability [3], the strong local diagnosability property [7] is discussed; this property describes the equivalence of the local diagnosability of a node and its degree. We prove that an n-dimensional star has this property, and it keeps this strong property even if there exist n - 3 missing edges in it. (C) 2011 Elsevier Inc. All rights reserved.
Strong Menger connectivity with conditional faults on the class of hypercube-like networks
(2008-04-15)
Shih, Lun-Min
;
Chiang, Chieh-Feng
;
Hsu, Lih-Hsing
;
Tan, Jimmy J. M.
;
資訊工程學系
In this paper, we study the Menger property on a class of hypercube-like networks. We show that in all n-dimensional hypercubelike networks with n - 2 vertices removed, every pair of unremoved vertices u and v are connected by min{deg(u), deg(v)} vertex-disjoint paths, where deg(u) and deg(v) are the remaining degree of vertices u and v, respectively. Furthermore, under the restricted condition that each vertex has at least two fault-free adjacent vertices, all hypercube-like networks still have the strong Menger property, even if there are up to 2n - 5 vertex faults. (C) 2007 Elsevier B.V. All rights reserved.
Using Node Diagnosability to Determine t-Diagnosability under the Comparison Diagnosis Model
(2009-02-01)
Chiang, Chieh-Feng
;
Tan, Jimmy J. M.
;
資訊工程學系
;
Department of Computer Science
Diagnosis is an essential subject for the reliability of a multiprocessor system. Under the comparison diagnosis model, Sengupta and Dahbura proposed a polynomial-time algorithm with time complexity O(N(5)) to identify all the faulty processors for a given syndrome in a system with N processors. In this paper, we present a novel idea on system diagnosis called node diagnosability. The node diagnosability can be viewed as a local strategy toward system diagnosability. There is a strong relationship between the node diagnosability and the traditional diagnosability. For this local sense, we focus more on a single processor and require only identifying the status of this particular processor correctly. Under the comparison diagnosis model, we propose a sufficient condition to determine the node diagnosability of a given processor. Furthermore, we propose a useful local structure called an extended star to guarantee the node diagnosability and provide an efficient algorithm to determine the faulty or fault-free status of each processor based on this structure. For a multiprocessor system with total number of processors N, the time complexity of our algorithm to diagnose a given processor is O(log N) and that to diagnose all the faulty processors is O(N log N) under the comparison model, provided that there is an extended star structure at each processor and that the time for looking up the testing result of a comparator in the syndrome table is constant.