Course
Description

Description:

This course describes a systematic and integrated approach towards the design and implementation of fault-tolerant computational and dynamic systems. Building on results from recent research work, the course blends together techniques from coding and complexity theory, digital design, and control,  automata and system theory.  The course studies fault-tolerant computational architectures under a unifying approach that exposes the similarities between coding for reliable communication and coding for reliable computation.  This approach is subsequently extended to handle fault tolerance in systems whose internal state influences their future behavior, such as finite state controllers or algorithmic computations evolving over several time steps.  The introduction of time and state dynamics presents new challenges for engineering design, but also offers new degrees of freedom and opens up exciting possibilities for future digital system implementation.  The course discusses some of these open research questions for a number of systems of special interest, such as finite state machines, digital signal processing filters, cellular automata and discrete event systems.  An introduction to the basic objectives and techniques in coding and in design for fault tolerance is provided.

Topics:
              - Fault models, errors, reliability, availability, fault tolerance
              - Failures in digital communication channels, coding approaches for communication systems, capacity considerations
              - Failures in gates or computational components:
                               (i) coding approaches for noisy circuits
                               (ii) ABFT techniques for computational systems
                               (iii) efficiency considerations and other parameters (capacity, probability of error, error coverage)
              - Failures in the error correcting mechanisms, coding approaches for dynamic systems
                                (i) dynamic error correction
                                (ii) decoding complexity and low density parity check codes
                                (iii) computational capacity, fault coverage, probability of error
            - Other uses of redundancy (monitoring and testing using redundant inputs, states and outputs)

Prerequisites:

Required:  ECE313 and ECE362 (or permission of instructor).
Desired:  ECE412, ECE415.
Familiarity with elementary algebra and linear system theory would be helpful, but not required;  a self-contained introduction to these topics will be provided.

Textbook:  Mainly class notes and research papers.

References:

•       D.P. Siewiorek and R.S. Swarz, Reliable Computer Systems: Design and Evaluation, A.K. Peters, 1998.
•       R.E. Blahut, Theory and Practice of Data Transmission Codes, Addison-Wesley, 1983.
•       D.K. Pradhan, ed., Fault Tolerant Computer System Design,  Prentice-Hall, 1996.
•       B.W. Johnson, Design and Analysis of Fault-Tolerant Digital Systems, Addison Wesley, 1989.
•       S.B. Wicker, Error Control Systems, Prentice Hall, 1995.
•       C.G. Cassandras, Discrete Event Systems, Aksen Associates, 1993.
•       F.T. Leighton, Introduction to Parallel Algorithms and Architectures:  Arrays, Trees, Hypercubes, Morgan Kaufmann Publishers, 1992.

Instructor information:  C. N. Hadjicostis / 265-8259 / 148 C&SRL / chadjic@control.csl.uiuc.edu

Course Time and Place: Tuesdays & Thursdays, 2:30-4:00pm, 57 Everitt Lab

Office Hours: Wednesdays, 1:30-3:00pm, 148 C&SRL

Course Outline:

I. Introductory Material (Hours: 7.5)

•       Motivation, definitions, basic principles and fundamental concepts
•       Fault models and error manifestation, hardware vs. software fault tolerance
•       Examples of successful fault-tolerant schemes in general purpose computers (hardware replication, voting schemes, RAID systems)
•       Reliability, availability, fault tolerance, security, cost issues

•       Reliable communication systems, coding theory
•       Classical extensions on circuits of ``noisy gates''
•       Application of coding techniques to special-purpose systems ($\alpha N$ codes, arithmetic codes, algorithm-based fault tolerance)
•       Case studies:  matrix multiplication, FFT, sorting
•       Extensions to computational systems with algebraic structure

•       Finite state machines, linear systems, linear finite state machines
•       Failures in the error correcting mechanisms
•       Low density parity check codes
•       Computational capacity

•       Reliable cellular automata
•       Fault-tolerant monitoring of large-scale discrete event systems
•       Software fault tolerance
•       Fault tolerance in cryptographic systems

Homework:

•       Homework 1
•       Homework 2
•       Homework 3

Projects:

•       Guoming Shou, April 18, 2000, Presentation
•       Manish Sharma, April 20, 2000, Presentation
•       Rajamohana Heghe