A Linear Time Algorithm for Sequential Diagnosis in Hypercubes |
| |
Affiliation: | 1. Federal University, Gusau, Nigeria;2. University of Hyderabad, Hyderabad, India;3. Asian Institute of Technology (AIT), Klong Luang, Thailand |
| |
Abstract: | This paper describes a new sequential diagnosis algorithm for hypercubes. The algorithm is based on the PMC model and it assumes the existence of a central observer for syndrome decoding. If we denote the total number of processors in a given hypercube by N, then the algorithm achieves Θ(formula]) degree of diagnosability using only O(N) tests over all iterations of diagnosis and repair. The aggregated syndrome decoding time is also shown to be O(N) for this algorithm. The number of iterations of diagnosis and repair needed by the algorithm is O(log N). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|