Coding approaches to fault tolerance in dynamic systems
Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1999.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/9335 |
| _version_ | 1811095086641971200 |
|---|---|
| author | Hadjicostis, Christoforos N. (Christoforos Nikos) |
| author2 | George C. Verghese. |
| author_facet | George C. Verghese. Hadjicostis, Christoforos N. (Christoforos Nikos) |
| author_sort | Hadjicostis, Christoforos N. (Christoforos Nikos) |
| collection | MIT |
| description | Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1999. |
| first_indexed | 2024-09-23T16:10:25Z |
| format | Thesis |
| id | mit-1721.1/9335 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T16:10:25Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/93352019-04-12T17:07:29Z Coding approaches to fault tolerance in dynamic systems Hadjicostis, Christoforos N. (Christoforos Nikos) George C. Verghese. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1999. Includes bibliographical references (p. 189-196). A fault-tolerant system tolerates internal failures while preserving desirable overall behavior. Fault tolerance is necessary in life-critical or inaccessible applications, and also enables the design of reliable systems out of unreliable, less expensive components. This thesis discusses fault tolerance in dynamic systems, such as finite-state controllers or computer simulations, whose internal state influences their future behavior. Modular redundancy (system replication) and other traditional techniques for fault tolerance are expensive, and rely heavily -- particularly in the case of dynamic systems operating over extended time horizons -- on the assumption that the error-correcting mechanism (e.g., voting) is fault-free. The thesis develops a systematic methodology for adding structured redundancy to a dynamic system and introducing associated fault tolerance. Our approach exposes a wide range of possibilities between no redundancy and full replication. Assuming that the error-correcting mechanism is fault-free, we parameterize the different possibilities in various settings, including algebraic machines, linear dynamic systems and Petri nets. By adopting specific error models and, in some cases, by making explicit connections with hardware implementation, we demonstrate how the redundant systems can be designed to allow detection/correction of a fixed number of failures. We do not explicitly address optimization criteria that could be used in choosing among different redundant implementations, but our examples illustrate how such criteria can be investigated in future work. The last part of the thesis relaxes the traditional assumption that error-correction be fa.ult-free. We use unreliable system replicas and unreliable voters to construct redundant dynamic systems that evolve in time with low probability of failure. Our approach generalizes modular redundancy by using distributed voting schemes. Combining these techniques with low-complexity error-correcting coding, we are able to efficiently protect identical unreliable linear finite-state machines that operate in parallel on distinct input sequences. The approach requires only a constant amount of redundant hardware per machine to achieve a probability of failure that remains below any pre-specified bound over any given finite time interval. by Christoforos N. Hadjicostis. Ph.D. 2005-08-22T20:24:38Z 2005-08-22T20:24:38Z 1999 1999 Thesis http://hdl.handle.net/1721.1/9335 44266095 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 196 p. 15074456 bytes 15074215 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Hadjicostis, Christoforos N. (Christoforos Nikos) Coding approaches to fault tolerance in dynamic systems |
| title | Coding approaches to fault tolerance in dynamic systems |
| title_full | Coding approaches to fault tolerance in dynamic systems |
| title_fullStr | Coding approaches to fault tolerance in dynamic systems |
| title_full_unstemmed | Coding approaches to fault tolerance in dynamic systems |
| title_short | Coding approaches to fault tolerance in dynamic systems |
| title_sort | coding approaches to fault tolerance in dynamic systems |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/9335 |
| work_keys_str_mv | AT hadjicostischristoforosnchristoforosnikos codingapproachestofaulttoleranceindynamicsystems |