Analysis of a composite performance reliability measure for fault-tolerant systems

ABSTRACT

Today's concomitant needs for higher computing power and reliability has increased the relevance of multiple-processor fault-tolerant systems. Multiple functional units improve the raw performance (throughput, response time, etc.) of the system, and, as units fail, the system may continue to function albeit with degraded performance. Such systems and other fault-tolerant systems are not adequately characterized by separate performance and reliability measures. A composite measure for the performance and reliability of a fault-tolerant system observed over a finite mission time is analyzed. A Markov chain model is used for system state-space representation, and transient analysis is performed to obtain closed-form solutions for the density and moments of the composite measure. Only failures that cannot be repaired until the end of the mission are modeled. The time spent in a specific system configuration is assumed to be large enough to permit the use of a hierarchical model and static measures to quantify the performance of the system in individual configurations. For a multiple-processor system, where performance measures are usually associated with and aggregated over many jobs, this is tantamount to assuming that the time to process a job is much smaller than the time between failures. An extension of the results to general acyclic Markov chain models is included.

REFERENCES

• 1: Arnold O. Allen, Probability, Statistics, and Queueing Theory with Computer Science Applications, Academic Press, Inc., Orlando, FL, 1978
• 2: François Baccelli , Kishor S. Trivedi, Analysis of M/G/2 - Standby Redundant System, Proceedings of the 9th International Symposium on Computer Performance Modelling, Measurement and Evaluation, p.457-476, May 25-27, 1983
• 3: BARLOW, R. E., AND PROSCHAN, F. Statistical Theory of Reliability and Life Testing Probability Models. Holt, Reinhart, and Winston, Silver Spring, Md., 1981.
• 4: Joel F. Bartlett, A NonStop kernel, Proceedings of the eighth ACM symposium on Operating systems principles, p.22-29, December 14-16, 1981, Pacific Grove, California, United States
• 5: Forest Baskett , K. Mani Chandy , Richard R. Muntz , Fernando G. Palacios, Open, Closed, and Mixed Networks of Queues with Different Classes of Customers, Journal of the ACM (JACM), v.22 n.2, p.248-260, April 1975 [doi>10.1145/321879.321887]
• 6: W. C. Carter, Hardware fault tolerance, Resilient computing systems: vol. 1, John Wiley & Sons, Inc., New York, NY, 1986
• 7: COURTOlS, P.J. Decomposability." Queueing and Computer System Applications. Academic Press, Orlando, Fla., 1977.
• 8: Edmundo de Souza e Silva , H. Richard Gail, Calculating cumulative operational time distributions of repairable computer systems, IEEE Transactions on Computers, v.35 n.4, p.322-332, April 1986 [doi>10.1109/TC.1986.1676765]
• 9: DONATIELLO, L., AND IYER, B.R. Closed-form solution for system availability distribution. IBM Res. Rep. RC I1169. IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., May 1985.
• 10: F'ERRARI, D. Computer Systems, Performance Evaluation. Prentice-Hall, Englewood Cliffs, N.J., 1978.
• 11: FURCHGOTT, D. G., AND MEYER, J.F. A solution method for degradable non-repairable systems. IEEE Trans. Comp. C-33, 6 (June 1984), 550-554.
• 12: GELENBE, E., AND MITRANi, I. Analysis and Synthesis of Computer Systems. Academic Press, London, 1980.
• 13: GOYAL, A., AND TANTAWI, A. N. Evaluation of performability in acyclic markov chain. IBM Res. Rep. RC 10529. IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., May 1984.
• 14: HOWARD, R.A. Dynamic Probabilistic Systems. Vol. II, Semimarkov and Decision. Wiley, New York, N.Y., 1971.
• 15: Ragnar Huslende, A combined evaluation of performance and reliability for degradable systems, Proceedings of the 1981 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.157-164, September 14-16, 1981, Las Vegas, Nevada, United States
• 16: IYER, B.R. Recent results in performability analysis. In Current Advances in Distributed Computing and Communications, Y. Yemini, Ed. Computer Science Press, Rockville, Md., 1987, pp. 50-64.
• 17: Balakrishna R. Iyer , Daniel M. Dias , Philip S. Yu, Performability analysis of operation modes of configurable duplex systems, Proceedings of 1986 ACM Fall joint computer conference, p.785-796, November 1986, Dallas, Texas, United States
• 18: B R Iyer , L Donatiello , P Heidelberger, Analysis of performability for stochastic models of fault-tolerant systems, IEEE Transactions on Computers, v.35 n.10, p.902-907, Oct. 1986 [doi>10.1109/TC.1986.1676681]
• 19: IYER, B. R., Yu, P. S., AND DONATIELLO, L. Analysis of fault-tolerant muitiprocessor architectures for lock engine design. IBM Res. Rep. RC 11314. IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., Aug. 1985.
• 20: KULKARNI, V. G., NICOLA, V. F., AND TRIVEDI, K.S. On modelling the performance and reliability of multi-mode computer systems. J. Syst. Sofiw. 6, 1-2 (May 1986), 175-182.
• 21: G V Kulkarni , F V Nicola , S K Trivedi , M R Smith, A Unified Model for the Analysis of Job Completion Time and Performability Measures in Fault-Tolerant Systems, Duke University, Durham, NC, 1985
• 22: Stephen S. Lavenberg, Computer Performance Modeling Handbook, Academic Press, Inc., Orlando, FL, 1983
• 23: MEYER, J. F. On evaluating performability of degradable computing systems. IEEE Trans. Comput. C-29 (1980), 720-731.
• 24: MEYER, J.F. Closed-form solutions of performability. IEEE Trans. Comput., C-31, 7 (July 1982), 648-657.
• 25: PURl, P.S. A method for studying the integral functionals of stochastic processes with applications: I. Markov chain case. J. Appl. Prob. 8 (1971), 331-343.
• 26: M. Reiser , S. S. Lavenberg, Mean-Value Analysis of Closed Multichain Queuing Networks, Journal of the ACM (JACM), v.27 n.2, p.313-322, April 1980 [doi>10.1145/322186.322195]
• 27: SAUER, C. H., AND CHANDY, K.M. Computer System Performance Modeling. Prentice-Hall, Englewood Cliffs, N.J., 198 i.
• 28: Charles H. Sauer , Edward A. MacNair, Simulation of Computer Communication Systems, Prentice Hall Professional Technical Reference, 1983
• 29: H. D. Schwetman, Hybrid simulation models of computer systems, Communications of the ACM, v.21 n.9, p.718-723, Sept. 1978 [doi>10.1145/359588.359594]
• 30: SERLIN, O. Fault-tolerant systems in commercial applications. Computer C-I 7, 8 (1984), 19-30.
• 31: SIEWIOREK, D.P. Architecture of fault-tolerant computers. Computer C-I 7, 8 (1984), 9-18.
• 32: SIEWIOREK, D. P., AND SWARZ, R.S. The Theory and Practice of Reliable Systems Design. Digital Press, Bedford, Mass., 1982.
• 33: SM,TH, W. L. Renewal theory and its ramifications. J. Roy. Stat. Soc. Set. B. 20 (1958), 243-302.
• 34: Kishar Shridharbhai Trivedi, Probability and Statistics with Reliability, Queuing and Computer Science Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1982
• 35: TOY, W. N., AND GALLAHER, L.E. Overview and architecture of the 3B20D processor. Bell Syst. Tech. J. 62, 1, Part 2, (Jan. 1982), 118-190.
• 36: Philip S. Yu , Daniel M. Dias , John T. Robinson , Balakrishna R. Iyer , Douglas Cornell, Modelling of centralized concurrency control in a multi-system environment, ACM SIGMETRICS Performance Evaluation Review, v.13 n.2, p.183-191, Aug. 1985

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

General Terms:
Algorithms, Measurement, Performance, Reliability, Theory