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

Christoforos N. Hadjicostis; George C. Verghese

Kybernetika (1999)

  • Volume: 35, Issue: 1, page [39]-55
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Hadjicostis, Christoforos N., and Verghese, George C.. "Structured redundancy for fault tolerance in state-space models and Petri nets." Kybernetika 35.1 (1999): [39]-55. <http://eudml.org/doc/33408>.

@article{Hadjicostis1999,
abstract = {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.},
author = {Hadjicostis, Christoforos N., Verghese, George C.},
journal = {Kybernetika},
keywords = {Petri nets; discrete event system; structured redundancy; Petri nets; discrete event system; structured redundancy},
language = {eng},
number = {1},
pages = {[39]-55},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Structured redundancy for fault tolerance in state-space models and Petri nets},
url = {http://eudml.org/doc/33408},
volume = {35},
year = {1999},
}

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
PB - Institute of Information Theory and Automation AS CR
VL - 35
IS - 1
SP - [39]
EP - 55
AB - 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.
LA - eng
KW - Petri nets; discrete event system; structured redundancy; Petri nets; discrete event system; structured redundancy
UR - http://eudml.org/doc/33408
ER -

References

top
  1. Abraham J. A., Fault tolerance techniques for highly parallel signal processing architectures, Proceedings of SPIE 614 (1986), 49–65 (1986) 
  2. Baccelli F., Cohen G., Olsder G. J., Quadrat J. P., Synchronization and Linearity, Wiley, New York 1992 Zbl0824.93003MR1204266
  3. Beckmann P. E., Fault–Tolerant Computation Using Algebraic Homomorphisms, Ph.D. Thesis. EECS Department, Massachusetts Institute of Technology, Cambridge, MA 1992 MR2716392
  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 (1992) 
  5. Beckmann P. E., Musicus B. R., 10.1109/78.224241, IEEE Trans. Signal Process. 41 (1993), 2300–2313 (1993) Zbl0800.94083DOI10.1109/78.224241
  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 MR0839186
  7. Cassandras C. G., Discrete Event Systems, Aksen Associates, Boston 1993 Zbl1225.93077MR2173259
  8. Cassandras C. G., Lafortune S., Olsder G. J., Trends in Control: A European Perspective, Springer–Verlag, London 1995 MR1448442
  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 (1991) 
  10. Chatterjee A., d’Abreu M., 10.1109/12.237720, IEEE Trans. Comput. 42 (1993), 794–808 (1993) DOI10.1109/12.237720
  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 (1992) Zbl0796.93001
  12. Gaubert S., Giua A., 10.1109/9.545718, IEEE Trans. Automat. Control AC-41 (1996), 12, 1802–1803 (1996) Zbl0867.93009MR1421414DOI10.1109/9.545718
  13. Ginzburg A., Algebraic Theory of Automata: Academic Press, New York 196 MR0242679
  14. Giua A., DiCesare F., 10.1109/9.384227, IEEE Trans. Automat. Control AC-40 (1995), 5, 906–910 (1995) MR1328088DOI10.1109/9.384227
  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 (1995) 
  17. Hadjicostis C. N., Verghese G. C., Fault–tolerant computation in groups and semigroups, submitte 
  18. Huang K.-H., Abraham J. A., 10.1109/TC.1984.1676475, IEEE Trans. Comput. 33 (1984), 518–528 (1984) Zbl0557.68027DOI10.1109/TC.1984.1676475
  19. Ikeda M., Šiljak D. D., 10.1109/TAC.1984.1103486, IEEE Trans. Automat. Control AC-29 (1984), 3, 244–249 (1984) Zbl0553.93004MR0739610DOI10.1109/TAC.1984.1103486
  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 (1986) 
  21. Jou J.-Y., Abraham J. A., 10.1109/12.4606, IEEE Trans. Comput. 37 (1988), 548–561 (1988) DOI10.1109/12.4606
  22. Kailath T., Linear Systems, Prentice–Hall, Englewood Cliffs, NJ 1980 Zbl0870.93013MR0569473
  23. Luenberger D. G., Introduction to Dynamic Systems: Theory, Models, & Applications, Wiley, New York 1979 Zbl0458.93001
  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 (1989) 
  26. Nair V. S. S., Abraham J. A., 10.1109/12.54836, IEEE Trans. Comput. 39 (1990), 426–435 (1990) DOI10.1109/12.54836
  27. Norton J. P., 10.1109/TAC.1980.1102468, IEEE Trans. Automat. Control AC-25 (1980), 980–981 (1980) Zbl0459.93028MR0595238DOI10.1109/TAC.1980.1102468
  28. Oppenheim A. V., Schafer R. W., Discrete–Time Signal Processing, Prentice Hall, Englewood Cliffs, NJ 1989 Zbl0676.42001
  29. Rao T. R. N., Error Coding for Arithmetic Processors, Academic Press, New York 1974 Zbl0301.94006MR0398649
  30. Reutenauer C., The Mathematics of Petri Nets, Prentice Hall, New York 1990 Zbl0694.68007MR1074575
  31. Roberts R. A., Mullis C. T., Digital Signal Processing, Addison–Wesley, Reading, MA 1987 Zbl0689.94001
  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 (1987) 
  33. Sifakis J., Realization of fault–tolerant systems by coding Petri nets, J. Design Automation and Fault–Tolerant Computing 3 (1979), 2, 93–107 (1979) MR0542534
  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 (1985) 
  35. Neumann J. von, Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components, Princeton University Press, Princeton, NJ 1956 MR0077479
  36. Wicker S. B., Error Control Systems, Prentice Hall, Englewood Cliffs, NJ 1995 Zbl0847.94001
  37. Yamalidou K., Moody J., Lemmon M., Antsaklis P., 10.1016/0005-1098(95)00103-4, Automatica 32 (1996), 1, 15–28 (1996) MR1365601DOI10.1016/0005-1098(95)00103-4

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.