A general algorithm for detecting faults under the comparison diagnosis model

Stewart, I.A.

Abstract

We develop a widely applicable algorithm to solve the fault diagnosis problem in certain distributed-memory multiprocessor systems in which there are a limited number of faulty processors. In particular, we prove that if the underlying graph G = (V,E) forming the interconnection network has connectivity no less than its diagnosability δ and can be partitioned into enough connected components of large enough size then given a syndrome of test results under the comparison diagnosis model resulting from some set of faulty nodes of size at most δ, we can find the actual set of faulty nodes with time complexity O(ΔN), where Δ is the maximal degree of any node of the graph and N is the number of nodes.

Citation

Stewart, I. (2010, April). A general algorithm for detecting faults under the comparison diagnosis model. Presented at 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2010), Atlanta, Georgia, U.S.A

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2010)
• Start Date: Apr 19, 2010
• End Date: Apr 23, 2010
• Online Publication Date: May 24, 2010
• Publication Date: Apr 1, 2010
• Deposit Date: Dec 18, 2009
• Publicly Available Date: Jun 29, 2010
• Pages: 1-9
• Series ISSN: 1530-2075
• Book Title: 2010 IEEE International Symposium on Parallel and Distributed Processing IPDPS, 19-23 April 2010, Atlanta GA, ; proceedings.
• DOI: https://doi.org/10.1109/ipdps.2010.5470369
• Keywords: Interconnection networks, Fault diagnosis, Comparison diagnosis model.
• Public URL: https://durham-repository.worktribe.com/output/1160757