(t, k)-diagnosability of multiprocessor systems with applications to grids and tori

被引：16

作者：

Chang, Guey-Yun ^{[1
]}

Chen, Gen-Huey ^{[2
]}

机构：

[1] Natl Cent Univ, Dept Comp Sci & Informat Engn, Tao Yuan 32001, Taiwan

[2] Natl Taiwan Univ, Dept Comp Sci & Informat Engn, Taipei 10617, Taiwan

来源：

SIAM JOURNAL ON COMPUTING | 2007年 / 37卷 / 04期

关键词：

diagnosability; diagnosis; MM* model; multiprocessor system; PMC model; sequential diagnosis; (t; k)-diagnosis;

D O I：

10.1137/06065043X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

(t, k)-diagnosis, which is a generalization of sequential diagnosis, requires at least k faulty processors identfied and replaced ( or repaired) in each iteration provided there are at most t faulty processors, where t = k. This paper suggests lower bounds on the degrees of (t, k)-diagnosability of multiprocessor systems under both the PMC and the MM* models. As a consequence, grids and tori of d dimensions are shown to be (O(Nd/d+ 1), Omega(d))- diagnosable and (O(Nd/d+ 1), Omega(2d))- diagnosable, respectively, where N is the number of processors.

引用

页码：1280 / 1298

页数：19

共 32 条

[1] Araki T, 2003, IEEE T COMPUT, V52, P971, DOI 10.1109/TC.2003.1214345
[2] Araki T, 2002, IEICE T FUND ELECTR, VE85A, P1152
[3] ARMSTRONG JR, 1981, IEEE T COMPUT, V30, P587, DOI 10.1109/TC.1981.1675844
[4] The bisection width and the isoperimetric number of arrays
Azizoglu, MC
Egecioglu, Ö
[J]. DISCRETE APPLIED MATHEMATICS, 2004, 138 (1-2) : 3 - 12
[5] Edge-isoperimetric problems for cartesian powers of regular graphs
Bezrukov, SL
Elsässer, R
[J]. THEORETICAL COMPUTER SCIENCE, 2003, 307 (03) : 473 - 492
[6] On an equivalence in discrete extremal problems
Bezrukov, SL
[J]. DISCRETE MATHEMATICS, 1999, 203 (1-3) : 9 - 22
[7] BHUYAN LN, 1984, IEEE T COMPUT, V33, P323, DOI 10.1109/TC.1984.1676437
[8] AN ISOPERIMETRIC INEQUALITY ON THE DISCRETE TORUS
BOLLOBAS, B
LEADER, I
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1990, 3 (01) : 32 - 37
[9] BRZRUKOV SL, 2000, ANN COMB, V4, P153
[10] Diagnosability of regular systems
Caruso, A
Chessa, S
Maestrini, P
Santi, P
[J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2002, 45 (02): : 126 - 143

← 1 2 3 4 →