{"id":522,"date":"2007-10-01T20:11:40","date_gmt":"2007-10-01T20:11:40","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/10\/01\/modeling-concurrency-with-graphs-petri-nets\/"},"modified":"2007-10-01T20:11:40","modified_gmt":"2007-10-01T20:11:40","slug":"modeling-concurrency-with-graphs-petri-nets","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/10\/01\/modeling-concurrency-with-graphs-petri-nets\/","title":{"rendered":"Modeling Concurrency with Graphs: Petri Nets"},"content":{"rendered":"

Among many of the fascinating things that we computer scientists do with graphs
\nis use them as a visual representation of computing devices. There are many subtle problems that can come up in all sorts of contexts where being able to see<\/em> what’s going on can make a huge difference. Graphs are, generally, the preferred metaphor for most computing tasks. For example, think of finite state machines, flowcharts, UML diagrams, etc.<\/p>\n

One of the most interesting cases of this for one of the biggest programming problems today is visual representations of concurrency. Concurrent program is incredibly hard, and making a concurrency regime correct is a serious challenge – communicating that regime and its properties to another developer is even harder.<\/p>\n

Which brings us to todays topic, Petri nets. Actually, I’m probably going to spend a couple of days writing about Petri nets, because they’re fun, and there are a lot of interesting variations. The use of Petri nets really isn’t just an academic exercise – they are seriously used by people in a lot of real, significant fields – for one example, they’re very commonly used to specify behaviors of network communication protocols.<\/p>\n

<\/p>\n

Today, I’m going to introduce the simplest version of a Petri net – the basic, simple, Petri net. A Petri net is a bipartite, weighted digraph used as a representation of concurrent computation – in particular, the coordination aspects of multi-threaded computations. The two sets of nodes in a PetriNet are called places<\/em> (drawn as circles or ovals) and transitions<\/em> (drawn as narrow rectangles). Since it’s a bipartite graph, there are edges from places to transitions; and transitions to places, but never places to places or transitions to transitions. So for example, the below is a petri-net. <\/p>\n

\"petri-ex.png\"<\/p>\n

Places are containers for tokens, which are inputs or results of computations. An edge carries tokens from a place to a transition, or a transition to a place. Transitions represent computations<\/em> which can occur. The computation associated with a transition is not explicitly represented in the
\nnet – the net only models concurrency and coordination.<\/p>\n

In addition to the basic Petri-net graph, there is a marking<\/em>, which assigns a number of tokens<\/em> to each place in the graph. The marking represents the current state<\/em> of a computation in the net. Given a list of places [p1<\/sub>, …, pn<\/sub>], you can represent
\na marking of a Petri net using an integer vector, where each position contains the number of tokens in the corresponding place.<\/p>\n

The way that a petri-net operates is by firing transitions<\/em>. Each step, the net non-deterministically<\/em> selects and fires an enabled transition. A transition is enabled when all<\/em> of the places that have edges to it have a number of tokens greater than or equal to<\/em> the weight of their edge. So in our example, transition “y” can fire when place “d” has at least 2 tokens, and “e” has at least 1 token.<\/p>\n

When a transition fires, for each incoming edge, it removes the edge’s weight in tokens from the edges source place; and for each outgoing edge, it adds<\/em> the edges weight in tokens to the target place. So, in our example, if “d” has 3 tokens, “e” had 4 tokens, “g” had 1 token, we could fire “y”, which would leave “d” with 1 token, “e” with 3 tokens, and “g” with 3 tokens. There’s no necessary relation between
\nthe number of tokens that come in to the transition and the number of tokens that are output by the transition.<\/p>\n

\"branch-and-join-petri.png\"<\/p>\n

For an extremely simple example of how Petri nets are used, look at the example to the right, which illustrates a common model of concurrency, called fork-join<\/em>. In a fork-join computation, you have one primary thread, which creates other threads that execute in parallel. Then at the end, the main thread stops and waits until the other threads are finished before it proceeds. In our fork-join Petri-net, all of the edges have weight 1, and I’ve color-coded the places for the three threads. The green places are the original main thread. The main thread first forks off the red thread; then it forks off the blue thread. Then each of the thread goes off and does its own computation (the color-coded transitions), and then all meet up at the bottom, black transition.<\/p>\n

\"petri-transition-one.png\"<\/p>\n

The computation starts off with a marking with one token in “Start”, and no tokens anywhere else. Since the one transition adjacent to start is the only selected transition, it fires, which removes the token from start, and puts one token each in places a and f. Then it has a choice – it can fire either the red-thread transition from f, or the green thread transition from a. If it fires the green, then there will be one token each in b, d, and f, as shown in the diagram. <\/p>\n

\"petri-almost-done.png\"<\/p>\n

After that, It will continue firing transitions, until it reaches the marking shown below, where, there’s a token in each of c, e, and g. No matter what transitions it fires, no matter what order it fires them in, it must eventually wind up in this state. This fires the last transition, and then the only token is in “End”. Once that happens, there are no more selected transitions, and since there are no selected transitions, the computation is over.<\/p>\n","protected":false},"excerpt":{"rendered":"

Among many of the fascinating things that we computer scientists do with graphs is use them as a visual representation of computing devices. There are many subtle problems that can come up in all sorts of contexts where being able to see what’s going on can make a huge difference. Graphs are, generally, the preferred […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[79,25],"tags":[],"class_list":["post-522","post","type-post","status-publish","format-standard","hentry","category-computation","category-graph-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-8q","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/522","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=522"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/522\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=522"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=522"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=522"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}