Petri Nets 1 Definition of Petri Net C P T I O Places P p1 p2 p3 pn Transitions T t1 t2 t3 tn Input I T Pr r number of places Output O T Pq q number of places marking assignment of tokens to the places of Petri net 1 2 3 n 2 Applications of Petri Net Petri net is primarily used for studying the dynamic concurrent behavior of network based systems where there is a discrete flow Petri Nets are applied in practice by industry academia and other places reference 3 Basics of Petri Nets Petri net consist two types of nodes places and transitions And arc exists only from a place to a transition or from a transition to a place A place may have zero or more tokens Graphically places transitions arcs and tokens are represented respectively by circles bars arrows and dots p1 t1 p2 4 Basics of Petri Nets continued Below is an example Petri net with two places and one transaction Transition node is ready to fire if and only if there is at least one token at each of its input places p1 t1 p2 state transition of form 1 0 0 1 p1 input place p2 output place 5 Properties of Petri Nets Sequential Execution Transition t2 can fire only after the firing of t1 This impose the precedence of constraints t2 after t1 t1 p2 t2 p3 Synchronization Transition t1 will be enabled only when a token there are at least one token at each of its input places p1 t1 Merging Happens when tokens from several places arrive for service at the same transition 6 Properties of Petri Nets continued Concurrency t1 and t2 are concurrent with this property Petri net is able to model systems of distributed control with multiple processes executing concurrently in time t1 t2 7 Properties of Petri Nets continued Conflict t1 and t2 are both ready to fire but the firing of any leads to the disabling of the other transitions t1 t2 t1 t2 8 Properties of Petri Nets continued Conflict continued the resulting conflict may be resolved in a purely non deterministic way or in a probabilistic way by assigning appropriate probabilities to the conflicting transitions there is a choice of either t1 and t2 or t3 and t4 t1 t2 t3 t4 9 Example In a Restaurant A Petri Net Waiter free Customer 1 Customer 2 Take order Take order wait eating Serve food Order taken Tell kitchen wait eating Serve food 10 Example In a Restaurant Two Scenarios Scenario 1 Waiter takes order from customer 1 serves customer 1 takes order from customer 2 serves customer 2 Scenario 2 Waiter takes order from customer 1 takes order from customer 2 serves customer 2 serves customer 1 11 Example In a Restaurant Scenario 1 Waiter free Customer 1 Customer 2 Take order Take order wait eating Serve food Order taken Tell kitchen wait eating Serve food 12 Example In a Restaurant Scenario 2 Waiter free Customer 1 Customer 2 Take order Take order wait eating Serve food Order taken Tell kitchen wait eating Serve food 13 Example Vending Machine A Petri net Take 15c bar Deposit 10c 5c 15c Deposit 5c 0c Deposit 5c Deposit 10c 10c Deposit 5c Deposit 5c 20c Deposit 10c Take 20c bar 14 Example Vending Machine 3 Scenarios Scenario 1 Deposit 5c deposit 5c deposit 5c deposit 5c take 20c snack bar Scenario 2 Deposit 10c deposit 5c take 15c snack bar Scenario 3 Deposit 5c deposit 10c deposit 5c take 20c snack bar 15 Example Vending Machine Token Games Take 15c bar Deposit 10c 5c 15c Deposit 5c 0c Deposit 5c Deposit 10c 10c Deposit 5c Deposit 5c 20c Deposit 10c Take 20c bar 16 Petri Net with Time 1962 Carl Adam Petri originally proposed Petri without any notion of time Concept of time was intentionally avoided because addition of time restricts the behavior of the net 1970s Addition of time has been discussed in order to analyze the performance of the modeled system Many properties are still undecided for Petri nets extended with data and time 17 References Fishwick Paul 1995 Simulation Model Design and Execution Petri Nets World Ling Chris 2001 Lecture on Petri Nets Method Chapman Nick 1997 Surprise97 journal on Petri Nets Models 18