Asynchronous Box Calculus

• Autorzy: Devillers R. , Klaudel H. , Koutny M. , Pommereau F.
• Języki publikacji: EN

Abstrakty

EN

The starting point of this paper is an algebraic Petri net framework allowing one to express net compositions, such as iteration and parallel composition, as well as transition synchronisation and restriction. We enrich the original model by introducing new constructs supporting asynchronous interprocess communication. Such a communication is made possible thanks to special `buffer' places where different transitions (processes) may deposit and remove tokens. We also provide an abstraction mechanism, which hides buffer places, effectively making them private to the processes communicating through them. We then provide an algebra of process expressions, whose constants and operators directly correspond to those used in the Petri net framework. Such a correspondence is used to associate nets to process expressions in a compositional way. That the resulting algebra of expressions is consistent with the net algebra is demonstrated by showing that an expression and the corresponding net generate isomorphic transition systems. This results in the Asynchronous Box Calculus (or ABC), which is a coherent dual model, based on Petri nets and process expressions, suitable for modelling and analysing distributed systems whose components can interact using both synchronous and asynchronous communication.

Słowa kluczowe

EN

Petri net; process algebras; synchronous communication; asynchronous communication; Structured Operational Semantics (SOS)

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 54, nr 4
• Strony: 295--344
• Opis fizyczny: bibliogr. 29 poz.

Twórcy

autor

Devillers R.

autor

Klaudel H.

autor

Koutny M.

autor

Pommereau F.

• LACI, Universite Paris XII, 61, avenue du Général de Gaulle 94010 Créteil, France,

Bibliografia

• [1] J. Baeten and W. P. Weijland: Process Algebra. Cambridge Tracts in Theoretical Computer Science 18, Cambridge University Press (1990).
• [2] T. Basten and M. Voorhoeve: An Algebraic Semantics for Hierarchical P/T Nets. Proc. of ICATPN’95, G. DeMichelis and M. Diaz (Eds.). Springer, Lecture Notes in Computer Science 935 (1995) 45-65.
• [3] E. Best, R. Devillers and J. Hall: The Petri Box Calculus: a New Causal Algebra with Multilabel Communication. In: Advances in Petri Nets 1992, G. Rozenberg (Ed.). Springer, Lecture Notes in Computer Science 609 (1992) 21-69.
• [4] E. Best, R. Devillers and M. Koutny: A Unified Model for Nets and Process Algebras. In: Handbook of Process Algebra, J. A. Bergstra, A. Ponse, S. A. Smolka, (Eds.). Elsevier (2001) 873-944.
• [5] E. Best, R. Devillers and M. Koutny: Petri Net Algebra. EATCS Monographs on TCS, Springer (2001).
• [6] E. Best and R. P. Hopkins: B(PN) - a Basic Petri Net Programming Notation. Proc. of PARLE ’93, A. Bode, M. Reeve and G. Wolf (Eds.). Springer, Lecture Notes in Computer Science 694 (1993) 379-390.
• [7] G. Boudol and I. Castellani: Flow Models of Distributed Computations: Three Equivalent Semantics for CCS. Information and Computation 114 (1994) 247-314.
• [8] M. Broy and E-R. Olderog: Trace-Oriented Models of Concurrency. In: Handbook of Process Algebra, J. A. Bergstra, A. Ponse, S. A. Smolka, (Eds.). Elsevier (2001) 101-195.
• [9] P. Degano, R. De Nicola and U. Montanari: A Distributed Operational Semantics for CCS Based on C/E Systems. Acta Informatica 26 (1988) 59-91.
• [10] R. Devillers, H. Klaudel, M. Koutny, E. Pelz and F. Pommereau: Operational Semantics for PBC with Asynchronous Communication. Proc. of HPC’02, A. Tentner (Ed.). SCS (2002) 314-319.
• [11] R. J. van Glabbeek and F. V. Vaandrager: Petri Net Models for Algebraic Theories of Concurrency. Proc. of PARLE’87, J. W. de Bakker, A. J. Nijman and P. C. Treleaven (Eds.). Springer, Lecture Notes in Computer Science 259 (1987) 224-242.
• [12] U. Goltz and R. Loogen: A Non-interleaving Semantic Model for Nondeterministic Concurrent Processes. Fundamentae Informaticae 14 (1991) 39-73.
• [13] R. Gorrieri and U. Montanari: On the Implementation of Concurrent Calculi in Net Calculi: two Case Studies. Theoretical Computer Science 141(1-2) (1995) 195-252.
• [14] C. A. R. Hoare: Communicating Sequential Processes. Prentice Hall (1985).
• [15] P. W. Hoogers, H. C. M. Kleijn and P. S. Thiagarajan: An Event Structure Semantics for General Petri Nets. Theoretical Computer Science 153 (1996) 129-170.
• [16] R. Janicki and P. E. Lauer: Specification and Analysis of Concurrent Systems - the COSY Approach. EATCS Monographs on TCS, Springer (1992).
• [17] H. Klaudel: Parameterized M-expression semantics of parallel procedures. Proc. of DAPSYS’00, Kluwer Academic Publishers (2000) 85-94.
• [18] H. Klaudel and F. Pommereau: Asynchronous links in the PBC and M-nets. Proc. of ASIAN’99, P. S. Thiagarajan and R. Yap (Eds.). Springer, Lecture Notes in Computer Science 1742 (1999) 190-200.
• [19] H. Klaudel and F. Pommereau: A concurrent and Compositional Petri Net Semantics of Preemption. Proc. of IFM’2000, W. Grieskamp, T. Santen and B. Stoddart (Eds.). Springer, Lecture Notes in Computer Science 1945 (2000) 318-337.
• [20] M. Koutny and E. Best: Fundamental Study: Operational and Denotational Semantics for the Box Algebra. Theoretical Computer Science 211 (1999) 1-83.
• [21] R. Milner: Communication and Concurrency. Prentice Hall (1989).
• [22] U. Montanari and D. Yankelevich: Combining CCS and Petri Nets via Structural Axioms. Fundamentae Informaticae 20(1-3) (1994) 193-229.
• [23] E. R. Olderog: Nets, Terms and Formulas. Cambridge Tracts in Theoretical Computer Science 23, Cambridge University Press (1991).
• [24] J. Parrow: An Introduction to the -Calculus. In: Handbook of Process Algebra, J. A. Bergstra, A. Ponse, S. A. Smolka, (Eds.). Elsevier (2001) 479-543.
• [25] G. D. Plotkin: A Structural Approach to Operational Semantics. Technical Report FN-19, Computer Science Department, University of Aarhus (1981).
• [26] F. Pommereau: FIFO buffers in tie sauce. Proc. of DAPSYS’00, Kluwer Academic Publishers (2000) 95-104.
• [27] W. Reisig: Deterministic Buffer Synchronization of Sequential Processes. Acta Informatica 18 (1982) 117-134.
• [28] W. Reisig: Petri Nets. An Introduction. EATCS Monographs on TCS, Springer (1985).
• [29] D. Taubner: Finite Representation of CCS and TCSP Programs by Automata and Petri Nets. Springer, Lecture Notes in Computer Science 369 (1989).