| Title:
|
Structured redundancy for fault tolerance in state-space models and Petri nets (English) |
| Author:
|
Hadjicostis, Christoforos N. |
| Author:
|
Verghese, George C. |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
35 |
| Issue:
|
1 |
| Year:
|
1999 |
| Pages:
|
[39]-55 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
Petri nets |
| Keyword:
|
discrete event system |
| Keyword:
|
structured redundancy |
| MSC:
|
68Q85 |
| MSC:
|
93C65 |
| MSC:
|
93C83 |
| idZBL:
|
Zbl 1274.93190 |
| idMR:
|
MR1705529 |
| . |
| Date available:
|
2009-09-24T19:23:08Z |
| Last updated:
|
2015-03-27 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/135266 |
| . |
| Reference:
|
[1] Abraham J. A.: Fault tolerance techniques for highly parallel signal processing architectures.Proceedings of SPIE 614 (1986), 49–65 |
| Reference:
|
[2] Baccelli F., Cohen G., Olsder G. J., Quadrat J. P.: Synchronization and Linearity.Wiley, New York 1992 Zbl 0824.93003, MR 1204266 |
| Reference:
|
[3] Beckmann P. E.: Fault–Tolerant Computation Using Algebraic Homomorphisms.Ph.D. Thesis. EECS Department, Massachusetts Institute of Technology, Cambridge, MA 1992 MR 2716392 |
| Reference:
|
[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 |
| Reference:
|
[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 Zbl 0800.94083, 10.1109/78.224241 |
| Reference:
|
[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 0839186 |
| Reference:
|
[7] Cassandras C. G.: Discrete Event Systems.Aksen Associates, Boston 1993 Zbl 1225.93077, MR 2173259 |
| Reference:
|
[8] Cassandras C. G., Lafortune S., Olsder G. J.: Trends in Control: A European Perspective.Springer–Verlag, London 1995 MR 1448442 |
| Reference:
|
[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 |
| Reference:
|
[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 10.1109/12.237720 |
| Reference:
|
[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 0796.93001 |
| Reference:
|
[12] Gaubert S., Giua A.: Deterministic weak–and–marked Petri net languages are regular.IEEE Trans. Automat. Control AC-41 (1996), 12, 1802–1803 Zbl 0867.93009, MR 1421414, 10.1109/9.545718 |
| Reference:
|
[13] Ginzburg A.: Algebraic Theory of Automata: Academic Press, New York 196. MR 0242679 |
| Reference:
|
[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 MR 1328088, 10.1109/9.384227 |
| Reference:
|
[15] Hadjicostis C. N.: Fault–Tolerant Computation in Semigroups and Semirings.M. Engr. Thesis. EECS Department, Massachusetts Institute of Technology, Cambridge, MA 1995 |
| Reference:
|
[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 |
| Reference:
|
[17] Hadjicostis C. N., Verghese G. C.: Fault–tolerant computation in groups and semigroups, submitte. |
| Reference:
|
[18] Huang K.-H., Abraham J. A.: Algorithm–based fault tolerance for matrix operations.IEEE Trans. Comput. 33 (1984), 518–528 Zbl 0557.68027, 10.1109/TC.1984.1676475 |
| Reference:
|
[19] Ikeda M., Šiljak D. D.: An inclusion principle for dynamic systems.IEEE Trans. Automat. Control AC-29 (1984), 3, 244–249 Zbl 0553.93004, MR 0739610, 10.1109/TAC.1984.1103486 |
| Reference:
|
[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 |
| Reference:
|
[21] Jou J.-Y., Abraham J. A.: Fault–tolerant FFT networks.IEEE Trans. Comput. 37 (1988), 548–561 10.1109/12.4606 |
| Reference:
|
[22] Kailath T.: Linear Systems.Prentice–Hall, Englewood Cliffs, NJ 1980 Zbl 0870.93013, MR 0569473 |
| Reference:
|
[23] Luenberger D. G.: Introduction to Dynamic Systems: Theory, Models, & Applications.Wiley, New York 1979 Zbl 0458.93001 |
| Reference:
|
[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 |
| Reference:
|
[25] Murata T.: Petri nets: properties, analysis and applications.Proc. IEEE 77 (1989), 541–580 |
| Reference:
|
[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 10.1109/12.54836 |
| Reference:
|
[27] Norton J. P.: Structural zeros in the modal matrix and its inverse.IEEE Trans. Automat. Control AC-25 (1980), 980–981 Zbl 0459.93028, MR 0595238, 10.1109/TAC.1980.1102468 |
| Reference:
|
[28] Oppenheim A. V., Schafer R. W.: Discrete–Time Signal Processing.Prentice Hall, Englewood Cliffs, NJ 1989 Zbl 0676.42001 |
| Reference:
|
[29] Rao T. R. N.: Error Coding for Arithmetic Processors.Academic Press, New York 1974 Zbl 0301.94006, MR 0398649 |
| Reference:
|
[30] Reutenauer C.: The Mathematics of Petri Nets.Prentice Hall, New York 1990 Zbl 0694.68007, MR 1074575 |
| Reference:
|
[31] Roberts R. A., Mullis C. T.: Digital Signal Processing.Addison–Wesley, Reading, MA 1987 Zbl 0689.94001 |
| Reference:
|
[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 |
| Reference:
|
[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 0542534 |
| Reference:
|
[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 |
| Reference:
|
[35] Neumann J. von: Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components.Princeton University Press, Princeton, NJ 1956 MR 0077479 |
| Reference:
|
[36] Wicker S. B.: Error Control Systems.Prentice Hall, Englewood Cliffs, NJ 1995 Zbl 0847.94001 |
| Reference:
|
[37] Yamalidou K., Moody J., Lemmon M., Antsaklis P.: Feedback control of Petri net based on place invariants.Automatica 32 (1996), 1, 15–28 MR 1365601, 10.1016/0005-1098(95)00103-4 |
| . |
