Reliability of Computer Systems and Networks

MARTIN L. SHOOMAN, PhD, served for many years as a Professor of Electrical Engineering and Computer Science at Polytechnic University in Brooklyn, New York. Dr. Shooman has been a Visiting Professor at MIT and Hunter College, and a consultant to Bell Laboratories, NASA, IBM, the US Army, and many other government and commercial organizations. A fellow of the IEEE, he has received five best paper awards from their Reliability and Computer Societies. Dr. Shooman has contributed to over 100 papers and reports to the research literature and has given special courses in Britain, Canada, France, Israel, and throughout the US. The author of Probabilistic Reliability: An Engineering Approach and Software Engineering: Design, Reliability, and Management, he is currently President of the consulting firm Martin L. Shooman & Associates.

Preface. 1 Introduction.

1.1 What is Fault-Tolerant Computing?

1.2 The Rise of Microelectronics and the Computer.

1.3 Reliability and Availability.

1.4 Organization of the Book.

2 Coding Techniques.

2.1 Introduction.

2.2 Basic Principles.

2.3 Parity-Bit Codes.

2.4 Hamming Codes.

2.5 Error-Detection and Retransmission Codes.

2.6 Burst Error-Correction Codes.

2.7 Reed–Solomon Codes.

2.8 Other Codes.

3 Redundancy, Spares, and Repairs.

3.1 Introduction.

3.2 Apportionment.

3.3 System Versus Component Redundancy.

3.4 Approximate Reliability Functions.

3.5 Parallel Redundancy.

3.6 An r-out-of-n Structure.

3.7 Standby Systems.

3.8 Repairable Systems.

3.9 RAID Systems Reliability.

3.10 Typical Commercial Fault-Tolerant Systems: Tandem and Stratus.

4 N-Modular Redundancy.

4.1 Introduction.

4.2 The History of N-Modular Redundancy.

4.3 Triple Modular Redundancy.

4.4 N-Modular Redundancy.

4.5 Imperfect Voters.

4.6 Voter Logic.

4.7 N-Modular Redundancy with Repair.

4.8 N-Modular Redundancy with Repair and Imperfect Voters.

4.9 Availability of N-Modular Redundancy with Repair and Imperfect Voters.

4.10 Microcode-Level Redundancy.

4.11 Advanced Voting Techniques.

5 Software Reliability and Recovery Techniques.

5.1 Introduction.

5.2 The Magnitude of the Problem.

5.3 Software Development Life Cycle.

5.4 Reliability Theory.

5.5 Software Error Models.

5.6 Reliability Models.

5.7 Estimating the Model Constants.

5.8 Other Software Reliability Models.

5.9 Software Redundancy.

5.10 Rollback and Recovery.

6 Networked Systems Reliability.

6.1 Introduction.

6.2 Graph Models.

6.3 Definition of Network Reliability.

6.4 Two-Terminal Reliability.

6.5 Node Pair Resilience.

6.6 All-Terminal Reliability.

6.7 Design Approaches.

7 Reliability Optimization.

7.1 Introduction.

7.2 Optimum Versus Good Solutions.

7.3 A Mathematical Statement of the Optimization Problem.

7.4 Parallel and Standby Redundancy.

7.5 Hierarchical Decomposition.

7.6 Apportionment.

7.7 Optimization at the Subsystem Level via Enumeration.

7.8 Bounded Enumeration Approach.

7.9 Apportionment as an Approximate Optimization Technique.

7.10 Standby System Optimization.

7.11 Optimization Using a Greedy Algorithm.

7.12 Dynamic Programming.

7.13 Conclusion.

Appendix A Summary of Probability Theory.

A1 Introduction.

A2 Probability Theory.

A3 Set Theory.

A4 Combinatorial Properties.

A5 Discrete Random Variables.

A6 Continuous Random Variables.

A7 Moments.

A8 Markov Variables.

Appendix B Summary of Reliability Theory.

B1 Introduction.

B2 Combinatorial Reliability.

B3 Failure-Rate Models.

B4 System Reliability.

B5 Illustrative Example of Simplified Auto Drum Brakes.

B5.6 Summary.

B6 Markov Reliability and Availability Models.

B7 Repairable Systems.

B8 Laplace Transform Solutions of Markov Models.

Appendix C Review of Architecture Fundamentals.

C1 Introduction to Computer Architecture.

C2 Logic Gates, Symbols, and Integrated Circuits.

C3 Boolean Algebra and Switching Functions.

C4 Switching Function Simplification.

C5 Combinatorial Circuits.

C6 Common Circuits: Parity-Bit Generators and Decoders.

C7 Flip-Flops.

C8 Storage Registers.

Appendix D Programs for Reliability Modeling and Analysis.

D1 Introduction.

D2 Various Types of Reliability and Availability Programs.

D3 Testing Programs.

D4 Partial List of Reliability and Availability Programs.

D5 An Example of Computer Analysis.

Name Index.

Subject Index.