Petri Nets and Timed Petri Nets in Modeling and
\nAnalysis of Concurrent Systems – An Overview

Petri nets are formal models of systems which
\nexhibit concurrent activities. Communication networks,
\nmultiprocessor systems, manufacturing systems and dis-
\ntributed databases are simple examples of such systems. As
\nformal models, Petri nets are bipartite directed graphs, in
\nwhich the two types of vertices represent, in a very gen-
\neral sense, conditions and events. An event can occur only
\nwhen all conditions associated with it (represented by arcs
\ndirected to the event) are satisfied. An occurrence of an
\nevent usually satisfies some other conditions, indicated by
\narcs directed from the event. So, an occurrence of one event
\ncauses some other event to occur, and so on.
\nIn order to study performance aspects of systems modeled
\nby Petri nets, the durations of modeled activities must also
\nbe taken into account. This can be done in different ways,
\nresulting in different types of temporal nets. In timed Petri
\nnets, occurrence times are associated with events, and the
\nevents occur in real–time (as opposed to instantaneous oc-
\ncurrences in other models). For timed nets with constant or
\nexponentially distributed occurrence times, the state graph
\nof a net is a Markov chain, in which the stationary prob-
\nabilities of states can be determined by standard methods.
\nThese stationary probabilities are used for the derivation of
\nmany performance characteristics of the model.
\nAnalysis of net models based on exhaustive generation of
\nall possible states is called reachability analysis; it provides
\ndetailed characterization of model’s behavior, but often re-
\nquires generation and analysis of huge state spaces (in some
\nmodels the number of states increases exponentially with
\nsome model parameters, which is known as “state explo-
\nsion”). Structural analysis determines the properties of net
\nmodels on the basis of connections among model elements;
\nstructural analysis is usually much simpler than reachability
\nanalysis, but can be applied only to models satisfying certain
\nproperties. If neither reachability nor structural analysis is
\nfeasible, discrete–event simulation of timed nets can be used
\nto study the properties of net models.
\nThis paper overviews basic concepts of Petri nets, intro-
\nduces timed Petri nets, and provides brief summaries of sev-
\neral case studies of performance analysis which are discussed
\nin greater detail in other publications of the author.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.