We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Professor Iain Stewart

Stewart, I.A. (2010), A general algorithm for detecting faults under the comparison diagnosis model, 24th IEEE International Parallel and Distributed Processing Symposium, IPDPS'10,. Atlanta, Georgia, U.S.A., IEEE Computer Society Press, Piscataway, 1-9.

Author(s) from Durham


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.