Distributed monitoring of concurrent and asynchronous systems. (English) Zbl 1077.68059
Summary: In this paper we study the diagnosis of distributed asynchronous systems with concurrency. Diagnosis is performed by a peer-to-peer distributed architecture of supervisors. Our approach relies on Petri net unfoldings and event structures, as means to manipulate trajectories of systems with concurrency. This article is an extended version of the paper with same title, which appeared as a plenary address in CONCUR 2003 – concurrency theory, 14th international conference, Marseille, France, September 3–5, 2003. Proceedings. Lect. Notes Comput. Sci. 2761, 1–26 (2003).
MSC:
| 68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |
| 93B07 | Observability |
| 93C65 | Discrete event control/observation systems |
Keywords:
asynchronous; concurrent; distributed; unfoldings; event structures; fault diagnosis; fault managementCitations:
Zbl 1026.00029Software:
UMDESReferences:
| [1] | Aghasaryan, A., Dousson, C., Fabre, E., Pencolé, Y., and Osmani, A. 2002. Modeling fault propagation in telecommunications networks for diagnosis purposes. In XVIII World Telecommunications Congress. Paris, France, 22-27 September, Available: http://www.irisa.fr/sigma2/benveniste/pub/topic_distribdiag.html. |
| [2] | Aghasaryan, A., Jard, C., and Thomas, J. 2004. UML Specification of a generic model for fault diagnosis of telecommunication networks. In 2004 International Conference on Telecommunications, Fortalezza, Brasil, 2-7 August. |
| [3] | Baroni, P., Lamperti, G., Pogliano, P., and Zanella, M. 1999. Diagnosis of large active systems. Artificial Intelligence 110: 135-183. · Zbl 0996.68209 |
| [4] | Benveniste, A., Fabre, E., Jard, C., and Haar, S. 2003a. Diagnosis of asynchronous discrete event systems, a net unfolding approach. IEEE Trans. on Automatic Control, 48(5), May. Preliminary version available from http://www.irisa.fr/sigma2/benveniste/pub/IEEE_TAC_AsDiag_2003.html. · Zbl 1274.68221 |
| [5] | Benveniste, A., Haar, S., and Fabre, E. 2003b. Markov nets: probabilistic models for distributed and concurrent systems. IEEE Trans. on Automatic Control, November. Extended version available as IRISA Report 1538, May 2003; available electronically at ftp://ftp.irisa.fr/techreports/2003/PI-1538.ps.gz. · Zbl 1274.68221 |
| [6] | Boel, R. K., and van Schuppen, J. H. 2002. Decentralized failure diagnosis for discrete-event systems with costly communication between diagnosers. In Proc. of 6th Int. Workshop on Discrete Event Systems, WODES? 2002, pp. 175-181. |
| [7] | Cassandras, C., and Lafortune, S. 1999. Introduction to Discrete Event Systems. Kluwer Academic Publishers. · Zbl 0934.93001 |
| [8] | Debouk, R., Lafortune, S., and Teneketzis, D. 2000. Coordinated decentralized protocols for failure diagnosis of discrete event systems. Discrete Event Dynamic Systems: Theory and Application. 10(1/2), 33-86. · Zbl 0959.93039 |
| [9] | Degano, P., De Nicola, R., and Montanari, U. 1988. On the Consistency of ?Truly Concurrent? Operational and Denotational Semantics. In Proc. 3rd Symp. on Logics in Computer Science, IEEE , pp. 133-141. |
| [10] | Desel, J., and Esparza, J. 1995. Free Choice Petri Nets. Cambridge University Press. · Zbl 0836.68074 |
| [11] | Engelfriet, J. 1991. Branching processes of Petri nets. Acta Informatica 28: 575-591. · Zbl 0743.68106 |
| [12] | Esparza, J., and Römer, S. 1999. An unfolding algorithm for synchronous products of transition systems. In Proc. of CONCUR?99, LNCS Vol. 1664, Springer Verlag. · Zbl 0946.68097 |
| [13] | Fabre, E. 2002a. Compositional models of distributed and asynchronous dynamical systems. In Proc. of the 2002 IEEE Conf. on Decision and Control, Las Vegas, December, pp. 1-6. |
| [14] | Fabre, E. 2002b. Monitoring distributed systems with distributed algorithms. In Proc. of the 2002 IEEE Conf. on Decision and Control, Las Vegas, December, pp. 411-416. |
| [15] | Fabre, E. 2003. Convergence of the turbo algorithm for systems defined by local constraints. IRISA Res. Rep. 1510. |
| [16] | Fabre, E., Benveniste, A., and Jard, C. 2002. Distributed diagnosis for large discrete event dynamic systems. In Proc. of the IFAC Congress, July. |
| [17] | Fabre, E., Benveniste, A., Haar, S., and Jard, C. 2003. Distributed monitoring of concurrent and asynchronous systems. In R. Amadio and D. Lugiez (eds.), Proc. of 14th Int. Conf. on Concurrency Theory, CONCUR? 2003, LNCS 2761, pp. 1-26. · Zbl 1274.68221 |
| [18] | Fabre, E., Benveniste, A., Haar, S., and Jard, C. 2004a. Distributed monitoring of concurrent and asynchronous systems. Extended version of this paper. IRISA Res. Rep. 1636, also INRIA Res. Rep. 4842, version 2, July. · Zbl 1077.68059 |
| [19] | Fabre, E., Benveniste, A., Haar, S., Jard, C., and Aghasaryan, A. 2004b. Algorithms for distributed fault management in telecommunications. In 2004 International Conference on Telecommunications, Fortalezza, Brasil, 2-7 August. |
| [20] | Genc, S., and Lafortune, S. 2003. Distributed diagnosis of discrete-event systems using Petri nets. In W. M. P. van der Aalst and E. Best (eds.), Proc. of ICATPN 2003, LNCS 2679, pp. 316-336. · Zbl 1274.68234 |
| [21] | Haar, S., Benveniste, A., Fabre, E., and Jard, C. 2003 . Partial order diagnosability of discrete event systems using Petri net unfoldings. In Proceedings of the 42nd Int. IEEE Conference on Decision and Control, Maui, 9-12 December. |
| [22] | Lamperti, G., and Zanella, M. 2003. Diagnosis of Active Systems, Kluwer Academic Publishers. · Zbl 1044.93002 |
| [23] | McMillan, K. 1992. Using Unfoldings to avoid the state explosion problem in the verification of asynchronous circuits. In 4th Workshop on Computer Aided Verification, pp. 164-174. |
| [24] | Nielsen, M., Plotkin, G., and Winskel, G. 1981. Petri nets, event structures, and domains. Part I. Theor. Comp. Sci. 13: 85-108. · Zbl 0452.68067 |
| [25] | Pencolé, Y., Cordier, M-O., and Rozé, L. 2002. A decentralized model-based diagnostic tool for complex systems. In International Journal on Artificial Intelligence Tools. World Scientific Publishing Company, 11(3): 327-346. |
| [26] | Reisig, W. 1985. Petri Nets. Springer Verlag. · Zbl 0604.68068 |
| [27] | Sampath, M., Sengupta, R., Lafortune, S., Sinnamohideen, K., and Teneketzis, D. 1995. Diagnosability of discrete-event systems. IEEE Trans. Autom. Control 40(9): 1555-1575. · Zbl 0839.93072 |
| [28] | Sampath, M., Sengupta, R., Sinnamohideen, K., Lafortune, S., and Teneketzis, D. 1996. Failure diagnosis using discrete event models. IEEE Trans. Syst. Technol. 4(2): 105-124, March. |
| [29] | Su, R., Wonham, W.M., Kurien, J., and Koutsoukos, X. 2002. Distributed diagnosis for qualitative systems. In 6th International Workshop on Discrete Event Systems (WODES?02), Zaragoza, Spain, 2-4 October, pp. 169-174. |
| [30] | Su, R. 2004. Distributed Diagnosis for Discrete-Event Systems, Ph.D. Thesis, Department of Electrical and Computer Engineering, University of Toronto, June. |
| [31] | Vaandrager, F. 1989. A simple definition for parallel composition of prime event structures. CWI Report CS-R8903, March. |
| [32] | Winskel, G. 1982. Event structure semantics for CCS and related languages. In M. Nielsen, and M. Schmidt (eds.), Proceedings of ICALP 82, LNCS 140, pp. 561-576, Springer-Verlag. Extended version as DAIMI Research Report, University of Aarhus, 67 pp., April 1983. |
| [33] | Winskel, G. 1985. Categories of Models for Concurrency. Seminar on Concurrency, Carnegie-Mellon University, July 1984. LNCS 197: 246-267. |
| [34] | Winskel, G. 1987. Event structures. In W. Brauer, W. Reisig and G. Rozenbegr (eds.), Petri Nets: Applications and Relationships to Other Models of Concurrency. Advances in Petri Nets 1986, Part II, Springer-Verlag. LNCS 255: 325-392. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
