Kybernetika 35 no. 1, 39-55, 1999

Structured redundancy for fault tolerance in state-space models and Petri nets

Christoforos N. Hadjicostis and George C. Verghese


The design and implementation of systems in state form has traditionally focused on {\sl minimal} representations which require the least number of state variables. However, "structured redundancy'' - redundancy that has been intentionally introduced in some systematic way - can be extremely important when fault tolerance is desired. The redundancy can be used to detect and correct errors or to guarantee desirable performance despite hardware or computational failures. Modular redundancy, the traditional approach to fault tolerance, is prohibitively expensive because of the overhead in replicating the hardware. This paper discusses alternative methods for systematically introducing redundancy in state-space systems. Our approach consists of mapping the state space of the original system into a redundant space of higher dimension while preserving the properties of the original system in some encoded form within this larger space. We illustrate our approach by focusing primarily on linear time-invariant (LTI) systems in state form. We provide a complete characterization of the class of appropriate redundant systems and demonstrate through several examples ways in which our framework can be used for achieving fault tolerance. We also discuss appropriate error models and outline the extension of our approach to Petri nets.