An adaptive distributed system-level diagnosis algorithm and its implementation

An adaptive distributed system-level diagnosis algorithm, called Adaptive DSD, suitable for local area networks, is presented. Adaptive DSD assumes a distributed network in which nodes perform tests of other nodes and determine them to be faulty or fault-free. Test results conform to the PMC model of system-level diagnosis. Tests are issued from each node adaptively and depend on the fault situation of the network. Adaptive DSD is proved correct in that each fault-free node reaches an accurate independent diagnosis of the fault conditions of the remaining nodes. Furthermore, no restriction is placed on the number of faulty nodes. The algorithm can diagnose any fault situation with any number of faulty nodes. Adaptive DSD is shown to be a considerable improvement over previous efforts including being optimal in terms of the total number of tests and messages required. The use of the algorithm in an actual distributed network environment and the experimentation within that environment are described.<>