Stochastic Well-formed Nets

Stochastic Well Formed Nets (SWN) [19] are a colored extension of GSPNs that allow to build a more compact and parametric representation of a symmetric system by folding similar subnets. In this way it is possible to represent very concisely systems that would have required a huge uncolored net. When similar subnets are folded, some additional annotation is needed to distinguish tokens that end up being in the same folded place.

These annotations constitute the color structure of the net. Tokens are no longer indistinguishable: each token can be regarded as an instance of a data structure whose meaning depends on the place to which the token belongs.

The place color domain (denoted C(p)) is defined as the Cartesian product of basic color classes, possibly with repetitions of the same basic color class. Each basic color class is a finite set of basic objects and it is usually defined by enumeration of its elements (e.g. C ={c1, c₂, . . . c_n}). Color classes may be ordered and may be

2We will not use this set in the models presented in the thesis

partitioned into disjoint subsets called static subclasses. Color domain of transitions (denoted C(t)) are defined analogously to color domain of places.

The enabling check of a transition and the state change caused by its firing depend on the arc functions that label the arcs connecting the transition to input, inhibitor and output places.

Arc functions are formal sums of tuples structured according to the corresponding place color domain. If the place color domain is the Cartesian product of k basic color classes, then the corresponding arc function is a weighted sum of k-tuples. The j^th element in each k-tuple is a weighted sum of three basic functions, the identity function (denoted by a variable), the successor function (“!”), and the synchronization function (“S”).

The weights of the sum may be numbers or predicates. Predicates are logical expressions used to test either equality of pairs of basic objects, selected by some identity/ successor function, or to check the membership of a selected basic object in a given static subclass.

A major interest of SWNs is that they provide a modeling framework in which the intrinsic symmetries are au-tomatically detected and used naturally as a way for reducing the size of the underlying state space. The reduction is obtained thanks to the original concept of symbolic marking. Informally a symbolic marking corresponds to an equivalence class representing a set of ordinary markings characterized by a common future behavior. These ordinary markings in fact enable the same transitions whose firings lead to new ordinary states which are still equivalent, i.e., belong to the same symbolic marking. Symbolic markings are obtained by disregarding the iden-tities of the objects within the places of the net and considering only their number. Color classes are partitioned into dynamic subclasses and the only relevant information is the cardinality of these subclasses (i.e., the number of objects they contain). This shows how many elements in the net have the same behavior at the same time.

This type of partitioning varies from one marking to another, hence it must not be confused with the static subclass partitioning which is part of the color class definition.

With the introduction of dynamic subclasses places no longer contain colored tokens but symbolic tokens whose components are expressed in terms of dynamic subclasses. All the ordinary markings which can be obtained by assigning identities to the objects of the dynamic subclasses belong to the same symbolic marking.

A symbolic enabling rule and a symbolic firing rule, which operate directly on the symbolic marking repre-sentation, and an efficient algorithm for the generation of an aggregated state space called symbolic reachability graph (SRG) have been defined [19] and implemented [69]. The SRG describes the evolution of a SWN model through a set of macro-states, the symbolic markings, that represent sets of more detailed states which are equiv-alent. Several properties valid for the SRG have been introduced. For example, the equivalence between the SRG and the RG from the point of view of the reachability of the markings ensures that no information is lost by ana-lyzing the SRG instead of the RG. Formulae have been defined to compute both the number of ordinary markings belonging to the same equivalence class and the number of ordinary firings represented by each symbolic firing.

Let us consider again, for example, the communicating processes whose behavior has been represented by the GSPN model of Figure 2.5: the communication between two processes a_i and b_j (i = 1, 2 and j = 1, 2, 3)

CHAPTER 2. BACKGROUND 31

Figure 2.6: GSPN (A) and SWN (B) models of several communicating processes.

belonging to the two different groups A and B, was carried out without considering the identities of the processes.

Let us assume now that communication is performed exclusively between the pairs (ai, bj), where i = j.

Under this restriction, “send” and “receive” actions have to contain information on the identities of the sender and of the receiver. The behavior of the processes can be represented, then, either by the GSPN model shown in Figure 2.6(A) or by the SWN model shown in Figure 2.6(B). The GSPN model is characterized by 32 tangible markings. There are two dead transitions: rvc_b3and ok_b3 that correspond, respectively, to the reception and to the reception confirmation of messages executed by the unpaired process b3. Since b3does not interact with any other process these transitions will never fire. The SWN model captures the identities of the processes through the definition of the place color domain C and the definition of the initial state for processes of group A (Ma) and for processes of group B (M_b). The color domain is defined as the union of two static subclasses: SubC1, with one element c₁, and SubC2, with two elements c₂ and c₃. The initial marking M_a is a dynamic subclass and it contains two tokens of colors c2and c3, while the initial marking Mbcontains three tokens of colors c1, c2

and c₃. The pairs of sender and receiver (a_i, b_j)_{i= j} are defined through the guards of transitions rcv_b and ok_a. Actually, the SWN model is the folding of the GSPN model of Figure 2.6(A): they have the same RG. At a first sight, it seems that all the transitions are live: but it can be verified that transitions rev_b and ok_b never fire for color c1. Unlike the GSPN model it allows to exploit symmetries: indeed, its SRG is characterized by 20 tangible symbolic markings (actually, processes a1and a2behaves in the same way as well as processes b1and b2).

Concerning performance results we have computed the (steady state) mean execution time of a process belong-ing to group A with the same input parameters and service policy used for the computation of the metrics on the

p1

p2

t1

p4

p5

t3

p6

p7

t4

Lx Lx Lx

S_1 S_2

p1

p3

t23

p6

p7

t24

Lx Lx

p4

p5

S_12

t2

p3 p2

t1

{Lx}

Figure 2.7: Composition of two GSPN component models over transitions.

GSPN model of Figure 2.5. The result is E[Texec_ai] = 2, 333, i = 1, 2 for both the GSPN and SWN models of Figure 2.6. Comparing this result with the value obtained for the same index on the GSPN model of Figure 2.5, we have in this case a worse performance due to the constraint on the process identities.

Observation: Generalized Stochastic Petri Nets and their colored version (SWNs) are extensions of the SPNs defined by M.Molloy [61]. In this thesis we will always refer to either GSPNs or SWNs, although in some context we have used the acronym “SPN” to indicate Petri Net model that can be either GSPN or SWN.