A discrete event model generatorYannick Pencolé |
This tutorial illustrates the way to randomly generate a discrete event system.
It is possible to randomly generate a global model (i.e. a single automaton) with the help of the command dd-des-generate.
Usage: dd-des-generate --help | [--topo topologyFileName.topo] [--seed randomSeed] [--evtMin nbEvtMin] [--evtMax nbEvtMax] [--obsMin nbObsMin] [--obsMax nbObsMax] [--stateMin nbStateMin] [--stateMax nbStateMax] [--latex latexFileName] [--outputdir dirName] [--obsInteractionMin nbObsIntMin] [--obsInteractionMax nbObsIntMax] [--nodeBehaviour node=file.descomp ci=ej ck=el ...]] [--outputDegreeMax outDeg]
The command dd-des-generate randomly generates a distributed discrete-event system that has the topology defined in the file topologyFileName.topo. The generator uses a random generator of number that can be initialised with the seed randomSeed. If not provided, the seed is the starting time of each run of the program. As far as the behaviour of a component is concerned, the number of generated states is between nbStateMin and nbStateMax. The number of event is between nbEvtMin and nbEvtMax as long as it is compatible with the topology. The number of observable events is between nbObsMin and nbObsMax. The generated model consists of a set of files written in the directory dirName. The model generator also generates a document in latex format for documentation purposes (if the option is set). The parameters --obsInteractionMin and --obsInteractionMax states the possible numbers of observable interactions. The --nodeBehaviour parameters states that one (and only one) of the node called node has the predefined behaviour described in file.descomp. Constraints like ci=sj assert that the component ’node’ implements the connection ci of the topology with the iteractive event sj. The option --outputDegreeMax rules the maximal number of transitions (i.e. events) that are the output of one state.
In this section, the generated model is monolithic (no topology provided):
dd-des-generate --evtMin 400 --evtMax 400 --obsMin 350 --obsMax 350 --stateMin 3000 --stateMax 3000 --outputDegreeMax 3
In this example, the system contains 3000 states and 400 event types. Among the 400 events, 350 are observable. Each state maximally contains between 1 and 3 output transitions. It creates a file n0.des_comp in the default directory model_generator_directory. To get information about the generated model you can run dd-component-info as follows:
dd-component-info n0.des_comp --events
dd-component-info n0.des_comp --events_number
dd-component-info n0.des_comp --states
To randomly generate a system that is defined as a set of components that interact with each other, the generation is a two-stage process:
The generation of the topology is performed with the following command: dd-generate-topology
Usage: dd-generate-topology
[--nodes nbNode]
[--connectivity nbConn]
[--commonConnectionMax nbConn]
[--cliqueSizeMax cliqueSize]
[--seed randomSeed]
[--output fileName]
This command generates a topology of nbNode nodes (default = 3). A connection between a set of nodes corresponds to a set of synchronised events between the nodes. Any node is directly or indirectly connected to the other nodes. The connectivity of a node is the set of connections in which the node is involved (default = 2). The parameter connectivity sets the maximal number of connections that a node can have. A connection involves a set of nodes (that is then called a clique). cliqueSizeMax sets the maximal size of a clique (default = 2). Two nodes may have several connections in common, commonConnectionMax sets the maximal number of connections involving two components (default = 2). The generation is random and require a seed (default = depends on the time). Two runs with the same seed and parameters generate the same topology. The topology is then saved in the fileName (default = generatedTopology+Params.topo).
dd-generate-topology-static --nodes 10 --connectivity 4
--output mytopology.topo
This command generates a topology containing 10 nodes (i.e. 10 components) with a connectivity up to 4 (a node can interact with 4 other components maximum). The result of generation is stored in the text file mytopology.topo. By running the previous command, we can get a topology like the following one (content of mytopology.topo):
p top 10 12 c21: n4, n7; c20: n7, n9; c10: n0, n8; c11: n6, n8; c12: n5, n8; c13: n0, n9; c14: n0, n4; c15: n6, n7; c16: n0, n2; c17: n1, n4; c18: n1, n3; c19: n8, n9;
The file starts with p top and gives the number of components (10) and the number of connections (12). Then it consists of a list of connections. The connection c21 connects n4 and n7, etc. It is possible to visualize the topology with the help of the graphviz/dot program, as follows:
dd-topology2dot mytopology.topo dot -Tpng -o mytopology.topo.png mytopology.topo.dot
You will get the following figure in mytopology.topo.png.
Once a topology is defined, it is now possible to generate the behaviours (the automata), each automaton is associated to one node, and a set of synchronisation rules along these components that are compatible with the topology. Note that the generation of a topology is independent from the generation of the behaviours. It is perfectly possible to design a topology by hand (and not by using the topology generator) as long as it is written in a file with the format of the topology text file.
To perform this generation, we still use the command introduced in section 1, that is:dd-des-generate.
The main difference with the first use of this command is that now we put as a parameter the provided topology. For instance,
dd-des-generate --stateMin 3 --stateMax 6
--evtMax 20 --topo mytopology.topo
With this command, we ask the generator to generate 10 components (as there are 10 nodes in the given topology). For each of them, we asked that the generator creates an automaton containing between 3 and 6 states. The overall number of events must not be over 20. The run of this command results in the generation of 12 files, namely:
The file sync.rules defines the synchronisation law. This file is important as it defines the way the components are generated. Below is the content of the file generated by the previous example.
components: n2, n5, n3, n6, n1, n8, n0, n9, n7, n4; rules: <n9.s17, n8.s10>; <n1.s6, n3.s2>; <n4.s21, n7.s18>; <n4.s22, n0.s13>; <n7.s19, n9.s15>; <n0.s11, n8.s7>; <n4.s23, n1.s5>; <n8.s8, n6.s3>; <n8.s9, n5.s1>; <n9.s16, n0.s12>; <n7.s20, n6.s4>; <n0.s14, n2.s0>;
The first line starts with the keyword components: and lists the set of components (here n0 to n9). The second line starts the definition of the synchronisation law with the keyword rules:. Finally, the file lists the synchronisation rules. Each line defines a rule, the first one <n9.s17, n8.s10> declares that the event s17 from the component n9 is synchronised with event s10 from node n8, etc. Note that a synchronisation rule may list more than 2 events, it is totally possible to define a rule like this: <n9.s17, n8.s10,n4.s23, n1.s5> which states that the four events are synchronised.
The last file that is generated is topology.maptopo. This file is for information only as it is not used by any diades command. It describes how the synchronisation rules are mapped with the connection of the topology. In the following example, we can see that the synchronisation rule <n9.s17, n8.s10> that is detailed above is actually mapped to the connection c19 of the topology.
p maptop 12 c19: n9.s17, n8.s10; c18: n1.s6, n3.s2; c21: n4.s21, n7.s18; c14: n4.s22, n0.s13; c20: n7.s19, n9.s15; c10: n0.s11, n8.s7; c17: n4.s23, n1.s5; c11: n8.s8, n6.s3; c12: n8.s9, n5.s1; c13: n9.s16, n0.s12; c15: n7.s20, n6.s4; c16: n0.s14, n2.s0; ;
The result of dd-des-generate on a given topology guarantees by construction1 that the set of generated components are globally consistent, that is there exists a single automaton that is not empty and that results from the synchronisation of the components and any transition of any component is triggered at least once in the global model.
For instance, to build the complete global model as a single automaton here,
dd-global-model n0.des_comp n1.des_comp n2.des_comp n3.des_comp
n4.des_comp n5.des_comp n6.des_comp n7.des_comp
n8.des_comp n9.des_comp sync.rules
It computes the global model in the file n0_n1_n2_n3_n4_n5_n6_n7_n8_n9.des_comp. Be aware that the size of the global model is exponential to the number of components so this computation is very expensive and most of the time untracktable. To see the size of the result, you can run:
dd-component-info n0_n1_n2_n3_n4_n5_n6_n7_n8_n9.des_comp --statistics
and you will get:
# component name: n0_n1_n2_n3_n4_n5_n6_n7_n8_n9 # number of states: 82944 # number of transitions: 3431808 # ratio transitions/states: 41.375
Got the full story? Try and enjoy yourself.
This document was translated from LATEX by HEVEA.