Nsv. Rao, ON PARALLEL ALGORITHMS FOR SINGLE-FAULT DIAGNOSIS IN FAULT-PROPAGATION GRAPH SYSTEMS, IEEE transactions on parallel and distributed systems, 7(12), 1996, pp. 1217-1223
Citations number
33
Categorie Soggetti
System Science","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
Systems modeled as directed graphs where nodes represent components an
d edges represent fault propagation between components, are studied fr
om a parallel computation viewpoint. Some of the components are equipp
ed with alarms that ring in response to an abnormal condition. The sin
gle fault diagnosis problem is to compute the set of all potential fai
lure sources, P-S, that correspond to a set of ringing alarms A(R). Th
ere is a lower bound of Omega(e + k(n - k + 1)) for any sequential alg
orithm for this problem (under a decision tree model), where n and e a
re the number of nodes and edges of the graph respectively, and k is t
he number of alrams. Using a CREW PRAM of p less than or equal to k(n
- k + 1)/log k processors, the graph can be preprocessed in O(n(2.81)/
p + log2n) time; then PS can be computed in O(k(n - k + 1)/p + log k)
time. On a hypercube of p less than or equal to k(n-k+1)/log k process
ors, the preprocessng cna be done in O(n2/root p + n(2.61)/p(0.805) nk(n - k + 1)/p) time; then P-S can be computed in O(k(n - k + 1) log
n/p log k + log n) time.