Optimal adaptive parallel diagnosis for a distributed system modeled by dual-cubes
Problem diagnosis in large distributed computer systems and networks is a challenging task that requires fast and accurate inferences from huge data volumes. In this paper, the PMC diagnostic model are considered and the diagnosis approach in this model is based on end-to-end probing technology. A probe is a test transaction whose outcome depends on some of the systems component; diagnosis is performed by appropriately selecting the probes and analyzing the results. In the PMC mode, every computer can execute a probe to test dedicated systems components. The key point of the PMC model is that any test result reported by a faulty probe station is unreliable and the test result reported by fault-free probe station is always correct The aim of the diagnosis is to locate all faulty components in the system based on the collection of the test results. The fault diagnosis probem in an unstructured network has been shown to be NP-hard. We address an special structured network, namely dual cubes, in this paper. Ann-dimensional dual-cube DC(n) is an (n + 1)-regular spanning subgraph of a (2n + 1)-dimensional hypercube. It uses n-dimensional hypercubes as building blocks and keeps the main desired properties of the hypercube so that it is suitable to be used as a topology of distributed systems. In this paper, we first show that the diagnosability of DC(n) is n + 1 and then show that adaptive diagnosis is possible using at most N + n tests for an TV-nodes distributed system modeled by dual-cubes DC(n) in which at most n + 1 processes are faulty, where N = 22n+1 and n > 1.
Jheng-Cheng Chen Chia-Jui Lai Chang-Hsiung Tsai
Department of Computer Science and Information Engineering National Dong Hwa University Hualien, Taiwan 970, R.O.C.
国际会议
上海
英文
2040-2044
2011-07-26（万方平台首次上网日期，不代表论文的发表时间）