Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Petri Nets!Definitions–Source Transition: a transition without any input place»is unconditionally enabled–Sink Transition: a transition without any output place»consumes but does not create any tokens–Self-Look: P is both an input and output place of T –Pure Petri Net: does not contain self-loops–Ordinary Petri Net: all of the arc weights are unity, i.e. one.–Infinite Capacity Net: assumes that each place can accommodate an unlimited number of tokens–Finite Capacity Net: max. token-capacity K(P) defined for each P–Strict Transition Rule: finite capacity net with additional rule that the number of tokens in each output place P of T cannot exceed its capacity K(P) after firing T.1Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Petri Nets!Modeling Constructs–Concurrency–Precendence–Conflict, choice or decision»function: “exclusive OR”»only one transition can fire»weight: probability of taking that arc...0.10.9...par begin par end2Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Petri Nets!Modeling Constructs–Synchronization»AND»joining several paths into a single path...3Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Example4Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Example5Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Petri Nets!Modeling Constructs–Time»need new concept => timed transition»timed transition has firing delay T»when transition is enabled, wait T, then fire"tokens are consumed and created at the firing instance»timed Petri Net symbol!Stochastic Petri Net–T is not fixed–T = random variable with exponential distributionT6Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Petri Nets!Generalized Stochastic Petri Nets (GSPN)Adds extra constructs–Mixed transitions»stochastic and instantaneous transitions–Multiple Arcs»needs 2 tokens to fire2same as7Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Petri Nets!Generalized Stochastic Petri Nets (cont.)–Inhibitory Arcs»token inhibits firing»obviously no token transfer»watch for deadlocks!–Multiple Inhibitory Arcs»needs at least N tokens to inhibit firing»less than N tokens => transition is firableN8Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Petri Nets!Reachability–fundamental basis for studying the dynamic properties of any system–firing of enabled transition will change token distribution–sequence of firings results in sequence of markings–marking Mn is reachable from M0 if there exists a sequence of firings that transforms M0 into Mn –firing sequence is denoted by »! = M0 t1 M1 t2 … tn or simply ! = t1 t2 … tn»in this case Mn is reachable from M0 by !–the set of all possible markings reachable from M0 in a net (N,M0) is denoted by R(N,M0) or simply R(M0)–the set of all possible firing sequences from M0 in a net (N,M0) is denoted by L(N,M0) or simply L(M0)9Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Petri Nets!Reachability Graph–Petri Net with initial marking –Reachability Graph»add transitions to graph and…»Markov chainm1 "p1p22""2.01.10.22.01.10.210Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Petri Nets!Reachability Graph–Petri Net with initial marking –Reachability Graphp1p31.1.00.1.10.0.2p21.0.111Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Petri Nets!Boundedness–A Petri net (N,M0) is said to be k-bounded (or simply bounded) if the number of tokens in each place does not exceed a finite number k of any marking reachable from M0 , i.e., M(p) ! k for every place p and every marking M# R(M0)–example of 2-bound net12Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Petri Nets!Liveness–closely related to the complete absence of deadlock in OS–A Petri net (N,M0) is said to be live (or equivalently M0 is said to be a live marking of N) if, no matter what marking has been reached from M0 , it is possible to ultimately fire any transition of the net by progressing through some further firing sequence.A live Petri net guaranteesdeadlock-free operation, no matter what firing sequence is chosen.However, this property is costly to verify, e.g. for large systems.13Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Petri Nets!How did we get the net of the candy machine? –identify places needed0510201514Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Petri Nets!Example: candy machine–identify paths from places to places and the events that get you there (interpret the numbers as “deposit x cents”. get 20c candy1505102015510101055 5get 15c candyPage: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Petri Nets!Example: candy machine–transition events: “deposit x cents”1605102015510101055 5get 15c candyget 20c candyPage: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12Petri Nets!Example: candy machine–final Petri net17Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12GSPN!gspn model name (opt. param. list)–1. List all places and initial marking»place-name expr for init num of tokens–2. List all timed trans. and rates»trans-name ind expr for rate»trans-name dep place-name expr for base rate–3. List instant. trans. and branch weights»trans-name ind expr for weight»trans-name dep place-name expr for base weight–4. List all place to trans. arcs»place-name trans-name expr for mult.–5. List all trans. to place arcs»trans-name place-name expr for mult.–6. List all inhibitory arcs(See language description)18Page: © 2011 A.W. Krings CS449/549 Fault-Tolerant Systems Sequence 12GSPN!Some general notes–Recall: reachability graph is Markov.–Most functions compute CDF of “time to absorption” in reachability graph.–Must ensure net is “dead" at desired point, e.g.:»when 1st token enters “Failure" place,»when exactly k-of-N nodes are faulty,»when exactly k-of-N nodes are still up,–Need Inhibitory arcs from “Failure” back to all timed transitions.»Causes net to become dead at instant of failure.»Otherwise absorption could occur well after