Systems Dependability Assessment Set
coordinated by
Jean-François Aubry
First published 2016 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.
Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:
ISTE Ltd
27-37 St George’s Road
London SW19 4EU
UK
www.iste.co.uk
John Wiley & Sons, Inc.
111 River Street
Hoboken, NJ 07030
USA
www.wiley.com
© ISTE Ltd 2016
The rights of Jean-François Aubry, Nicolae Brinzei and Mohammed-Habib Mazouni to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.
Library of Congress Control Number: 2015960014
British Library Cataloguing-in-Publication Data
A CIP record for this book is available from the British Library
ISBN 978-1-84821-991-5
In the first book of this series [AUB 15], finite state automata were introduced as an efficient model for the study of reliability and dependability of systems as well in static as in dynamic context. We saw that this type of model requires either an a priori exhaustive knowledge of the possible states of the system or its formal construction by operations starting from the models of its components. This is unfortunately sometimes not possible. For example, during the design of a system these states are not known in advance. It is however useful to make a predictive dependability assessment in order to select the best solution among some propositions. Petri nets may be an interesting way to answer such problems. Widespread in the field of automatic control, especially for the modeling of discrete event systems, Petri nets were introduced in the field of dependability studies with a noticeable success. The objective of this book is not to present all of the forms of Petri nets used in dependability assessment but instead to focus on the most interesting ones. Before their description, we give a preliminary formal description of the different successive models of Petri nets which led to the advent of their use in the dependability field. Of course, it is not just a matter of exhaustively describing the existing variants of the basic models which are today hardly countable. In the same way, we will not demonstrate all the mathematical properties of these models and we will refer the reader to the essential basic works on the subject. After the introduction of the basic models called “autonomous Petri nets” and the comparison with the finite state automata especially in terms of event language expression, we will present the fundamental models of non-autonomous Petri nets to take account of the time and of an external environment, such models giving an opening to the study of hybrid systems. Relying on these timed and synchronized Petri nets, we will describe a systematic method of risk analysis based on an ontological approach whose elements are entities (supplier or target of hazard), their successive states and the events corresponding to these state changes. From the proposed model, a risk assessment may be deduced by simulation thanks to the introduction of random event generators. This approach is illustrated by an example from the railway transportation field. The need of models, integrating the stochastic character of elements (in this case, events) and allowing an analytical solution instead of simulation, leads to the introduction of stochastic Petri nets modeling and its equivalence conditions with Markov or some extensions of Markov models. We then show how, under some conditions, complex models may be simplified by a distribution of the global model on the two formalisms: stochastic Petri nets and Markov processes. Numerous extensions of Petri nets have been proposed; we recall the most significant ones and the conditions of their Markov process equivalence. To complete the book, we present some modeling examples using different available software tools. These examples are issued from different application domains.
Writing this book would not have been possible without the contribution of colleagues and of PhD and Master students who investigated some related aspects. All of these contributions have been the subject of publications and are referenced in the text. We would like to extend our thanks to G. Babykina, P. Barger, G. Deleuze, L. Gérard, R. Ghostine, D. Jampi, J. Lalouette, R. Schoenig, J-M. Thiriet and N. Villaume.
Petri nets (denoted as PN in this book) were introduced by Carl Adam Petri in 1962 [PET 62]. As finite state automata (FSA) described in Volume 1 of this book series [AUB 15], PNs are intended to describe discrete event systems but contrary to FSAs, the transition function is explicitly described in PNs. Adding the suggestive and intuitive graphic representation, we can say that PN is a more powerful model than FSA to describe discrete event systems, due to the fact that an FSA may always be transposed into PN whereas PNs, for example, do not always have a finite state number. We will show here that the notion of language, set of all the possible event sequences in a system, may also be associated with a PN and that the class of these languages is wider than regular languages associated with FSAs.
Like for FSAs, PNs were the subject of multiple extensions at first to move them from the abstraction level, where only event sequencing is considered, to the level taking time into account. Timed PNs were defined to describe behavior of deterministic time systems. Following extensions, called non-autonomous PNs, associated with a PN, an external environment is needed in order to consider synchronization events, continuous variables, especially to describe controlled systems. All these models at various levels have an interest to model problems in the dependability assessment of systems.
A unmarked PN is a bipartite oriented 1-graph1 provided with a mapping 
from the set of arcs to the positive integer set 
+:
∀a ∈ A, if α(a) ∈ T then β(a) ∈ P
if α(a) ∈ P then β(a) ∈ T
is a mapping or weighting function associating an integer with each arc, : A → +.If is reduced to {1}, the PN is of ordinary type (or state transition graph), otherwise the PN is of generalized type.
Practically, rather than this formalism directly issued from the graph theory, we will use a definition where A does not explicitly appear. As it is an 1-graph, it consists of considering all the couples (Pi, Tj) or (Ti, Pj) and two applications ω− and ω+.
The PN is then defined as:
DEFINITION 1.1.– An unmarked PN or Place/Transition (P/T) net is a 4-uple Q = 
P, T, w−, w+
[DAV 89] where:
is the backward transition function; is the forward transition function.The value “0” associated with the couple (Pi, Tj) by ω− or ω+ means that there is no arc between Pi and Tj or Tj and Pi. If the value k ∈ + is associated with this couple by ω−, respectively ω+, then one arc oriented from Pi to Tj, respectively from Tj to Pi, exists between these nodes with the valuation k.
REMARK 1.1.– Another possibility is to define a PN as an n-graph (n arcs may exist between two nodes), an arc of weight n being replaced by n arcs each of them having the weight one.
In the drawing of a PN, places and transitions are, respectively, represented by circles and streaks (or filled or empty rectangles) and the arcs are arrows to which the weights are attached. Figure 1.1 shows an example of PN with three places and two transitions respectively named as P1, P2, P3, T1, T2. From this figure, we can write ω−(P1, T1) = 1, ω− (P3, T2) = 2, ω− (P2, T1) = 2, ω+(P3, T1) = 2, ω+ (P1, T1) = 1, ω+ (P2, T2) = 3.
Figure 1.1. The drawing of a PN
Some of other definitions concerning particular cases of PN are summarized in the Appendix, section A.1.
Notations [DAV 89]:
For example, in Figure 1.1, I (T1) = {P1, P2} and O (T1) = {P3, P1}.
The marking is a notion resulting from the association of tokens with the places of the PN. The position in the places of these tokens will evolve to represent the dynamics of the described system. This evolution is performed according to a set of rules described in section 1.3.
DEFINITION 1.2.– A marked PN is a couple R = Q, M0 where Q is an unmarked PN and M0 is an initial marking.
The marking M of a PN at a given instant is a p-sized columnar vector of integers (p is the place number of the PN), each of its component being the marking (or charge) of the place Pi that is to say the number of tokens inside Pi at the considered time instant:
The initial marking M0 is the marking at time t = 0.
Figure 1.2 shows the initial marking of the PN of Figure 1.1 with: 
.
Figure 1.2. A marked PN
Let us consider two markings M1 and M2 of a PN.
We define the order relation between these markings as follows:
The transition Tj is enabled for a given marking M if and only if:
In Figure 1.1, only the transition T1 is enabled.
The previously defined notion of marking is the observation means of the evolution of the model. The position of the tokens will evolve according to a set of formal rules allowing the definition of some properties of the model. This will be recalled in the following, and more details may be found, for example, in [CAS 08, DAV 92, BES 01].
As PNs are models dedicated to discrete events systems, the firing of a transition may be considered as an event describing an elementary evolution of a system (see section 2.1 for the formal definition of labeled PN) characterized by the successive values of the marking before and after the firing. An enabled transition may be fired; from a given marking, each enabled transition could be fired but only one will be. The choice of the transition to be fired can be done arbitrarily. When a place has two output transitions their firings are in conflict. This notion of conflict (formally defined in Appendix A1.1) will be retrieved, for example, each time a failure occurs concurrently with a task activation or achievement. Some PN-dedicated software tools give the possibility of priority assignment to a transition concerned by a conflict, but this must be carefully handled to avoid the appearance of dead branches in the reachability graph. Two transitions T1, T2 ∈ O (Pi) are not in conflict if they are not simultaneously enabled, which implies that these transitions have input places other than Pi.
The set of the enabled transitions must always be considered according to the current marking of the PN and not limited to a given place.
If Mb is the marking before the firing of Tj, the marking Ma after the firing is defined by:
The firing of the transition Tj subtracts in place Pi as many tokens as indicated by ω− (Pi, Tj) and adds in place Pk as many tokens as indicated by ω+(Pk, Tj).
Figure 1.3 shows the PN of Figure 1.2 after the firing of transition T2.
Figure 1.3. PN of Figure 1.2 after firing of transition T2
DEFINITION 1.3.– Let us define the backward matrix and forward matrix, as the following matrices with p lines and t columns:
The transition matrix W is defined by:
The transition matrix (p lines and t columns) is independent of the marking, each column simply shows the number of tokens to remove or add in a place when the corresponding transition fires. For Figure 1.1:
DEFINITION 1.4.– A firing sequence is obtained when a set of transitions are successively fired, starting from an initial marking. It is represented by the concatenation of the successive names of the fired transitions.
If for example starting from the initial marking M0 the transitions T1 then T2 are fired to give the marking M2, the sequence will be denoted as:
REMARK 1.2.– The transition set T provided with the concatenation operation and a neutral element may be considered as a monoid denoted by T*. With such a notation, a firing sequence is one element of this monoid: S ∈ T*. This notation will sometimes be used later.
DEFINITION 1.5.– Let S be a firing sequence feasible from a marking Mi, the characteristic vector of the sequence denoted as N is a t size vector, whose jth component represents how many times the transition Tj is fired in the sequence S:
The M vector cannot take any value. From a given marking M0, it is possible to list all the possible firing sequences. The obtained marking after each of these sequences is a reachable marking.
Let us note that R(M0) is the set of the reachable marking from the initial marking M0:
In FSA, we defined the state changes by the mean of the transition function. In PNs, this function is defined as follows:
f (Mk, Tj) is defined if and only if Tj is enabled, in this case, f (Mk, Tj) = Mk+1 with:
Mk+1(Pi) = Mk(Pi) – ω– (Pi, Tj) + ω+(Tj, Pi) for Pi ∈ I (Tj) ∪ O(Tj)
As for the FSAs, we can extend f from the domain p × T to the domain p × T* (T* being the monoid on the set T provided with the concatenation operation (see section 1.3.3)) and define for a given initial marking, the new obtained marking after a firing sequence of characteristic vector N.
We then obtain the fundamental matrix equation as:
For Figure 1.2, let us imagine from the initial marking, the firing sequence T2T1. After the firing of T2, the obtained marking is shown by Figure 1.3 and after the firing of T1 it becomes as indicated by Figure 1.4.
Figure 1.4. PN state of Figure 1.3 after firing of transition T1
As the two components of the vector N are 1 and 1, each of the two transitions being fired one time, the obtained marking may be retrieved by the following calculus:
A set of definitions and properties are summarized here. For a complete description and formal demonstrations of properties, we can report to [DAV 89, CAS 08, DAV 92, BES 01, BRA 83]:
- a place of a PN is bounded for a given initial marking M0 if for any accessible marking from M0 the token number in this place remains finite. If ∀Mn ∈ R(M0), Mn(Pi) ≤ k with k ∈
- a PN is bounded for a given initial marking M0 if all the places are bounded for M0.
If ∀Pi ∈ P, ∀Mn ∈ R(M0), Mn(Pi) ≤ k with k ∈ , then the PN is k-bounded.
These properties are dependent of the initial marking but sometimes a PN may be structurally bounded, that is to say bounded for any initial marking.
- a transition Tj is alive for a given marking M0 if ∀Mn ∈ R(M0),
S : M0
Mn/Tj ∈ S (there is always a firing of Tj),
- a PN is alive for a given marking M0 if all its transitions are alive for M0.
- a blocking is a marking from which any transition is enabled. It corresponds to an absorbing state,
- a PN is blocking free for a given initial marking M0 if no marking Mn ∈ R(M0) is a blocking.
Liveness and blocking are properties dependant on the initial marking M0.
Some other properties are summarized in Appendix A.1.
It should be noted that sometimes the weighted sum of the markings of a subset of places remains constant. This is an invariant of this subset which is called conservative component of the PN. As it is independent of the initial marking, this is a property of the unmarked PN (the value of this constant may only depend on the initial marking). In most cases, this is the characteristic of a physical property of the modeled system.
A P-semi-flow is a vector F of integers of dimension p (number of places of the PN) so that:
According to the fundamental equation Mk = Mi + W ∙ N (for any accessible marking from Mi by a firing sequence S characterized by the vector N): FT ∙ Mk = FT ∙ Mi + FT ∙ W ∙ N. If FT ∙ W = 0 we obtain:
which is the marking invariant.
The integers of the vector F may be considered as weights assigned to the places of the PN. The subset of places whose weights are null is the PN conservative component support of the P-semi-low. It will be noted PF.
Any linear combination of a semi-flow is itself a semi-flow.
Let PF = {P1, P2, …, Pr} be a conservative component of a PN and F = [q1, q2, qr]T the corresponding weighting vector. All the places of the conservative component are bounded and we get: M (Pi) ≤ FT ∙ M0/qi.
For example, it is easy to verify that in the PN of Figure 2.1 (see section 2.2) the subset of places {P4, P5} is a conservative component, the sum of their marking is always equal to 1 (the initial marking of P4).
In the same way, a T-semi-flow is defined: W ∙ F = 0.
Here, the weighting vector of integers is a vector N (dimension = t, Nj, being the firing number of Tj) associated with a transition sequence S. Let us note TS the transition subset fired at least once in the sequence S.
TS is a stationary repetitive component if and only if
TS is an increasing repetitive component if and only if W ∙ N > 0.
If W ∙ N = 0, then N is a T-semi-flow but any semi-flow does not necessarily correspond to a repetitive component because it must correspond at least to a firing sequence.
If S is a repetitive sequence from the marking M1 ∈ R(M0) and if S is also a firing sequence from M2 ∈ R(M0), then S is also a repetitive sequence from M2 (see fundamental equation).
For Figure 2.1 (see section 2.2), the transition set {T2, T3} is a repetitive component because a firing of T2 leads to a firing of T3 and so on.
The evolution of the marking due to transition firings may be represented by a graph called a reachability graph.
The reachability graph of a PN RG(M0) is a graph whose nodes are associated with the successive values of the marking vector from initial marking M0 and whose arcs correspond to the firings of transitions. All the properties of a PN may be retrieved on the reachability graph.
Let us consider the PN of Figure 1.5 (left) and its initial marking with two tokens in place P1 and one in place P3. The corresponding reachability graph is on the right-hand side of the figure. The node [2, 0,1, 0]T corresponds to the initial marking that may evolve by firing of transitions T or T2 to reach respectively the markings [1,1,1, 0]T and [2, 0, 0,1]T, and so on.
Figure 1.5. A marked PN and its reachability graph
In the current example, the reachability graph is finite but it is possible that it is not the case, meaning that the PN is not bounded (see section 1.3.6). It is then possible to define a finite covering graph by the identification of cycles in the reachability graph [DAV 89, DAV 92, DIA 01].