Nets within Nets

Nets within Nets is a modelling method belonging to the family of Petri nets. This method is distinguished from other sorts of Petri nets by the possibility to provide their tokens with a proper structure, which is based on Petri net modelling again. Hence, a net can contain further net items, being able to move around and fire themselves.

Motivation

Nets within nets are well suited for the modelling of distributed systems under the particular aspects of

  • hierarchy,
  • mobility
  • encapsulation.

In a lot of publications in relation to object-oriented design is given, in order to combine the ability of Petri nets in modelling distributed computing with the modelling of objects, being able to be created and to interact.

History

Starting from the need of practical applications, by the mid of nineties, different formalisms have been created, which fit the description of „nets within nets“. Lomazova and Schnoebelen are listing[1] some of these approaches, namely by Sibertin-Blanc,[2] Lakos,[3] Moldt und Wienberg[4] as extending Coloured Petri nets, aside the Object Nets of Valk.[5] The earliest use of such hierarchic net models appeared by Rüdiger Valk in Valk and Jessen,[6] where the so-called task-flow nets[7] are introduced in order to model task systems in operating systems. In these models tasks are modelled by a Petri net, which represents the precedences of tasks and their state of execution.

Semantics

The most important differences in semantics is given by the execution of net tokens. On the one side net tokens can be references to net items,[8] which case is called „reference semantics“. This kind of semantic is distinguished from value semantics, where net objects may exist in different places and different internal states. In value semantics different copies can be created to model concurrent execution. The corresponding join of such a split can be defined in different ways, as for instance by „distributed token semantics“[9] or „history process semantics“.[10] In connection with mobile computing hybrid versions of reference and value semantics are of importance.[11] In distributed token semantics the important calculus of place invariants for Petri nets remains valid.[12]

Communication

The formalism of nets within nets would be of few importance without communication between net tokens. Like in object-oriented programming communication of net tokens is introduced via predefined interfaces which are dynamically bound.

Figure 1: Nested Petri net containing channels via inscriptions

In Figure 1 a Petri net is shown containing a token Petri net in place „a“. The token net can move around from place „a“ to place „b“ and back by firing of the transitions of the outer net. The channel inscriptions at the transitions behave like a call of a method, resulting in the synchronised firing of the calling transition in the outer net [e.g. labelled by x:forth()] and the called transition [e.g. labelled by :forth()] in the token net. The variable „x“ at an arrow is bound to the token net in the place connected with this arrow. The brackets may contain parameters to be passed. This example is so simple that reference and value semantics coincide.

Algorithms and restricted formalisms

Standard Petri net properties like reachability, boundedness and liveness show a mixed picture. A paper [13] of Köhler-Bußmeier gives a survey on decidability results for elementary object systems. To reduce the complexity of the formalism subclasses have been defined by restricting the structure of the Petri nets, as for instance to state machines. Such restrictions still allow complex modelling of distributed and mobile systems, but have polynomial complexity in model checking.[14]

Tools

References
  1. Irina A. Lomazova, Philippe Schnoebelen: Some decidability results for nested Petri nets, Springer LNCS 1755, 2000, pp. 208-220
  2. Christophe Sibertin-Blanc: Cooperative Nets, Springer LNCS 815, 1994, pp. 471-490
  3. Charles Lakos: From coloured Petri nets to object Petri nets, Springer LNCS 935, 1995, pp. 278-297
  4. Daniel Moldt und Frank Wienberg: Multi-agent-systems based on coloured Petri nets, Springer LNCS 1248, 1997, pp. 82-101
  5. Rüdiger Valk: Petri nets as token objects, Springer LNCS 1420, 1998, pp. 1-24
  6. Eike Jessen, Rüdiger Valk: Rechensysteme: Grundlagen der Modellbildung, Springer, 1987
  7. Rüdiger Valk: Modelling Concurrency by Task/Flow EN Systems. Proceedings 3rd Workshop on Concurrency and Compositionality, GMD-Studien Nr. 191, Bonn, 1991
  8. Olaf Kummer: Referenznetze, Dissertation, Universität Hamburg, Logos Verlag Berlin 2002
  9. Michael Köhler, Heiko Rölke: Properties of Object Petri Nets. Springer LNCS 3099, 2004, pp. 278-297
  10. Rüdiger Valk: Object Petri Nets, Springer LNCS 3098, 2004, pp. 819-848
  11. Berndt Farwer, Michael Köhler: Modelling global and local name spaces for mobile agents using object nets, Fundamenta Informaticae, Vol. 72, No 1, pp. 109-122, 2006
  12. Michael Köhler-Bußmeier, Daniel Moldt: Analysis of mobile agents using invariants of object nets. Electronic Communications of the EASST: Special Issue on Formal Modeling of Adaptive and Mobile Processes, 12, 2009. http://www.easst.org/eceasst/
  13. Michael Köhler-Bußmeier: A Survey of Decidability Results for Elementary Object Systems: Fundamenta Informaticae, Vol. 130, No 1, pp. 99-123, 2014
  14. Frank Heitmann, Michael Köhler-Bußmeier: P- and t-systems in the nets-within-nets formalism: Springer LNCS 7347, 2012, pp. 368-387
  15. Olaf Kummer, Frank Wienberg, Michael Duvigneau, Jörn Schumacher, Michael Köhler, Daniel Moldt, Heiko Rölke, Rüdiger Valk, : An Extensible Editor and Simulation Engine for Petri Nets: Renew: Springer LNCS 3099, 2004, pp. 484-493
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.