Fault Tolerant Systems by Israel Koren, C. Mani Krishna

Foreword     xi
Preface     xiii
Acknowledgements     xvii
About the Authors     xix
Preliminaries     1
Fault Classification     2
Types of Redundancy     3
Basic Measures of Fault Tolerance     4
Traditional Measures     5
Network Measures     6
Outline of This Book     7
Further Reading     9
References     10
Hardware Fault Tolerance     11
The Rate of Hardware Failures     11
Failure Rate, Reliability, and Mean Time to Failure     13
Canonical and Resilient Structures     15
Series and Parallel Systems     16
Non-Series/Parallel Systems     17
M-of-N Systems     20
Voters     23
Variations on N-Modular Redundancy     23
Duplex Systems     27
Other Reliability Evaluation Techniques     30
Poisson Processes     30
Markov Models     33
Fault-Tolerance Processor-Level Techniques     36
Watchdog Processor     37
Simultaneous Multithreading for Fault Tolerance     39
Byzantine Failures     41
Byzantine Agreement with Message Authentication     46
Further Reading     48
Exercises     48
References     53
Information Redundancy     55
Coding     56
Parity Codes     57
Checksum     64
M-of-N Codes     65
Berger Code     66
Cyclic Codes     67
Arithmetic Codes     74
Resilient Disk Systems     79
Raid Level 1     79
Raid Level 2     81
Raid Level 3     82
Raid Level 4     83
Raid Level 5     84
Modeling Correlated Failures     84
Data Replication     88
Voting: Non-Hierarchical Organization     89
Voting: Hierarchical Organization     95
Primary-Backup Approach     96
Algorithm-Based Fault Tolerance     99
Further Reading     101
Exercises     102
References     106
Fault-Tolerant Networks     109
Measures of Resilience     110
Graph-Theoretical Measures     110
Computer Networks Measures     111
Common Network Topologies and Their Resilience     112
Multistage and Extra-Stage Networks     112
Crossbar Networks     119
Rectangular Mesh and Interstitial Mesh     121
Hypercube Network     124
Cube-Connected Cycles Networks     128
Loop Networks     130
Ad hoc Point-to-Point Networks     132
Fault-Tolerant Routing     135
Hypercube Fault-Tolerant Routing     136
Origin-Based Routing in the Mesh     138
Further Reading     141
Exercises     142
References     145
Software Fault Tolerance     147
Acceptance Tests     148
Single-Version Fault Tolerance     149
Wrappers     149
Software Rejuvenation     152
Data Diversity     155
Software Implemented Hardware Fault Tolerance (SIHFT)     157
N-Version Programming     160
Consistent Comparison Problem     161
Version Independence     162
Recovery Block Approach     169
Basic Principles     169
Success Probability Calculation     169
Distributed Recovery Blocks     171
Preconditions, Postconditions, and Assertions     173
Exception-Handling     173
Requirements from Exception-Handlers     174
Basics of Exceptions and Exception-Handling     175
Language Support     177
Software Reliability Models     178
Jelinski-Moranda Model     178
Littlewood-Verrall Model     179
Musa-Okumoto Model     180
Model Selection and Parameter Estimation     182
Fault-Tolerant Remote Procedure Calls     182
Primary-Backup Approach     182
The Circus Approach     183
Further Reading     184
Exercises     186
References     188
Checkpointing     193
What is Checkpointing?     195
Why is Checkpointing Nontrivial?     197
Checkpoint Level     197
Optimal Checkpointing-An Analytical Model     198
Time Between Checkpoints-A First-Order Approximation     200
Optimal Checkpoint Placement     201
Time Between Checkpoints-A More Accurate Model     202
Reducing Overhead     204
Reducing Latency     205
Cache-Aided Rollback Error Recovery (CARER)     206
Checkpointing in Distributed Systems     207
The Domino Effect and Livelock     209
A Coordinated Checkpointing Algorithm     210
Time-Based Synchronization     211
Diskless Checkpointing     212
Message Logging     213
Checkpointing in Shared-Memory Systems     217
Bus-Based Coherence Protocol     218
Directory-Based Protocol     219
Checkpointing in Real-Time Systems     220
Other Uses of Checkpointing     223
Further Reading     223
Exercises     224
References     226
Case Studies     229
NonStop Systems     229
Architecture     229
Maintenance and Repair Aids     233
Software     233
Modifications to the NonStop Architecture     235
Stratus Systems     236
Cassini Command and Data Subsystem     238
IBM G5     241
IBM Sysplex     242
Itanium     244
Further Reading     246
References     247
Defect Tolerance in VLSI Circuits     249
Manufacturing Defects and Circuit Faults     249
Probability of Failure and Critical Area     251
Basic Yield Models     253
The Poisson and Compound Poisson Yield Models     254
Variations on the Simple Yield Models     256
Yield Enhancement Through Redundancy     258
Yield Projection for Chips with Redundancy     259
Memory Arrays with Redundancy     263
Logic Integrated Circuits with Redundancy     270
Modifying the Floorplan     272
Further Reading     276
Exercises     277
References     281
Fault Detection in Cryptographic Systems     285
Overview of Ciphers     286
Symmetric Key Ciphers     286
Public Key Ciphers     295
Security Attacks Through Fault Injection     296
Fault Attacks on Symmetric Key Ciphers     297
Fault Attacks on Public (Asymmetric) Key Ciphers     298
Countermeasures     299
Spatial and Temporal Duplication     300
Error-Detecting Codes     300
Are These Countermeasures Sufficient?     304
Final Comment     307
Further Reading     307
Exercises     307
References     308
Simulation Techniques      311
Writing a Simulation Program     311
Parameter Estimation     315
Point Versus Interval Estimation     315
Method of Moments     316
Method of Maximum Likelihood     318
The Bayesian Approach to Parameter Estimation     322
Confidence Intervals     324
Variance Reduction Methods     328
Antithetic Variables     328
Using Control Variables     330
Stratified Sampling     331
Importance Sampling     333
Random Number Generation     341
Uniformly Distributed Random Number Generators     342
Testing Uniform Random Number Generators     345
Generating Other Distributions     349
Fault Injection     355
Types of Fault Injection Techniques     356
Fault Injection Application and Tools     358
Further Reading     358
Exercises     359
References     363
Subject Index     365