## Abstract

In this paper, assuming that each vertex is neighboring to at least one fault-free vertex, we investigate the (t,k)-diagnosability of a graph G under the PMC model. Lower bounds on the numeric degrees of (t,k)-diagnosability are suggested when G is a general graph or G is a regular graph. In particular, the following results are obtained. Symmetric d-dimensional grids are (N-m\over 2d, min m, 2d-1-diagnosable, where d≥ 2, 1≤ m≤ 2d-1, and N are the number of vertices. Symmetric d-dimensional tori are (N+0.62 2/3-2/4,1)-diagnosable if d=2, and (N-m 2d m, 4d-2)-diagnosable if d≥ 3, where 1≤ m≤ 4d-2. Hypercubes are (N-2 N+2 N ,2 N-2)-diagnosable. Cube-connected cycles are (N-m 3, m, 4)-diagnosable, where 1≤ m ≤ 4; k-ary trees are (N-1 k, 1)-diagnosable.

Original language | English |
---|---|

Article number | 5733340 |

Pages (from-to) | 1797-1803 |

Number of pages | 7 |

Journal | IEEE Transactions on Parallel and Distributed Systems |

Volume | 22 |

Issue number | 11 |

DOIs | |

State | Published - 2011 |

## Keywords

- (t, k)-diagnosis
- Conditional fault
- PMC model
- fault-tolerance
- multiprocessor system
- sequential diagnosis
- system-level diagnosis