TY - JOUR
T1 - (t, k)-Diagnosis for Matching Composition Networks Under the MM* Model
AU - Chang, Guey Yun
AU - Chen, Gen Huey
PY - 2007/1/1
Y1 - 2007/1/1
N2 - (t, k)-diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identified and repaired in each iteration provided there are at most t faulty processors, where t > k. In this paper, a (t, k)-diagnosis algorithm under the MM* model is proposed for matching composition networks, which include many well-known interconnection networks, such as hypercubes, crossed cubes, twisted cubes, and Mobius cubes. It is shown that a matching composition network of n dimensions is (Ω(2*log n/n), n)-diagnosable.
AB - (t, k)-diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identified and repaired in each iteration provided there are at most t faulty processors, where t > k. In this paper, a (t, k)-diagnosis algorithm under the MM* model is proposed for matching composition networks, which include many well-known interconnection networks, such as hypercubes, crossed cubes, twisted cubes, and Mobius cubes. It is shown that a matching composition network of n dimensions is (Ω(2*log n/n), n)-diagnosable.
KW - (t, k)-diagnosis
KW - Diagnosability
KW - MM model
KW - matching composition network
KW - multiprocessor system
KW - precise diagnosis strategy
UR - http://www.scopus.com/inward/record.url?scp=85008013289&partnerID=8YFLogxK
U2 - 10.1109/TC.2007.250624
DO - 10.1109/TC.2007.250624
M3 - 期刊論文
AN - SCOPUS:85008013289
SN - 0018-9340
VL - 56
SP - 73
EP - 79
JO - IEEE Transactions on Computers
JF - IEEE Transactions on Computers
IS - 1
ER -