Package jline.api.spn

Class Spn_conv

java.lang.Object
jline.api.spn.Spn_conv
public class Spn_conv extends Object
Convolution algorithm for the normalising constant of an S-invariant reachable product-form stochastic Petri net.

J. Coleman, W. Henderson, P. Taylor, "Product form equilibrium distributions and a convolution algorithm for stochastic Petri nets", Performance Evaluation 26(3), 1996, 159-180; presented as the point of comparison for MDD-rec in S. Balsamo, A. Marin, I. Stojic, FGCS 111 (2020), Sec. 5.1.

With S the minimal-support S-invariant matrix and V = S m0 the load vector, the reachability set of an S-INVARIANT REACHABLE net is exactly {m >= 0 : S m = V}, and conditioning on the marking of one place partitions it (Lemma 5.1). Writing G_j(W) for the mass of the markings supported on the first j places with S m = W,

   G_0(W) = [W == 0],     G_j(W) = sum_i g_j(i) G_{j-1}(W - i S_j),

and G = G_n(V). On a net whose only invariant is "the tokens are conserved" this is Buzen's convolution for a closed queueing network, one place per station.

NO ILP IS SOLVED. The paper obtains the marking set M_p(P',W) from the feasibility of an integer program (Prop. 5.2) so that the sum skips the terms that contribute nothing. Here the sum simply runs over i whose residual W - i S_j stays non-negative and the recursion returns zero on an infeasible residual, which gives the same value: the ILP is an optimisation of the enumeration, not part of the definition. Memoising on (j, W) keeps the walk over the reachable residuals rather than over all of them.

S-INVARIANT REACHABILITY IS NOT CHECKED, and cannot be cheaply: no algorithm is known that decides it without generating the reachability set (FGCS, Sec. 5.1). On a net that fails it, {m : S m = V} is strictly larger than the reachable set and this returns a normalising constant over unreachable markings too, which is why Mdd_rec.mdd_rec -- which walks the reachable set itself -- is the general algorithm and this one the special case. Compare the two on a new net before trusting this one on it.

MATLAB twin: spn_conv.m. Python twin: api/spn/conv.py.

  • Method Details

    • spn_conv

      public static double spn_conv(Spn_sinvariants.SpnInvariants inv, double[][] g)
      Convolve straight off the invariant basis Spn_sinvariants returned.

    • spn_conv

      public static double spn_conv(long[][] S, long[] V, double[][] g)
      The normalising constant by convolution over the invariant load vector.
      Parameters:
      S - S[i][p], the minimal-support S-invariants, one row per invariant
      V - the load vector S m0, one entry per invariant
      g - g[p][i] is g_p(i), the product-form factor of i tokens in place level p; its length bounds the marking of that level
      Returns:
      the normalising constant