For the most recent entries see the Petri Nets Newsletter.

Stochastic Marked Graphs.

Rajsbaum, Sergio

In: Proc. 4th Int. Workshop on Petri Nets and Performance Models (PNPM'91), Melbourne, Australia, pages 95-105. IEEE Comp. Soc. Press, December 1991.

Abstract: Stochastic Marked Graphs (SMG's) are marked graphs in which transmission delays of tokens, and firing durations are random variables. A technique is presented to study the performance of SMG's. The main performance measure is the rate of computation, i.e., the average number of firings of a vertex, per time unit. The effect of the topology and the probability of the random variables on the rate is investigated. For deterministic random variables, the rate is maximized, while for exponential random variables the rate is minimized (among a natural class of distributions). For random variables with exponential distribution several bounds on the rate are provided. The bounds depend on the degree of the vertices and on the average number of tokens in a cycle, but not on the number of vertices itself. In particular, it is shown that the rate is at least the optimal (deterministic) rate, divided by a logarithmic factor of the vertex degrees. Thus, for some graphs the rate does not deminishes below a bound, regardless of the number of vertices.


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography