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
some of these approaches, namely by Sibertin-Blanc, Lakos, Moldt und Wienberg as extending Coloured Petri nets, aside the Object Nets of Valk.
The earliest use of such hierarchic net models appeared by Rüdiger Valk in Valk and Jessen, where the so-called task-flow nets 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, 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“ or „history process semantics“. In connection with mobile computing hybrid versions of reference and value semantics are of importance. In distributed token semantics the important calculus of place invariants for Petri nets remains valid.

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.

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 .g. labelled by x:forth()and the called transition .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 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.

Tools

* CO-OPN https://smv.unige.ch//research-projects/co-opn (based on algebraic high level nets)
* RENEW http://www.renew.de (free development Model checking of reference nets with JAVA-Integration)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

References

{{reflist

Formal specification languages
Models of computation
Concurrency (computer science)
Diagrams

Software modeling language