Information Trust Institute: University of Illinois at Urbana-Champaign

Short Course: Validating High-Availability Systems

COURSE DESCRIPTION:

This course provides a comprehensive introduction to methods for validating high-availability systems and networks that can be used from the early design stage to the testing of a prototype. After introducing basic concepts related to reliability, availability, and performability, the course presents combinatorial modeling methods, which are most useful in the early design stage. Markov process theory, and numerical issues in solving Markov models, are then presented as a method to solve system models during the early/middle design phase, and discrete-event simulation is presented as a method for solving detailed models built in the final design phase. In both cases, stochastic activity networks are introduced as a high-level, easy-to-use method of describing system models. Finally, the use of fault injection to validate a prototype implementation is discussed.

PREREQUISITE: An undergraduate course in probability and statistics.

HIGH-LEVEL COURSE OUTLINE AND TIMETABLE:

1. Introduction to the Validation of High-Availability Systems
   1. Review of Design Techniques for High-Availability and Dependable Systems
   2. Validation of High-Availability Systems is Critical
   3. Fault Types: Stand-Alone and Networked Systems
   4. Definitions and Measures of Success: Dependability and Performability
   5. Approaches to Validation
   6. Synergistic Relationship Between Validation Methods
   7. Validation Methods not Covered in this Course
   8. When Validation Should Take Place
   9. Course Overview
2. First-Cut, Rapid Validation by Combinatorial Methods
   1. Reliability Assessment: The Need for Probability
   2. Combinatoric Methods: Independent Failure Assumption
   3. Reliability Formalisms: Fault Trees, Reliability Block Diagrams, Reliability Graphs
   4. Reliability Block Diagram Examples
3. Validation Using Classical State-Based Methods
   1. Availability: One Need for State-Based Methods
   2. Random Processes
   3. Discrete Time Markov Chains
   4. Continuous Time Markov Chains
   5. Markov Chain Solution Techniques: Transient and Steady State
   6. CTMC Model Examples
4. Specifying High-Availability System Designs Using Stochastic Activity Networks
   1. The Need for High-Level Specification Methods
   2. Stochastic Petri Nets: Basic Definitions and Examples
   3. Generating Markov Models from Stochastic Petri Nets: Example
   4. Stochastic Activity Networks (SANs)
   5. Execution of SANs
   6. Specification of Reliability, Availability, and Performability Variables
   7. Simple Example: Multiprocessor Failure/Repair Model
   8. Building Larger Models from SAN Components: Composed Models
5. Simulation-Based Validation Techniques
   1. Simulation as Model Experimentation - Basic Algorithms and Assumptions
   2. Random Number and Random Variable Generators
   3. Types of Simulation: Transient and Steady-State
   4. Confidence Intervals about Estimators - Statistical Issues and Pitfalls
   5. Parallel Simulation: Study-Level, Experiment-Level, and Trajectory-Level Parallelism
   6. Variance Reduction Techniques: Importance Sampling
6. Fault Injection Methods and Mechanisms
   1. Fault Injection in the Development and Validation Process
   2. Fault Injection on Simulated Systems
   3. Hardware-Implemented Fault Injection
   4. Software-Implemented Fault Injection - Stand-Alone Systems
   5. Software-Implemented Fault Injection - Networks / Distributed Systems
   6. Comparison of Three Hardware Fault Injection Techniques on the MARS Architecture
7. Removal, Benchmarking, and Dependability Assessment Using Fault Injection
   1. Fault Removal
   2. Dependability Benchmarks
   3. Dependability Assessment
8. Summary and Concluding Remarks
   1. Review of Previous Lectures
   2. The "Art" of Dependability Validation
   3. Validating Validation Models and Measurements
   4. Next Steps

Instructor Biography

William H. Sanders is a Donald Biggar Willett Professor of Engineering and the Director of the Information Trust Institute at the University of Illinois. He is a professor in the Department of Electrical and Computer Engineering and the Coordinated Science Laboratory. He is a Fellow of the IEEE and the ACM. He serves as the Vice-Chair of IFIP Working Group 10.4 on Dependable Computing . In addition, he serves on the editorial board of Performance Evaluation , and is the Area Editor for Simulation and Modeling of Computer Systems for the ACM Transactions on Modeling and Computer Simulation . He is a past Chair of the IEEE Technical Committee on Fault-Tolerant Computing. Dr. Sanders's research interests include performance/dependability evaluation, dependable computing, and reliable distributed systems. He has published more than 160 technical papers in these areas. He is a co-developer of three tools for assessing the performability of systems represented as stochastic activity networks: METASAN, UltraSAN, and Möbius. Möbius and UltraSAN have been distributed widely to industry and academia; more than 300 licenses for the tools have been issued to universities, companies, and NASA for evaluating the performance, dependability, security, and performability of a variety of systems. He is also a co-developer of the Loki distributed system fault injector and the AQuA/ITUA middlewares for providing dependability/security to distributed and networked applications.