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 ). |
Year | DOI | Venue |
---|---|---|
1995 | 10.1006/jpdc.1995.1046 | J. Parallel Distrib. Comput. |
Keywords | Field | DocType |
sequential diagnosis,linear time algorithm | Discrete mathematics,Binary logarithm,Combinatorics,Computer science,Algorithm,Fault tolerance,Decoding methods,Freivalds' algorithm,Time complexity,Partition (number theory),Observer (quantum physics),Hypercube | Journal |
Volume | Issue | ISSN |
26 | 1 | Journal of Parallel and Distributed Computing |
Citations | PageRank | References |
17 | 0.76 | 14 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sanjeev Khanna | 1 | 17 | 0.76 |
W. Kent Fuchs | 2 | 1469 | 279.02 |