Fault-Tolerant Systems (Second Edition)

Fault-Tolerant Systems, Second Edition, is the first book on fault tolerance design utilizing a systems approach to both hardware and software. No other text takes this approach or offers the comprehensive and up-to-date treatment that Koren and Krishna provide. The book comprehensively covers the design of fault-tolerant hardware and software, use of fault-tolerance techniques to improve manufacturing yields, and design and analysis of networks. Incorporating case studies that highlight more than ten different computer systems with fault-tolerance techniques implemented in their design, the book includes critical material on methods to protect against threats to encryption subsystems used for security purposes. The text’s updated content will help students and practitioners in electrical and computer engineering and computer science learn how to design reliable computing systems, and how to analyze fault-tolerant computing systems. Delivers the first book on fault tolerance design with a systems approach Offers comprehensive coverage of both hardware and software fault tolerance, as well as information and time redundancy Features fully updated content plus new chapters on failure mechanisms and fault-tolerance in cyber-physical systems Provides a complete ancillary package, including an on-line solutions manual for instructors and PowerPoint slides Contents Preface to the Second Edition Acknowledgments 1 Preliminaries 1.1 Fault Classification 1.2 Types of Redundancy 1.3 Basic Measures of Fault Tolerance 1.3.1 Traditional Measures 1.3.2 Network Measures 1.4 Outline of This Book 1.5 Further Reading References 2 Hardware Fault Tolerance 2.1 The Rate of Hardware Failure 2.2 Failure Rate, Reliability, and Mean Time to Failure 2.3 Hardware Failure Mechanisms 2.3.1 Electromigration 2.3.2 Stress Migration 2.3.3 Negative Bias Temperature Instability 2.3.4 Hot Carrier Injection 2.3.5 Time-Dependent Dielectric Breakdown 2.3.6 Putting It All Together 2.4 Common-Mode Failures 2.5 Canonical and Resilient Structures 2.5.1 Series and Parallel Systems 2.5.2 Nonseries/Parallel Systems 2.5.3 M-of-N Systems 2.5.4 Voters 2.5.5 Variations on N-Modular Redundancy Unit-level modular redundancy Dynamic redundancy Hybrid redundancy Sift-out modular redundancy 2.5.6 Duplex Systems Acceptance tests Hardware testing Forward recovery Pair-and-spare system Triplex-duplex system 2.6 Other Reliability Evaluation Techniques 2.6.1 Poisson Processes 2.6.2 Markov Models 2.7 Fault-Tolerance Processor-Level Techniques 2.7.1 Watchdog Processor 2.7.2 Simultaneous Multithreading for Fault Tolerance 2.8 Timing Fault Tolerance 2.9 Tolerance of Byzantine Failures 2.9.1 Byzantine Agreement With Message Authentication 2.10 Further Reading 2.11 Exercises References 3 Information Redundancy 3.1 Coding 3.1.1 Parity Codes 3.1.2 Checksum 3.1.3 M-of-N Codes 3.1.4 Berger Code 3.1.5 Cyclic Codes 3.1.6 Arithmetic Codes 3.1.7 Local Hard and Soft Decisions 3.2 Resilient Disk Systems 3.2.1 RAID Level 1 3.2.2 RAID Level 2 3.2.3 RAID Level 3 3.2.4 RAID Level 4 3.2.5 RAID Level 5 3.2.6 Hierarchical RAID 3.2.7 Modeling Correlated Failures 3.2.8 RAID With Solid-State Disks 3.3 Data Replication 3.3.1 Voting: Nonhierarchical Organization 3.3.2 Voting: Hierarchical Organization 3.3.3 Primary-Backup Approach 3.4 Algorithm-Based Fault Tolerance 3.5 Further Reading 3.6 Exercises References 4 Fault-Tolerant Networks 4.1 Measures of Resilience 4.1.1 Graph Theoretical Measures 4.1.2 Computer Networks Measures 4.2 Common Network Topologies and Their Resilience 4.2.1 Multistage and Extra-Stage Networks Analysis of the butterfly network Analysis of the extra-stage network 4.2.2 Crossbar Networks 4.2.3 Rectangular Mesh and Interstitial Mesh 4.2.4 Hypercube Network 4.2.5 Cube-Connected Cycles Networks 4.2.6 Loop Networks 4.2.7 Tree Networks 4.2.8 Ad Hoc Point-to-Point Networks 4.3 Fault-Tolerant Routing 4.3.1 Hypercube Fault-Tolerant Routing 4.3.2 Origin-Based Routing in the Mesh 4.4 Networks on a Chip 4.4.1 Router Fault Tolerance 4.4.2 Links 4.4.3 Routing in the Presence of Failure 4.5 Wireless Sensor Networks 4.5.1 Basics 4.5.2 Sensor Network Failures 4.5.3 Sensor Network Fault Tolerance Regular structures Irregular structures Sporadically connected networks 4.6 Further Reading 4.7 Exercises References 5 Software Fault Tolerance 5.1 Acceptance Tests 5.2 Single-Version Fault Tolerance 5.2.1 Wrappers 5.2.2 Software Rejuvenation Rejuvenation level Timing of rejuvenation 5.2.3 Data Diversity 5.2.4 Software-Implemented Hardware Fault Tolerance (SIHFT) Recomputing with shifted operands (RESO) 5.3 N-Version Programming 5.3.1 Consistent Comparison Problem 5.3.2 Version Independence 5.3.3 Other Issues in N-Version Programming 5.4 Recovery Block Approach 5.4.1 Basic Principles 5.4.2 Success Probability Calculation 5.4.3 Distributed Recovery Blocks 5.5 Preconditions, Postconditions, and Assertions 5.6 Exception Handling 5.6.1 Requirements From Exception Handlers 5.6.2 Basics of Exceptions and Exception Handling Propagation of exceptions Exception-terminate and exception-resume 5.6.3 Language Support 5.7 Software Reliability Models 5.7.1 Jelinski-Moranda Model 5.7.2 Littlewood-Verrall Model 5.7.3 Musa-Okumoto Model 5.7.4 Ostrand-Weyuker-Bell (OWB) Fault Model 5.7.5 Model Selection and Parameter Estimation 5.8 Fault-Tolerant Remote Procedure Calls 5.8.1 Primary-Backup Approach 5.8.2 The Circus Approach 5.9 Further Reading 5.10 Exercises References 6 Checkpointing 6.1 What Is Checkpointing? 6.1.1 Why Is Checkpointing Nontrivial? 6.2 Checkpoint Level 6.3 Optimal Checkpointing: an Analytical Model 6.3.1 Time Between Checkpoints-a First-Order Approximation 6.3.2 Optimal Checkpoint Placement 6.3.3 Time Between Checkpoints: a More Accurate Model 6.3.4 Reducing Overhead 6.3.5 Reducing Latency 6.4 Cache-Aided Rollback Error Recovery (CARER) 6.5 Checkpointing in Distributed Systems 6.5.1 The Domino Effect and Livelock 6.5.2 A Coordinated Checkpointing Algorithm 6.5.3 Time-Based Synchronization 6.5.4 Diskless Checkpointing 6.5.5 Message Logging Pessimistic message logging Optimistic message logging Staggered checkpointing 6.6 Checkpointing in Shared-Memory Systems 6.6.1 Bus-Based Coherence Protocol 6.6.2 Directory-Based Protocol 6.7 Checkpointing in Real-Time Systems 6.8 Checkpointing While Using Cloud Computing Utilities 6.9 Emerging Challenges: Petascale and Exascale Computing 6.10 Other Uses of Checkpointing 6.11 Further Reading 6.12 Exercises References 7 Cyber-Physical Systems 7.1 Structure of a Cyber-Physical System 7.2 The Controlled Plant State Space 7.3 Sensors 7.3.1 Calibration 7.3.2 Detecting Faulty Sensors 7.3.3 Confidence Measures for Intervals 7.4 The Cyber Platform 7.4.1 Isolation 7.4.2 Load Shedding 7.4.3 Overrun Absorption 7.5 Actuators 7.6 Further Reading 7.7 Exercises References 8 Case Studies 8.1 Aerospace Systems 8.1.1 Protecting Against Radiation 8.1.2 Flight Control System: Boeing 777 8.2 NonStop Systems 8.2.1 Architecture 8.2.2 Maintenance and Repair Aids 8.2.3 Software 8.2.4 Modifications to the NonStop Architecture 8.3 Stratus Systems 8.4 Cassini Command and Data Subsystem 8.5 IBM POWER8 8.6 IBM G5 8.7 IBM Sysplex 8.8 Intel Servers 8.8.1 Itanium 8.8.2 Xeon 8.9 Oracle SPARC M8 Server 8.10 Cloud Computing 8.10.1 Checkpointing in Response to Spot Pricing 8.10.2 Proactive Virtual Machine Migration 8.10.3 Fault Tolerance as a Service 8.11 Further Reading References 9 Simulation Techniques 9.1 Writing a Simulation Program 9.2 Parameter Estimation 9.2.1 Point Versus Interval Estimation 9.2.2 Method of Moments 9.2.3 Method of Maximum Likelihood 9.2.4 The Bayesian Approach to Parameter Estimation 9.2.5 Confidence Intervals 9.3 Variance Reduction Methods 9.3.1 Antithetic Variables 9.3.2 Using Control Variables 9.3.3 Stratified Sampling 9.3.4 Importance Sampling Simulating continuous-time Markov chains: mean time between system failures Simulating continuous-time Markov chains: reliability 9.4 Splitting 9.5 Random Number Generation 9.5.1 Uniformly Distributed Random Number Generators 9.5.2 Testing Uniform Random Number Generators 9.5.3 Generating Other Distributions 9.6 Fault Injection 9.6.1 Types of Fault Injection Techniques 9.6.2 Fault Injection Application and Tools 9.7 Further Reading 9.8 Exercises References 10 Defect Tolerance in VLSI Circuits 10.1 Manufacturing Defects and Circuit Faults 10.2 Probability of Failure and Critical Area 10.3 Basic Yield Models 10.3.1 The Poisson and Compound Poisson Yield Models 10.3.2 Variations on the Simple Yield Models 10.4 Yield Enhancement Through Redundancy 10.4.1 Yield Projection for Chips With Redundancy Chips with one type of modules More complex designs 10.4.2 Memory Arrays With Redundancy Advanced redundancy techniques 10.4.3 Logic Integrated Circuits With Redundancy 10.4.4 Modifying the Floorplan 10.5 Further Reading 10.6 Exercises References 11 Fault Detection in Cryptographic Systems 11.1 Overview of Ciphers 11.1.1 Symmetric Key Ciphers 11.1.2 Public Key Ciphers 11.2 Security Attacks Through Fault Injection 11.2.1 Fault Attacks on Symmetric Key Ciphers 11.2.2 Fault Attacks on Public (Asymmetric) Key Ciphers 11.3 Countermeasures 11.3.1 Spatial and Temporal Duplication 11.3.2 Error-Detecting Codes 11.3.3 Are These Countermeasure Sufficient? 11.3.4 Final Comment 11.4 Further Reading 11.5 Exercises References Index Fault-tolerant Systems, Second Edition, Is The First Book On Fault Tolerance Design Utilizing A Systems Approach To Both Hardware And Software. No Other Text Takes This Approach Or Offers The Comprehensive And Up-to-date Treatment That Koren And Krishna Provide. The Book Comprehensively Covers The Design Of Fault-tolerant Hardware And Software, Use Of Fault-tolerance Techniques To Improve Manufacturing Yields, And Design And Analysis Of Networks. Incorporating Case Studies That Highlight Six Different Computer Systems With Fault-tolerance Techniques Implemented In Their Design, The Book Includes Critical Material On Methods To Protect Against Threats To Encryption Subsystems Used For Security Purposes. The Text's Updated Content Will Help Students And Practitioners In Electrical And Computer Engineering And Computer Science Learn How To Design Reliable Computing Systems, And How To Analyze Fault-tolerant Computing Systems. Delivers The First Book On Fault Tolerance Design With A Systems Approach Offers Comprehensive Coverage Of Both Hardware And Software Fault Tolerance, As Well As Information And Time Redundancy Features Fully Updated Content Plus New Chapters On Failure Mechanisms And Fault-tolerance In Cyber-physical Systems Provides A Complete Ancillary Package, Including An On-line Solutions Manual For Instructors And Powerpoint Slides