Geodesic
Structured redundancy for fault tolerance in state-space models and Petri nets
Kybernetika, Tome 35 (1999) no. 1, pp. 39-55 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

The design and implementation of systems in state form has traditionally focused on 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.
The design and implementation of systems in state form has traditionally focused on 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.
Classification : 68Q85, 93C65, 93C83
Keywords: Petri nets; discrete event system; structured redundancy 
@article{KYB_1999_35_1_a4,
     author = {Hadjicostis, Christoforos N. and Verghese, George C.},
     title = {Structured redundancy for fault tolerance in state-space models and {Petri} nets},
     journal = {Kybernetika},
     pages = {39--55},
     year = {1999},
     volume = {35},
     number = {1},
     mrnumber = {1705529},
     zbl = {1274.93190},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_1999_35_1_a4/}
}
TY  - JOUR
AU  - Hadjicostis, Christoforos N.
AU  - Verghese, George C.
TI  - Structured redundancy for fault tolerance in state-space models and Petri nets
JO  - Kybernetika
PY  - 1999
SP  - 39
EP  - 55
VL  - 35
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/KYB_1999_35_1_a4/
LA  - en
ID  - KYB_1999_35_1_a4
ER  - 
%0 Journal Article
%A Hadjicostis, Christoforos N.
%A Verghese, George C.
%T Structured redundancy for fault tolerance in state-space models and Petri nets
%J Kybernetika
%D 1999
%P 39-55
%V 35
%N 1
%U http://geodesic.mathdoc.fr/item/KYB_1999_35_1_a4/
%G en
%F KYB_1999_35_1_a4
Hadjicostis, Christoforos N.; Verghese, George C. Structured redundancy for fault tolerance in state-space models and Petri nets. Kybernetika, Tome 35 (1999) no. 1, pp. 39-55. http://geodesic.mathdoc.fr/item/KYB_1999_35_1_a4/

[1] Abraham J. A.: Fault tolerance techniques for highly parallel signal processing architectures. Proceedings of SPIE 614 (1986), 49–65

[2] Baccelli F., Cohen G., Olsder G. J., Quadrat J. P.: Synchronization and Linearity. Wiley, New York 1992 | MR | Zbl

[3] Beckmann P. E.: Fault–Tolerant Computation Using Algebraic Homomorphisms. Ph.D. Thesis. EECS Department, Massachusetts Institute of Technology, Cambridge, MA 1992 | MR

[4] Beckmann P. E., Musicus B. R.: A group–theoretic framework for fault–tolerant computation. In: IEEE Internat. Conf. on Acoustics, Speech, and Signal Processing, 1992, pp. 557–560

[5] Beckmann P. E., Musicus B. R.: Fast fault–tolerant digital convolution using a polynomial residue number system. IEEE Trans. Signal Process. 41 (1993), 2300–2313 | DOI | Zbl

[6] Brewer J. W., Bunce J. W., Vleck F. S. Van: Linear Systems Over Commutative Rings. (Lecture Notes in Pure and Applied Mathematics 104.) Marcel Dekker, Inc., New York 1986 | MR

[7] Cassandras C. G.: Discrete Event Systems. Aksen Associates, Boston 1993 | MR | Zbl

[8] Cassandras C. G., Lafortune S., Olsder G. J.: Trends in Control: A European Perspective. Springer–Verlag, London 1995 | MR

[9] Chatterjee A.: Concurrent error detection in linear analog and switched–capacitor state variable systems using continuous checksums. In: Internat. Test Conference 1991, pp. 582–591

[10] Chatterjee A., d’Abreu M.: The design of fault–tolerant linear digital state variable systems: theory and techniques. IEEE Trans. Comput. 42 (1993), 794–808 | DOI

[11] Fedorov V. Y., Chukanov V. O.: Analysis of the fault tolerance of complex systems by extensions of Petri nets. Automat. Remote Control 53 (1992), 2, 271–280 | Zbl

[12] Gaubert S., Giua A.: Deterministic weak–and–marked Petri net languages are regular. IEEE Trans. Automat. Control AC-41 (1996), 12, 1802–1803 | DOI | MR | Zbl

[13] Ginzburg A.: Algebraic Theory of Automata: Academic Press, New York 196. | MR

[14] Giua A., DiCesare F.: Decidability and closure properties of weak Petri net languages in supervisory control. IEEE Trans. Automat. Control AC-40 (1995), 5, 906–910 | DOI | MR

[15] Hadjicostis C. N.: Fault–Tolerant Computation in Semigroups and Semirings. M. Engr. Thesis. EECS Department, Massachusetts Institute of Technology, Cambridge, MA 1995

[16] Hadjicostis C. N., Verghese G. C.: Fault–tolerant computation in semigroups and semirings. In: Internat. Conf. on Digital Signal Processing, Vol. 2, Cyprus, 1995, pp. 779–784

[17] Hadjicostis C. N., Verghese G. C.: Fault–tolerant computation in groups and semigroups, submitte.

[18] Huang K.-H., Abraham J. A.: Algorithm–based fault tolerance for matrix operations. IEEE Trans. Comput. 33 (1984), 518–528 | DOI | Zbl

[19] Ikeda M., Šiljak D. D.: An inclusion principle for dynamic systems. IEEE Trans. Automat. Control AC-29 (1984), 3, 244–249 | DOI | MR | Zbl

[20] Jou J.-Y., Abraham J. A.: Fault–tolerant matrix arithmetic and signal processing on highly concurrent parallel structures. Proc. IEEE 74 (1986), 732–741

[21] Jou J.-Y., Abraham J. A.: Fault–tolerant FFT networks. IEEE Trans. Comput. 37 (1988), 548–561 | DOI

[22] Kailath T.: Linear Systems. Prentice–Hall, Englewood Cliffs, NJ 1980 | MR | Zbl

[23] Luenberger D. G.: Introduction to Dynamic Systems: Theory, Models, & Applications. Wiley, New York 1979 | Zbl

[24] Moody J. O., Antsaklis P. J.: Supervisory control using computationally efficient linear techniques: a tutorial introduction. In: 5th IEEE Mediterranean Conf. on Control and Systems, Cyprus 1997

[25] Murata T.: Petri nets: properties, analysis and applications. Proc. IEEE 77 (1989), 541–580

[26] Nair V. S. S., Abraham J. A.: Real–number codes for fault–tolerant matrix operations on processor arrays. IEEE Trans. Comput. 39 (1990), 426–435 | DOI

[27] Norton J. P.: Structural zeros in the modal matrix and its inverse. IEEE Trans. Automat. Control AC-25 (1980), 980–981 | DOI | MR | Zbl

[28] Oppenheim A. V., Schafer R. W.: Discrete–Time Signal Processing. Prentice Hall, Englewood Cliffs, NJ 1989 | Zbl

[29] Rao T. R. N.: Error Coding for Arithmetic Processors. Academic Press, New York 1974 | MR | Zbl

[30] Reutenauer C.: The Mathematics of Petri Nets. Prentice Hall, New York 1990 | MR | Zbl

[31] Roberts R. A., Mullis C. T.: Digital Signal Processing. Addison–Wesley, Reading, MA 1987 | Zbl

[32] Sahraoui A., Atabakhche H., Courvoisier M., Valette R.: Joining Petri nets and knowledge–based systems for monitoring purposes. In: IEEE Internat. Conf. Robotics Automation, Raleigh, NC 1987, pp. 1160–1165

[33] Sifakis J.: Realization of fault–tolerant systems by coding Petri nets. J. Design Automation and Fault–Tolerant Computing 3 (1979), 2, 93–107 | MR

[34] Silva M., Velilla S.: Error detection and correction on Petri net models of discrete events control systems. In: Proceedings of the ISCAS 1985, pp. 921–924

[35] Neumann J. von: Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components. Princeton University Press, Princeton, NJ 1956 | MR

[36] Wicker S. B.: Error Control Systems. Prentice Hall, Englewood Cliffs, NJ 1995 | Zbl

[37] Yamalidou K., Moody J., Lemmon M., Antsaklis P.: Feedback control of Petri net based on place invariants. Automatica 32 (1996), 1, 15–28 | DOI | MR