Interpretation of diagnosis problem of system level self-diagnosis

The paper represents the analysis of the main issues of system level self-diagnosis and explanation of its three basic problems. The main attention is paid to the problem of diagnosis which is expressed with the help of set theory. The influence of made assumptions concerning the allowable faulty sets on the diagnosis results is discussed with the help of simple example.

  1. Preparata T., Metze G., Chien R. On the connection assignment problem of diagnosable system. IEEE Transactions on Electronic Computers. EC-16, n.12, 848–854 (1967).
  2. Barborak M., Malek M., Dahbura A. The consensus problem in fault-tolerant computing. ACM Computing Surveys. 25, n.2, 171–220 (1993).
  3. Somani A. K. System Level Diagnosis: A Review. (1997) [online]. Available from
  4. Chang Y. M., Yeh J. M. A new sequential diagnosis algorithm in hypercubes with high diagnosability. In International Computer Symposium, Taiwan (2004).
  5. Somani A. K., Agarwal V. K., Avis D. A generalized theory for system level diagnosis. IEEE Trans. Comput. C-36, 538–546 (1987).
  6. Fujiwara H., Kinoshita K. Some existence theorems for probabilistically diagnosable systems. IEEE Trans. on Comp. C-27, n.4, 297–303 (1981).
  7. Blount M. L. Probabilistic treatment of diagnosis in digital systems. In 7th IEEE Int. Symp. On Fault-Tolerant Computing. 72–77 (1977).
  8. Barsi T., Grandoni T., Maestrini P. A theory of diagnosability of digital systems. In IEEE Trans. on Comput. C-25, n.6, 585–593 (1976).
  9. Dahbura A., Masson G. An O(N2.5) fault identification algorithm for diagnosable systems. IEEE Trans. Comput. C-33, 486–492 (1984).
  10. Sullivan G. An O(t3 + |E|) fault identification algorithm for diagnosable systems. IEEE Trans. Comput. C-37, 388–397 (1988).
  11. Meyer G., Masson G. An efficient fault diagnosis algorithm for symmetric multiple processor architectures. IEEE Trans. Comput. C-27, 1059–1063 (1978).