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
BLECHER, PM
[J]. DISCRETE MATHEMATICS, 1983, 43 (01) : 107 - 110
[3] IMPLEMENTATION AND ANALYSIS OF BINOMIAL QUEUE ALGORITHMS
BROWN, MR
[J]. 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
HAKIMI, SL
AMIN, AT
[J]. 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
PREPARATA, FP
METZE, G
CHIEN, RT
[J]. IEEE TRANSACTIONS ON ELECTRONIC COMPUTERS, 1967, EC16 (06): : 848 - +
[9] DATA STRUCTURE FOR MANIPULATING PRIORITY QUEUES
VUILLEMIN, J
[J]. COMMUNICATIONS OF THE ACM, 1978, 21 (04) : 309 - 315

← 1 →