Abstract
In a live and bounded Free Choice Petri net, pick a non-conflicting transition. Then there exists a unique reachable marking in which no transition is enabled except the selected one. For a routed live and bounded Free Choice net, this property is true for any transition of the net. Consider now a live and bounded stochastic routed Free Choice net, and assume that the routings and the firing times are independent and identically distributed. Using the above results, we prove the existence of asymptotic firing throughputs for all transitions in the net. Furthermore the vector of the throughputs at the different transitions is explicitly computable up to a multiplicative constant.
Introduction
In the study of distributed systems, Petri nets serve as a foundational tool for modeling how resources (tokens) move through actions (transitions). However, predicting the performance—specifically the throughput—of these systems is notoriously difficult once simple mathematical assumptions are relaxed.
In their research, Gaujal, Haar, and Mairesse uncover a structural property of Free Choice Petri nets (FCNs) that simplifies performance analysis. They demonstrate that blocking a single transition in a live and bounded FCN eventually forces the entire system into a unique, predictable "blocking marking." This result allows for the proof of asymptotic firing throughputs in stochastic systems with general (non-exponential) firing times.
Problem Statement
Performance evaluation in Petri nets often relies on Markovian assumptions, where firing times follow exponential distributions. This rarely reflects reality in fields like manufacturing or networking. The challenge addressed here is whether a system reaches a stable throughput under general, independent, and identically distributed (i.i.d.) firing times, and whether these rates can be calculated without knowing the exact shape of the time distributions.
Methods
The authors approach the problem in three logical stages:
- Structural Analysis of Untimed Nets: They prove that "blocking" a non-conflicting transition (one whose input places have no other output transitions) leads the net to a unique state where no other transitions can fire, termed the blocking marking.
- Introduction of Routing: To resolve conflicts where a token has multiple potential paths, they introduce routed Petri nets, where each place with multiple outputs has a predefined function to decide token flow.
- Stochastic Modeling: Using the monotone-separable framework from queuing theory, they treat the system as a series of completion instants to prove convergence to a steady state.
Key Insights and Ideas
A central insight is that the blocking marking $M_b$ acts as a "home state" reachable from any other state in the net. This provides a regeneration point that resets the system's memory, which is essential for proving stability in stochastic processes.
Furthermore, the authors discovered that the ratio of throughputs between any two transitions depends solely on the routing probabilities, independent of the specific firing time distributions. The "Free Choice" property is shown to be necessary for this uniqueness; without it, the stability of the blocking marking collapses.
Key Results
The research establishes that for any transition $b$ in a live, bounded, stochastic routed FCN, the limit $\lim_{t \to \infty} X_b(t)/t = \gamma_b$ exists almost surely. The vector of throughputs $\lambda$ can be computed as the left eigenvector of a routing matrix $R$ associated with the eigenvalue 1. This allows relative firing rates to be calculated using standard linear algebra (Perron-Frobenius theory).
Additionally, the authors provide a cubic-time algorithm $O(mT^3)$ to compute the blocking marking, making the approach computationally feasible for practical network sizes.
Limitations and Future Work
While the framework robustly determines relative throughputs, calculating the absolute throughput (the exact multiplicative constant) remains difficult for general firing time distributions. The authors note that this constant is hard to approximate even in simpler T-nets. Future research may explore extensions to stationary and ergodic assumptions to address the integrability of regeneration times in more general cases.
Summary updated