A message-based fault diagnosis procedure

ABSTRACT

A new diagnostic message protocol that provides fault diagnosis capabilities for the communications in a distributed system environment is described. The protocol is designed to operate in conjunction with a standard end-to-end communication protocol and uses special messages to determine the system fault state. A diagnosis message is represented using a test dependency model that is derived from the system topology. These messages are used by an adaptive strategy designed to achieve specific objectives such as reduced testing cost. Using the test dependency model, a general purpose algorithm is developed for generating these strategies based on an information theory criterion. Specific properties of the protocol are discussed, and several examples of strategies for a distributed system topology are provided.

REFERENCES

• 1: Parag K. Lala, Fault tolerant and fault testable hardware design, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 2: P. A. Lee , T. Anderson , J. C. Laprie , A. Avizienis , H. Kopetz, Fault Tolerance: Principles and Practice, Springer-Verlag New York, Inc., Secaucus, NJ, 1990
• 3: J.G. Kuhl and S.M. Reddy, "Fault-Daignosis in Fully Distributed Systems," Pro~. IEEE Intl. Symp. on Fault Tolerant Computing, June, 1951, pp. 100-105.
• 4: T.-Y. Feng and C.-L. Wu, "Fault-Diagnosis for a Class of Multistage Interconnection Networks," IEEE Trans. on Computers, Vol. C-30, No. 10, Oct., 1981, pp. 743-758.
• 5: Nathaniel J. Davis , William T.-Y. Hsu , Howard J. Siegel, Fault location techniques for distributed control interconnection networks, IEEE Transactions on Computers, v.34 n.10, p.902-910, Oct. 1985
• 6: W.Y. Lim, "A Test Strategy for Packet Switching Networks," Proc. Intl. Conf. on Parallel Processing, Aug., 1982, pp. 96-98.
• 7: C.R. Shashidhar and F.P. Coakley, "Fault Diagnosis of SPC Switching Systems Based on Structure and Signalling," Software and Microsystems, Vol. 4, No. 2, April, 1985, pp. 30-34.
• 8: S.A. Bruso, "A Failure Detection and Notification Protocol for Distributed Computing Systems," Proc. Fifth Int. Conf. on Distributed Computing Systems, Mar., 1985, pp. 116-123.
• 9: E.J. KIetsky, "An Application of the Information Theory Approach to Failure Diagnosis," IRE Trans. on Reliability and Quality Control, December 1960, pp. 29-39.
• 10: W.R. Simpson and H.S. Balaban, "The ARINC Research System Testability and Maintenance Program (STAMP)," Proc. iEEE AUTOTESTCON, Dayton, OH, Oct., 1982, pp. 88-95.
• 11: H.S. Balaban and W.R. Simpson, "Testability/Fault Isolation by Adaptive Stra. tegy," Annual Reliability and Maintainability Symposium, Orlando, FL, January 1983, pp. 344-350.
• 12: W.R. Simpson and J.R. Agre, "Experience Gained in Testability Design Tradeoffs," Proc. IEEE AU- TOTESTCON, Washington, DC, Nov., 1984, pp. 279- 286.
• 13: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 14: D.R. Shier and J.D. Spragins, "Exact and Approximate Dependent Failure Reliability Models for Telecommunications Networks," Proc. IEEE INFOCOM, Washington, DC, Mar., 1985, pp. 200-205.
• 15: Y.F. Lain and V.O. Li, "Reliability Modeling and Analysis of Communication Networks With Dependent Failures," Proc. IEEE INFOCOM, Washington, DC, Mar., 1985, pp. 196-199.
• 16: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 17: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 18: R. Strong, "Problems Maintaining Agreement," Proc. Fifth Symp. on Reliability in Distributed Software and Database Systems, Jan., 1986, pp. 20-27.
• 19: P.D. Ezhilchelvan and S.K. Shrivastava, "A Characterization of Faults in Systems," Proc. Fifth Symp. on Reliability in Distributed Software and Database Systems, Jan., 1986, pp. 215-222.
• 20: F.P. Preparata, G. Metze, and R.T. Chien, "On the Connection Assignment Problem of Diagnosable Systems,'' IEEE Trans. on Electronic Computers, Vol. EC-16, No. 6, Dec., 1967, pp. 848-854.
• 21: J.D. Russell and C.R. Kime, "System Fault Diagnosis: Closure and Diagnosability With Repair," IEEE Trans. on Computers, Vol. C-24, No. II, Nov., 1975, pp. 1078-I089.
• 22: J.D. Russell and C.R. Kime, "System Fault Diagnosis: Masking, Exposure, and Diagnosability Without Repair," IEEE Trans. on Computers, Vol. C-24, No. 12, Dec., 1975, pp. 1155-1161.
• 23: K.Y. Chwa and S.L. Hakimi, "On Fault Identification in Diagnosable Systems," iEEE Trans. on Computers, Vol. C-30, No. 6, June, 1981, pp. 414-422.
• 24: P.K. Varshney, C.R. Hartmann, and J.M. Faria, "Application of Information Theory to Sequential Fault Dignosis," IEEE Trans. on Computers, Vol. C-31, No. 2, Feb., 1982, pp. 164-170.
• 25: C.R. Hartmann, P.K. Varshney, K.G. Mehrotra, and C.L. Gerberich, "Application of Information Theory to the Construction of Efficient Decision Trees," IEEE Trans. on Information Theory, Vol. IT-28, No. 4, July, 1982, pp. 565-577.
• 26: Bernard M. E. Moret, Decision Trees and Diagrams, ACM Computing Surveys (CSUR), v.14 n.4, p.593-623, Dec. 1982 [doi>10.1145/356893.356898]
• 27: L.N. Kanal, "Problem-solving Models and Search Strategies for Pattern Recognition," IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. PAMI-I, No. 2, 1979, pp. 193-201.
• 28: James R. Slagle , Richard C. T. Lee, Application of game tree searching techniques to sequential pattern recognition, Communications of the ACM, v.14 n.2, p.103-110, Feb. 1971 [doi>10.1145/362515.362562]
• 29: R.R. Cantonne, et al, "Model-Based Probabilistic Reasoning for Electronic Troubleshooting," Proc. IJCAI- 83, Karlsruhe, Germany, Aug., 1983, pp~ 207-211.
• 30: L. Hyafil and R.L. Rivest, "Constructing Optimal Binary Decision Trees is NP-Complete," Information Processing Letters, Vol. 5, No~ 1, 1976, pp. 15-17.
• 31: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 32: J.R. Agre, "Fault Diagnosis Using the Test Dependency Model," Manuscript in progress, Rockwell International Science Center.
• 33: J.R. Agre and W.R. Simpson, "Adaptive Fault Isolation with Learning," Proc. IEEE AUTOTESTCON, Ft. Worth, TX, pp. 331-335, 1983.
• 34: R. Davis, H. Shrobe, W. llamscher, K. Wieckert, M. Shirley, and S. Polit, "Diagno.gtics Based on Description of Structure and Function," Proc. of Nat. Conf. on Artificial Intelligence (AAAI-82), Pittsburgh, PA, pp. 137-142.
• 35: P.K. Fink, J.C. Lusth, and J.W. Duran, "A Generai Expert System Design for Diagnostic Problem Solving,'' IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. PAMI-7, No. 5, Sep., 1985, pp. 553- 560.
• 36: P.K. Fink, Control and Integration of Diverse Knowledge in a Diagnostic Expert System," Proc. IJCAI-85, Los Angeles, CA, Aug., 1985, pp. 426-431.

INDEX TERMS

Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
  C.2 COMPUTER-COMMUNICATION NETWORKS

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Message sending
      D.4.5 Reliability
          Subjects: Fault-tolerance

General Terms:
Algorithms, Reliability, Standardization, Theory, Verification