The paper presents a method to distribute the generation of all possible bounded length sequences of events for a given Petri net. The crucial benet of our method is that it permits distributing of the generation process and allows to apply Big data processing techniques. The net is decomposed into functional fragments, each of them is simulated independently to produce the set of its sequences, which are combined to yield the sequences for the whole net. This process can be executed by structural induction, and facilitates re-usability of partial results. To limit the amount of data transferred during the computation, which is the critical factor, we represent these sequences in a compact form of Mazurkiewicz traces, which identify all sequences which dier by interchanging the order of subsequent independent events. Therefore a single trace corresponds to all distributed runs of the net, where tasks that can be executed concurrently are recorded in all possible orders. Our tool can be useful in process mining, in particular in conformance checking. In this use case, a Petri net model of a process is compared to its real-life behaviour, recorded in execution logs. As the investigated logs are large, the gain from distributing the computation is desired.
The focus of this paper is providing a methodology for ecient and distributed generation of the set of all limited length runs of a given Petri net.
Petri net (PN) [4] is a model of a distributed system. The formalism of such nets is a common and convenient modelling language. Their applications areas range from workow systems, representing decision processes in a business organization, through the design of control structures in concurrent programming, to the models of regulatory networks found in living cells.
One of the possible application areas for our tool is process mining [1, 6]. It is a relatively young research area, whose main aim is to develop methods and techniques to discover, monitor and modify real processes, making use of the knowledge implicitly present in their event logs. Certainly, achieving such a goal requires methodology to perform (automated) process discovery, i.e., constructing process models by mining the event log data. When the model is available, conformance checking becomes important it is the task of investigating and analysing deviations between the real process and its model. The next steps might then be model extension, model repair or case prediction.
The generation of all possible xed length runs of a model is our contribution towards conformance checking. Assuming that a Petri Net model of the process is already available, it is then natural to compare the sequences of events generated by the model with those indeed recorded in the log. It is relatively easy to do one way: check if the sequences of events present in the log are indeed permitted by the model. The other direction is much harder: to check if there are sequences of events permitted in the model, which do not appear in the event log, and if so, characterize them, estimate their frequency among all runs, discover their common properties, etc. In fact, using our tool to produce the complete set of sequences generated by the model (up to some length), allows one to mine the dierence between the model’s event log and the real system’s event log, providing otherwise unavailable information about what the real system cannot do, as opposed to its model. Existing solutions, like various applications of SAT-solvers, produce single runs, so can provide answers only to very detailed existence questions and do not provide the general picture.
Given a PN N and a limit k our tool produces the representation of all event sequences of length up to k of N . The cardinality of this set grows extremely fast with k, thus our goal was to distribute the computation. A nave method for exhaustive sequence generation would be to explore the possible state space. Such a method would be dicult to distribute due to excessive communication necessary to prevent repeated exploration of the same trajectories on dierent machines. The work could be distributed based on the order of events in the simulation, where each machine gets a fragment of the search space, composed of the sequences starting with a particular prex. Yet, for dierent prexes there can be signicant dierence in the number of possible result sequences, which would introduce skew and even if the computation would be balanced, then common suxes, or subsequences would lead to replication of work.
Instead we apply the techniques of Mazurkiewicz [3], where the sequences for the net can be obtained by combining sequences for its subnets. This allows us to reduce the problem to iterative Big data processing computation, which can be eciently distributed with Big data frameworks like Hadoop and Spark. Distributing the computation is done by structural induction on the PN model. This has additional practical consequences. In a net with several identical components it is enough to compute their behaviour once and then reuse it several times. To limit the amount of data transferred during the computation, which is the critical factor, rather than with sequences, we deal with Mazurkiewicz traces [3] and exploit the prex closure property. Each such trace represents a whole set of sequences, which dier only by interchanging the order of subsequent transitions that are independent in the net. This reduces the size of the data necessary to store all runs by many times without losing any signicant information. For example for sequences of length bounded by 7 we observed average reduction of 29 times. Indeed, every trace represents a set of runs in which subsequent independent events occur in dierent order or equivalently the trace represents a run where all subsequent independent events occur simultaneously. We further reduced the size of the representation (by 35% for the same example), thanks to the observation of the prex closure property for the sequences of events. However, even with this additional optimization and using the trace representation, we still end up in the Big data range even for not too large k.
For implementation of our ideas we use Apache Spark engine [7]. The additional advantage of this is that the computed traces are immediately available as Spark’s Resilient Distributed Dataset (RDD) and can be further processed/analysed without any overhead for parsing. Such post-processing could include analysing the deviations between the real observed process and the model, or computing some statistics, e.g., in which percent of all possible runs some chosen event always precedes some other event or what is the average delay/distance between some events. 2
We focus on elementary nets systems (ENS) [5] which are a kind of PN with a
restriction that each place can contain up to one token. That is, for a transition
to be enabled not only all its input places need to contain tokens, but also all
its output places need to be empty. Formally, ENS is an ordered triple (P, T, F ),
where P is a nite set of places, T a nite set of transitions and F ⊆ ((P ×
T ) ∪ (T × P )) denes the ow relation. The marking is dened as M ⊆ P and a
transition t is considered enabled if (
An ENS with an initial state denes a transition system whose size can be exponential with respect to the number of places. Such a system denes a language of sequences (strings) with symbols from T its net language that can be observed as the outcomes of possible runs of the system starting in the initial marking. Formally, for N = (P, T, F ) and for some initial marking M0, we say that sequence/string w = w1w2w3 . . . wn for wi ∈ T is in the net language of N if M0 −−→ M1 −−→ M2 −w−→3 . . . −w−→n Mn for some markings M1, . . . , Mn.
w1 w2 3
Synchronization of net languages [3] corresponds to composition of nets. We use the synchronization operation on net languages to distribute net language computation for complex nets by decomposing the net and then synchronizing net languages of the obtained components.
We consider composition for nets that have no common places but may have common transitions. During this operation such transitions form an interface on which the composition is conducted and are merged together. The marking of the composite net is obtained as the sum of the markings of the composed nets.
Composition of sequence of non-trivial nets N1, N2, . . . , Nn, where Ni = (Pi, Ti, Fi) and Pi ∩ Pj = ∅ for i 6= j, is dened as the net N1 + N2 + . . . + Nn = (S Pi, S Ti, S Fi). An example of the net composition is presented in Figure 1 for N1 = (P1, T1, F1) and N2 = (P2, T2, F2) where P1 ∩ P2 = ∅ and T1 ∩ T2 = {b, c} 6= ∅ is the common interface. The resulting net N1 + N2 = N is obtained by merging the interface transitions of the components. p1 a p2 p3 N1 b c b c p4 p5 N2
p1 + d =
a
Complementarily we can dene net decomposition of a non-trivial net by specifying partition of its set of places into non-empty sets. Each such set denes a subnet together with transitions adjacent to its places and corresponding edges (transitions can be replicated for multiple subnets). Suppose that we have a net N and its decomposition into N1 + N2 + . . . + Nn. The language L(N ) net language of N can be dened in terms of net languages L(N1), L(N2), . . . , L(Nn). Consider a seq ∈ L(N ). Observe, that each of nets Ni accepts a sequence πTi (seq) where πA(seq) is the projection of sequence seq onto alphabet A. This follows from the observation that if there exists a series of actions seq in system represented by N , then if we look only at places and transitions belonging to the component Ni and obscure remaining parts of the system we get πTi (seq).
Formally, synchronization [3] of (arbitrary) languages L1 over alphabet A1 and L2 over A2 is dened as the language L1 k L2 over alphabet A1 ∪ A2 such that: seq ∈ (L1 k L2) ⇔ πA1 (seq) ∈ L1 ∧ πA2 (seq) ∈ L2.
The smallest element of net decomposition, containing a single place, is called atom. Each net is a composition of all its atoms. We can observe that an atom A = ({p}, T, F ) for a marking M = {p} has a net language which is dened by the regular expression: ((p•)(•p))∗(p•+ ). This observation allows us to calculate the language of a net by decomposing it into atoms, calculating net languages of each atom and synchronizing those languages incrementally one by one.
We can analyse this using the resulting net from Figure 1. We will calculate net languages up to length 4. Let atom Ai be based on place pi for i = 1, 2, 3, 4, 5 and let the initial markings be given by projections of the marking presented in the gure. We have: L(A1) = { , a}, L(A2) = { , a, ab, aba, abab}, L(A3) = { , a, ac, aca, acac}, L(A4) = { , b, bd, bdb, bdbd}, L(A5) = { , c, cd, cdc, cdcd}. It can be observed that the following synchronizations hold: L12 = L(A1) k L(A2) = { , a, ab}, L123 = L12 k L(A3) = { , a, ab, abc, ac, acb}, L1234 = L123 k L(A4) = { , a, ab, abc, abcd, abd, acb, acbd}, L(N ) = L1234 k L(A5) = { , a, ab, abc, abcd, acb, acbd}. 4
The idea to decompose a net into atoms, compute net languages for them and then generate the net language for the initial net by incrementally synchronizing the languages of atoms gives us means to distribute the net language generation problem.
This procedure is presented in the Listing 1. Its correctness follows from the observation that synchronization is distributive, i.e., (A∪B) k C = (A k C)∪(B k C) and A k (B ∪ C) = (A k B) ∪ (A k C). Thus, to synchronize two languages we can break one of them into a collection of languages containing individual sequences and synchronize all such singletons with the second language and nally take union of the results. This observation forms the basis for how our algorithm distributes work. As the incrementally generated net language is large its subsets (partitions in Spark) can be stored on dierent nodes in the cluster and can be processed independently.
As the net languages of atoms are easy to generate and relatively small if bounded by reasonable length, we can use the broadcast mechanism available in Spark (and in Hadoop) to make them available on every node of the cluster. In that case the computation could be organized in a loop where in each step we would compute the net language of the net that is obtained from the net from the previous step by composing it with next atom. The net language of the composed net would be computed from the net language of the net from the previous step by synchronizing its every sequence as singleton net language with the net language of the composed atom.
The synchr(seq, bc.value) operation performs the synchronization {seq} k bc.value. It can be implemented by synchronizing the {seq} language with each language {s} for s ∈ bc.value and taking set union of the results. The denition of the synchronization operation is nonconstructive. We will present our method of computing synchronization in Section 6. For now let us just note that synchronization of two singleton languages can either contain no nonempty (epsilon) sequences, or contain a single nonempty sequence, or contain multiple nonempty sequences. Thus we have to repartition the RDD after each step, to equalize the sizes of subsets of the resulting sequences stored on individual nodes. This way, in the next iteration of the main loop computation will take comparable amount of time on each of the nodes. Furthermore, we also need to eliminate duplicates, def genLang(n: Net, k: Int, numPart: Int, sc: SparkContext) { val atoms = n.splitToAtoms() //split net to atoms //initialize with the language for the first atom val l = atoms.head().getLanguage(k) val res = sc.parallelize(l, numPart) //structural induction //incremental generation by synchr. with successive atom ’s languages for (nextAtom <- atoms.tail()) { l = nextAtom.getLanguage(k) var bc = sc.broadcast(l) //broadcast next atom’s language //synchr. all pairs of sequences from two languages res = res.flatMap(seq => synchr(seq, bc.value)) .map(seq => if (seq.length() > k) seq.substring(0,k)
else seq).distinct().repartition(numPart) bc.unpersist() } res.saveAsTextFile(hdfsOutputPath) //store output } Listing 1: Language generation by incremental synchronization of atom languages. which will be eciently done by Spark Spark can merge both repartitioning and duplicate elimination into one operation. 5
In the previous section we presented a method to calculate the net language of an ENS in a distributed manner. Now we introduce a technique to limit the amount of data transferred and at the same time reduce the amount of computation.
The net language consists of all possible sequences of events in a net even if they dier only by ordering of subsequent independent transitions. In this section we introduce traces which group all sequences that dier only in ordering of subsequent independent transitions. Traces allow us to represent the same information about the net as sequences but from the concurrent viewpoint as if all subsequent independent events occur simultaneously instead of considering their linearisation.
First, we formalize independence/dependence of transitions. Following [3] a dependence relation is any nite, reexive and symmetric relation. For a net N = (P, T, F ) we dene a dependence relation DN ⊆ T ×T and an independence relation IN ⊆ T × T over alphabet T based on how ring one transition aects the possibility to re another one. If ring of one transition enables or disables another transition we call them dependent. On the other hand if transitions are independent ring one of them should not immediately interfere with the ability to re the other. It is easy to see, that transitions are considered dependent, if they share a neighbouring place, otherwise they are independent. Formally, (t1, t2) ∈ DN i (•t1∪t1•)∩(•t2∪t2•) 6= ∅. Independence relation is dened as the complement of dependence relation IN = (T × T ) \ DN and we say it is induced by dependence DN . For given dependence D we mark independence induced by it as ID. Note that dependence D carries information about its alphabet which is denoted Σ(D), similarly we use Σ(I) for independence I. It is an easy check that dependence relation dened by us for a net is indeed nite, reexive and symmetric. For net N from Figure 1 we have DN = {a, b}2 ∪ {a, c}2 ∪ {b, d}2 ∪ {c, d}2, so independence induced by DN is IDN = {(b, c), (c, b), (a, d), (d, a)}.
For an alphabet A and a dependence D over A trace equivalence ≡D is dened as the least congruence in A∗ such that for all (a, b) ∈ ID ⇒ ab ≡D ba. Traces are equivalence classes of ≡D. A trace over dependence D represented by a sequence seq is denoted [seq]D. For a language of sequences L, by [L]D we denote the language of traces [L]D = {[seq]D | seq ∈ L}. Note that traces over full dependence A × A are singletons.
For a given net N , [L(N )]D is called its trace behaviour or trace language. It is important to note that trace behaviour of a net is consistent, i.e., {seq | [seq]D ∈ [L(N )]D} = L(N ). 6
Without losing any information we can store every trace as one of its representatives, i.e., one of the sequences that are in this equivalence class of the equivalence relation ≡D. The dependence relation that is needed to calculate the full net language of sequences of events from the representatives of its trace behaviour can be easily calculated by denition from the net.
Synchronization of trace languages T1 over dependence D1 and T2 over D2 is dened as the trace language T1 k T2 over D1 ∪ D2 (over the alphabet Σ(D1) ∪ Σ(D2)) such that t ∈ (T1 k T2) ⇔ πD1 (t) ∈ T1 ∧ πD2 (t) ∈ T2. Here πC (t) is the projection of trace t over dependence D onto dependence C ⊆ D, which not only can remove some symbols from the trace but also make some of them independent. Consider for example trace t = [abcd]DN = {abcd, acbd} where N is the net from Figure 1 and DN is its dependence. Take D1 = DN \ {a, c}2 and D2 = {b, d}2 ∪ {c, d}2, then πD1 (t) = {abcd, acbd, cabd} and πD2 (t) = {bcd, cbd}.
We present now a constructive method for computing synchronization of trace languages. It can be used in the algorithm in Listing 1. Later on we present how to adapt the method from net languages to trace languages and discuss how it can be implemented in an ecient way with dependence graphs.
Let us start with the observation that synchronization of singleton trace languages yields either a language consisting of one trace, being either nonempty or empty (epsilon) sequence. Therefore, for traces t1 over D1 and t2 over D2, we dene t1 k t2 to be t i {t1} k {t2} = {t}. Recall that t1 k t2 is a trace over D1 ∪ D2. Such denition allows one to compute the synchronization of trace languages as the set of all synchronizations of the pairs of the individual traces in the Cartesian product of those two trace languages: T1 k T2 = {t1 k t2 | t1 ∈ T1, t2 ∈ T2}.
We can observe that the result of this operation always contains empty (epsilon) sequence and contains any other sequences only if some traces match on the common interface Int = Σ(D1)∩Σ(D2) 1. Formally, this requirement means that for [seq1]D1 = t1 and [seq2]D2 = t2, we have πInt(seq1) = πInt(seq2). This follows immediately from the denition of synchronization.
The algorithm to construct a representative for the output trace from
matching representatives of the synchronized traces would be to divide the
synchronized representatives into subsequences delimited by interface symbols and then
interweave in any way the subsequences from the corresponding positions. Let
t1 = [k(∗,1), i1, k(
Unfortunately, it may happen that for two traces, some representatives allow for such a match but not all. For example traces t1 = [abc]D1 over D1 = {a, b}2 ∪ {b, c}2 and t2 = [cb]D2 over D2 = {(b, b), (c, c)} and common alphabet {b, c} can be synchronized. This becomes apparent if bc is chosen as the representative for t2. Next we present a constructive method that does not require us to enumerate all possible representatives to check if traces can be synchronized or not. 7
In this section we describe how synchronization of two singleton trace languages {t1} and {t2} can be implemented in an ecient way. For that we extend the dependence graphs representation from [3]. We also observe that the languages we deal with are prex closed, which allows us to further minimize the amount of memory needed to store them. The constructive synchronization we present, is designed in such a way that it results in the synchronization of the longest possible prexes, without storing them independently.
Dependence graphs are an alternative method to represent traces. They combine the partial ordering of transition occurrences common to all sequences in the dependence relation, in a form of a graph of partial ordering relation.
Formally, a dependence graph is a directed, acyclic graph that is labelled by elements of the alphabet (symbols from T ). Only nodes that represent dependent transitions are connected by an edge. Example of dependence graphs are given in the left hand side of Figure 2. They represent exactly the same information 1 Note that it is possible for a symbol to be independent of any other symbols. as [adbad]D1 k [adcead]D2 = [adbcead]D, where D1 = {a, b, d}2, D2 = {a, c, e}2 ∪ {c, d}2 and D = D1 ∪ D2.
The intuition is that the synchronization operation corresponds to combining the dependence graphs by merging the interface nodes. That is, there has to be the same number of occurrences of every interface transition, and after merging the interface transitions together we have to get a dependence graph which is directed and acyclic, i.e., the ordering dened by the synchronized dependence graphs cannot be contradictory.
As dependence relation is reexive, we extend the notation of Mazurkiewicz and enumerate successive occurrences of every transition in the trace/dependence graph. With such an indexing the occurrences of transitions are unique and the dependence graph representation is common to all representatives of a trace. We can now observe, that if dependence graphs have compatible indexing and ordering on the common interface, i.e., the order of occurrences is not contradictory and there is exactly the same number of each of the common interface transitions in both dependence graphs, then we can synchronize them by merging nodes representing the common interface (see Figure 2).
Now is the moment to observe that net languages and their trace representations are prex closed , i.e., for every sequence seq or trace [seq], all their prexes are also in the language, i.e., are sequences/traces of the same system. Thus we do not have to remember the prexes, which even further compresses our trace representation. Cleaning a huge language of prexes would be computationally intensive, especially as we do not have linear ordering of events for traces. Therefore we developed a synchronization algorithm that not only synchronizes traces (in the form of dependence graphs), but if they are not synchronizable then prex synchronizes them, i.e., it nds the synchronization of their longest synchronizable prexes. This allows us to avoid storing most of the prexes of other existing traces, while reducing the size of the representation even further. Some prexes can still appear in the representation, because it is possible that the result of prex synchronization of some traces is a prex of some other trace. We leave the elimination of this redundancy for future research.
For dependencies D1 = {a, b, c, d}2 and D2 = {a, b, e}2 with a common interface being comprised of a, b, and for traces t1 = [aacdba]D1 and t2 = [aaeaa]D2 , we have t1 k t2 = . If we consider prexes t01 = [aacd]D1 and t02 = [aae]D2 , we can synchronize them and get t01 k t02 = [aacde]D = {aacde, aaced, aaecd}.
The following steps can be used to extend the algorithm from Listing 1 to a trace version with prex synchronization. 1. Compute the common interface (this can be done once for two trace languages and reused for all the synchronized trace pairs). 2. Check if the number of occurrences of every transition from common interface is equal in both traces interfaces match. If not, for each element of the interface take the minimum of the numbers of occurrences of that element in both traces and remove the occurrences of this transition indexed above this minimum. Remove also all the successors of removed transitions. Repeat if signatures still do not match. 3. Merge the indexed dependence graphs. If there are any cycles, remove all their nodes. Remove also all descendant nodes of the removed ones. 4. The resulting dependence graph is the result of synchronization of longest synchronizable prexes. 5. From the dependence graph representation pick some representative for that trace. Use the same method of choosing representatives for all dependence graphs, i.e., make the representatives canonical. If the dependence graph has more nodes than the limit k pick all the prexes of length k and choose representatives for them.
In step 2 we nd the prexes that are suitable for synchronization by merging of dependence graphs representations. We remove nodes that cause the incompatibility of common interfaces, because the dependence graphs or traces that do not have matching interfaces are not synchronizable. We also remove all successive transitions.
A simple example shows that such a removal of nodes may have to be repeated several times. Consider D1 = {a, b, c}2∪{a, d}2, D2 = {a, b, c}2 with the common interface {a, b, c} and traces t1 = [adcb]D1 and t2 = [abbc]D2 . We have to make three steps (remove b then c then d) until we nd prexes that have matching interfaces.
These steps are presented in Figure 3. The left hand side dependence graphs are the subsequently examined prexes of t1, and on the right hand side are the prexes of t2. In the rst step, there are more occurrences of b in t2, so we remove the second one, and also remove the only node labelled c. This causes the situation, in which there is one more occurrence of c in the left hand side dependence graph. To remove it we also need to remove the only node with b. Again there is no match on the common interface {a, b, c}, so in the third step we have to remove the node with b from right hand side dependence graph. This results in prexes equivalent to traces: [ad]D1 v t1 and [a]D2 v t2, which can be synchronized.
Note that even if two traces have matching interfaces, it does not necessarily mean it is possible to synchronize them. It may be the case that their common interface from some point shows dierent orderings of transition occurrences, and the merging of dependence graphs will create cycles. Thus in step 3 we look for cycles. All cycle nodes can be eliminated from the result (with all of their successor nodes), because this corresponds to taking prexes of source operands. Note that we cannot hope to break a cycle by taking a prex in just one trace as this would prevent matching on the common interface.
Removing the same nodes from the source dependence graphs, which have been deleted during cycle removal, maintains common interface compatibility.
During synchronization only transitions that are included in the common interface are merged together, so the size of the result of synchronization can be larger than of any of the components. As we are interested in traces of limited length, we may calculate prexes of limited length. Note that trace can have more then one prex of any given length. For example, consider dependence relation D = {a, b}2 ∪ {a, c} and trace t = [abc]D. It has two prexes of length 2: [ab]D and [ac]D. This operation can be easily implemented for dependence graphs where we can iteratively drop nodes with no outgoing edges. We do not lose any information this way, because all traces of length bounded by k can be obtained by synchronization of traces of length bounded by k. We found this optimization to be protable in our experiments, but it does not have to be so in general, as it may be better to store longer traces rather than many prexes.
When choosing a representative for the trace, we make sure that for the same graph we always choose the same representative, so that if two synchronizations have the same result, we can eliminate one of them as a duplicate. 8
We conducted tests of the experimental implementation. The Petri net examples being simulated were adapted from the papers of Mazurkiewicz, together with their initial markings. Below we use the name m95 for the sole example from [3], and m84_Y where Y is a number, to indicate the example number Y from [2]. In order to get even larger nets, we multiplied them, by creating a few disjoint copies of the initial net, adding a starting place and a starting transition, which consumes the token from the starting place and inserts tokens into the places which have been originally marked in each of the copies. Figure 4 presents an example of this construction, where net m95 is three-fold multiplied to yield m95x3. Note that the disjoint copies of the initial m95 net are independent in m95x3.
The test cluster consisted of 12 machines equipped with Intel Core Quad Q9550 2,8GHz processors with 4 cores and 4 GB RAM each. Two of the machines were masters: one for Spark and one for HDFS. The other machines were used as Spark workers for distributed computation and data nodes for HDFS for the purpose of saving the nal results.
The nodes were running Java Development Kit 1.80_60, Apache Spark framework 1.4.1, and HDFS from the Hadoop 2.7.1 distribution. The Java VM was restricted to use at most 2 GB of memory.
Initially we performed several tests to choose the right number of partitions. It turned out, that in general a good choice was to use the number of partitions equal to the number of workers, i.e., 10, and enforce repartition after each task to equalize their load. However, this choice was not absolutely superior, and in some cases increasing the number of partitions to four times the number of workers, i.e., 40, was benecial.
Then we measured running time as a function of the number of places and transitions in the input net. The results are depicted in Figure 5. The general observation is that the graphs are almost linear in the logarithmic scale, so indeed the running time increases exponentially with the size of the net, if its structural complexity does not grow which in our case comes from the fact that each of the lines represents a sequence of nets, created by increasing the number of independent copies of the initial one.
Concerning the memory usage (see Figure 6), we have chosen to count data elements stored in RDDs, rather than the total memory consumption. The benet is that this gives a hint about the true sizes of the sets that emerge during computation, without taking their implementation details into account.
Those sizes vary greatly, depending on point of each step when they were measured, and to show this we represent the logs as a few separate graphs.
The curve indicated as initial represents the size of data structures at the beginning of the step. The curve described as after synchronization provides the size of data structures after the traces are synchronized, yet those traces can still be longer than the requested limit. Next, we calculate prexes of limited length which can increase the data size and is presented as curve described as after prexes . Finally, duplicates are removed by executing distinct, which eliminates the obvious redundant data elements and produces the initial data for the next step.
The peaks on the graphs generally occur when many duplicates emerge. This is caused by the structural properties of the nets being simulated.
Finally, we present a graph, depicting how the optimizations we perform (elimination of prexes and replacing sequences with traces) inuence the size of the resulting sets of objects, which represent the complete set of runs of the system. We have the following four cases: (A) is the unoptimized case, (B) is the case of all sequences of length up to k (with proper prexes eliminated), (C) is the case of all traces of length up to k (stored by using only one representative) and (D) of all traces of length k, without proper prexes, i.e., with both optimizations used simultaneously.
In order to visualize the situation, we repeated the experiments for all four possible cases (A), (B), (C) and (D) for the following 15 nets 2: m84_0, m84_0x2, m84_0x3, m84_1, m84_1x2, m84_1x3, m84_2, m84_2x2, m84_2x3, m84_3, m84_3x2, m84_3x3, m95, m95x2, m95x3, and for the length limits k = 5, 7 and 10.
Since we had many nets of dierent sizes, we normalized the results by calculating, for each net and each k separately, the ratios of (D), (C), (B) and (A) to 2 Recall that m84_2x3 is the second example from [2] multiplied three times. (A), getting the ratio of size reduction in each case. Then we computed averages of the ratios over all nets. As it is now apparent from the graph in Figure 7, representing behaviours in the form of traces reduces the sizes of the datasets much more than eliminating prexes. It is also visible that the larger k we have, the better the eect of moving from sequences to traces. Eliminating prexes alone gives a constant rate of size reduction, independent of k.
Our research demonstrates a successful attempt to treat the investigation of the
runs of a PN as a Big Data problem. Our contributions are the following: (
Our approach permits further improvements. An extra step could be added to the algorithm to remove all prexes which would require developing specialized algorithm for that and testing if the extra eort is protable. Note that for traces which do not represent linear ordering of events this may not be as straightforward as for sequences. In the case that the simulated net contains several copies of a certain subnet, we plan to reuse the trace language computed for one copy while processing other copies, instead of recomputing it from scratch. We intend to automatize detection of opportunities for such reuse.