Finding Isolated Cliques by Queries – An Approach to Fault Diagnosis with Many Faults

Algebraic Methods in Computational Complexity

计算机科学;物理学;物理学

William Gasarch1 ; Frank Stephan2 ; 2 National University of Singapore ; Departments of Computer Science and Mathematics ; 3 Science Drive 2 ; Singapore 117543 ; Republic of Singapore

Others  :  http://drops.dagstuhl.de/opus/volltexte/2005/106/pdf/04421.StephanFrank1.106.Paper.pdf
PID  :  6472

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

A well-studied problem in fault diagnosis is to identify theset of all good processors in a given set {p1, p2, . . . , pn} of processors via asking some processors pi to test whether processor pj is good or faulty. Mathematically, the set C of the indices of good processors forms an isolated clique in the graph with the edges E = {(i, j) : if you ask pi to test pj then pi states that “pj is good”}; where C is an isolated clique iff it holds for every i ∈ C and j 6= i that (i, j) ∈ E iff j ∈ C. In the present work, the classical setting of fault diagnosis is modified by no longer requiring that C contains at least n+12 of the n nodes of the graph. Instead, one is given a lower bound a on the size of C and the number n of nodes and one has to find a list of up to n/a candidates containing all isolated cliques of size a or more where the number of queries whether a given edge is in E is as small as possible. It is shown that the number of queries necessary differs at most by n for the case of directed and undirected graphs. Furthermore, for directed graphs the lower bound n2/(2a−2)−3n and the upper bound 2n2/a are established. For some constant values of a, better bounds are given. In the case of parallel queries, the number of rounds is at least n/(a−1)−6