Fault-tolerant Digital Systems

Course Synopsis

Our daily lives are becoming increasingly dependent on computer systems, from small, embedded computers to large-scale data centers. Any disruption in or malfunctioning of these systems can lead to devastating consequences for society as a whole. The reliability and availability of these systems is thus essential for our quality of life and for the smooth functioning of society. Therefore, it is important to build computer systems that operate correctly in the face of errors and failures.

This course focuses on the design of fault-tolerant and reliable computer systems. In particular, we will attempt to understand the root causes of faults in computer systems and their impact. We will study both traditional and cutting-edge techniques to provide fault-tolerance and error resilience. Finally, we will explore the practical applications of the techniques in the context of real systems.

An important thread that runs through the course is the evaluation of fault-tolerant systems. To this end, we will study techniques ranging from analytical modeling to empirical validation. The assignments will give you hands-on exposure to cutting edge tools and techniques for dependability evaluation, and will prepare you for the final project. You are encouraged (but not required) to work on a project related to your research interests. The final project constitutes a significant part of the grade.

Topics Covered

This is a tentative list of topics to be covered in the course. Note that these topics are subject to change.

Some slides are based on Prof. Saurabh Bagchi’s slides for “Fault Tolerant Computer System Design” (ECE 695B) at Purdue University. Used with permission.

Topic	Lectures	Sub-topics
Introduction and Overview	3	Introduction to the course, Basic concepts, Sources of faults in computer systems
Modeling and Evaluation -1	2	Probability review and discrete probability, Continuous probability and TMR
Hardware fault-tolerance	2	Architectural techniques
Modeling and Evaluation -2	2	Markov processes, Stochastic Activity Networks
Software fault-tolerance	3	N-version programming, recovery blocks, robust data structures and process pairs
Modeling and Evaluation – 3	2	Fault-injection: techniques and tools, Formal methods
Parallel and Distributed systems	4	Check-pointing and recovery, Byzantine fault-tolerance and paxos
Case Studies	2	Stratus and AT&T systems

Textbooks

There is NO required textbook. However, the following books are recommended:

1. D. P. Siewiorek and R. S. Swarz, Reliable Computer Systems – Design and Evaluation, 3rd edition, 1999, A.K. Peters, Limited.
2. K. Trivedi, Probability and Statistics with Reliability, Queuing and Computer Science Applications, 2nd edition, 2001, John Wiley & Sons.