A PARALLEL FAULT IDENTIFICATION ALGORITHM

被引：7

作者：

SCHMEICHEL, E

HAKIMI, SL

OTSUKA, M

SULLIVAN, G

机构：

[1] SAN JOSE STATE UNIV,DEPT MATH & COMP SCI,SAN JOSE,CA 95192

[2] UNIV CALIF DAVIS,DEPT ELECT ENGN & COMP SCI,DAVIS,CA 95616

[3] JOHNS HOPKINS UNIV,DEPT COMP SCI,BALTIMORE,MD 21218

来源：

JOURNAL OF ALGORITHMS | 1990年 / 11卷 / 02期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0196-6774(90)90004-X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Consider a system of n units, at most t < n 2 of which are faulty. Suppose each unit is capable of testing any other unit for a possible fault, but that results of tests performed by faulty units might be incorrectly or even maliciously reported. We give an adaptive algorithm which identifies the faulty units in O(1 + log[ n t]t) rounds of testing using O(n) tests. Previous adaptive algorithms required at least t + logn rounds of testing and n + t - 1 tests. If t < n1-e, our algorithm runs within O(1) rounds. © 1990.

引用

页码：231 / 241

页数：11

共 9 条

[1]

BEIGEL R, 1989, IN PRESS 1ST P ACM S

[2] ON A LOGICAL PROBLEM [J].

BLECHER, PM .

DISCRETE MATHEMATICS, 1983, 43 (01) :107-110

[3] IMPLEMENTATION AND ANALYSIS OF BINOMIAL QUEUE ALGORITHMS [J].

BROWN, MR .

SIAM JOURNAL ON COMPUTING, 1978, 7 (03) :298-319

[4]

HAKIMI SL, 1984, J ALGORITHM, V5, P526, DOI 10.1016/0196-6774(84)90005-1

[5]

HAKIMI SL, 1984, IEEE T COMPUT, V33, P234, DOI 10.1109/TC.1984.1676420

[6] CHARACTERIZATION OF CONNECTION ASSIGNMENT OF DIAGNOSABLE SYSTEMS [J].

HAKIMI, SL ;

AMIN, AT .

IEEE TRANSACTIONS ON COMPUTERS, 1974, C 23 (01) :86-88

[7]

OTSUKA M, 1986, JUL P JAP US S FELX, P653

[8] ON CONNECTION ASSIGNMENT PROBLEM OF DIAGNOSABLE SYSTEMS [J].

PREPARATA, FP ;

METZE, G ;

CHIEN, RT .

IEEE TRANSACTIONS ON ELECTRONIC COMPUTERS, 1967, EC16 (06) :848-+

[9] DATA STRUCTURE FOR MANIPULATING PRIORITY QUEUES [J].

VUILLEMIN, J .

COMMUNICATIONS OF THE ACM, 1978, 21 (04) :309-315

← 1 →