Probabilistic diagnosis algorithms tailored to system topology
S. Rangarajan, Donald S. Fussell · 2002
The authors previously (1989) presented algorithms in which if at least two processors perform tests on any given processor, the probability of correct diagnosis approaches one as N to infinity if the number of tests performed by each tester on each processor under test is O(log N). The algorithm was based on a comparison approach to probabilistic system-level fault diagnosis in which processors may perform multiple tests on other processors. Here they present a new hierarchical testing algorithm for this model and show that asymptotically efficient testing can be done when the product of number of testers*number of tests each performs on a processor grows as O(log N) as N to infinity . The method thus preserves the topological flexibility of the previous method, while allowing the number of tests each tester must perform to be tailored to the requirements of the topology.>