(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 [J].

Azizoglu, MC ;

Egecioglu, Ö .

DISCRETE APPLIED MATHEMATICS, 2004, 138 (1-2) :3-12

[5] Edge-isoperimetric problems for cartesian powers of regular graphs [J].

Bezrukov, SL ;

Elsässer, R .

THEORETICAL COMPUTER SCIENCE, 2003, 307 (03) :473-492

[6] On an equivalence in discrete extremal problems [J].

Bezrukov, SL .

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 [J].

BOLLOBAS, B ;

LEADER, I .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1990, 3 (01) :32-37

[9]

BRZRUKOV SL, 2000, ANN COMB, V4, P153

[10] Diagnosability of regular systems [J].

Caruso, A ;

Chessa, S ;

Maestrini, P ;

Santi, P .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2002, 45 (02) :126-143

← 1 2 3 4 →