Petri Net
A mathematical modeling language for distributed systems that uses places, transitions, and tokens to represent concurrent processes and resource flow.
Also known as: Petri Nets, Place/Transition Net, P/T Net
Category: Software Development
Tags: computer-science, modeling, concurrency, systems, formal-methods, distributed-systems
Explanation
A Petri net is a mathematical modeling language for the description of distributed systems, invented by Carl Adam Petri in 1962. It is a directed bipartite graph that excels at modeling concurrent, asynchronous, distributed, parallel, nondeterministic, or stochastic systems. Where ordinary state machines model a single thread of control, Petri nets natively express multiple simultaneous activities and the synchronization between them.
## Core Elements
- **Places**: Represented as circles, places hold tokens and typically denote conditions, resources, or buffers
- **Transitions**: Represented as bars or boxes, transitions are the events that may occur (firing)
- **Arcs**: Directed edges connecting places to transitions or transitions to places — never place-to-place or transition-to-transition
- **Tokens**: Markers that occupy places and represent the dynamic state of the net (the marking)
## Firing Rules
A transition is **enabled** when each input place holds at least as many tokens as the weight of the connecting arc. When an enabled transition **fires**, it removes tokens from input places and deposits tokens in output places. Multiple transitions may be enabled simultaneously, and the choice of which to fire is non-deterministic — this is what gives Petri nets their power for modeling concurrency.
## Variants and Extensions
- **Place/Transition nets**: The classical untyped form
- **Colored Petri nets (CPN)**: Tokens carry data values, allowing compact representation of complex systems
- **Timed Petri nets**: Transitions have associated delays for performance modeling
- **Stochastic Petri nets**: Transition firing follows probability distributions
- **Hierarchical Petri nets**: Subnets can be nested for scalability
## Applications
- **Workflow modeling**: Business processes, especially those with parallel branches and synchronization
- **Manufacturing systems**: Production lines, resource allocation, just-in-time scheduling
- **Communication protocols**: Modeling message passing and synchronization
- **Distributed computing**: Race conditions, deadlock analysis, liveness verification
- **Software engineering**: Concurrent program verification, embedded systems
- **Biology**: Metabolic pathways, gene regulatory networks
## Why Petri Nets Matter
Petri nets provide both a visual diagrammatic notation and a rigorous mathematical foundation. Properties like reachability, boundedness, liveness, and deadlock-freedom can be analyzed formally. They are particularly valuable when you need to reason about systems where multiple things happen at once and where synchronization, resource sharing, or mutual exclusion matters — situations that simple state machines cannot express compactly.
Related Concepts
← Back to all concepts