Package jline.api.mdd

Class Mdd_rec

java.lang.Object
jline.api.mdd.Mdd_rec
public class Mdd_rec extends Object
MDD-rec: the normalising constant of a product-form model whose reachable set is held in a decision diagram.

S. Balsamo, A. Marin, I. Stojic, "Computation of the normalising constant for product-form models of distributed systems with synchronisation", Future Generation Computer Systems 111 (2020) 475-490, Sec. 4.

A product-form model has P(s) = (1/G) prod_k g_k(s_k) over its levels, and G = sum_{s in S} prod_k g_k(s_k). Summing state by state is exponential and numerically unstable. MDD-rec instead walks the diagram that already encodes S, accumulating the unnormalised mass of each node ONCE (Def. 4.4, Algorithm 1):

   M(<l.p>) = sum_{v in S_l} g_l(v) * M(<l.p>[v]),  M(TRUE)=1, M(FALSE)=0

so the cost is O(sum_l |nodes_l| * |S_l|) rather than O(|S|), and G = M(root).

FORMALISM-AGNOSTIC. Nothing here knows what a level is: the paper's Appendix B shows that on the lattice sum_k s_k = n of a closed queueing network this collapses to Buzen's convolution, and Sec. 5 that on an S-invariant reachable Petri net it collapses to the Coleman-Henderson-Taylor convolution (Spn_conv). Unlike either, it needs only that the reachable set be finite and encoded -- no lattice, no S-invariant reachability.

THE MASK is how Sec. 5.3 computes measures. Restricting the sum at level l to a subset of its local values gives the unnormalised mass of the corresponding subset of S, so P(m_l = k) and P(e_j >= k) are the same recursion under a different mask rather than three separate algorithms.

WHAT IS NOT HERE. The g_l themselves, and the test that the model has a product form at all, are the caller's: the paper declares that out of scope (Sec. 3.2). Passing g_l that do not describe a product-form model returns a number that is not the normalising constant of anything, and nothing here can detect it.

MATLAB twin: mdd_rec.m. Python twin: api/mdd/rec.py.

  • Method Details

    • mdd_rec_masked

      public static double mdd_rec_masked(MddStruct mdds, double[][] g, boolean[][] mask)
      Unnormalised mass of the masked subset of the reachable set (Algorithm 1).
      Parameters:
      mdds - the reachable set, in MDD orientation (level 0 is the root)
      g - g[l][v] is g_l(v), the per-level factor of the product form
      mask - per-level admissible values; null admits everything and returns the normalising constant G
      Returns:
      the unnormalised mass of the masked subset

    • mdd_rec

      public static double mdd_rec(MddStruct mdds, double[][] g)
      The normalising constant G = sum_{s in S} prod_l g_l(s_l).

    • mdd_rec_marginal

      public static double[] mdd_rec_marginal(MddStruct mdds, double[][] g, int l)
      Unnormalised masses of {s in S : s_l = k}, one per local value k of level l.

      Divided by G these are P(m_l = k) of Sec. 5.3: the mean occupancy of a level is sum_k k * P(m_l = k), and its utilization 1 - P(m_l = 0).

      Parameters:
      mdds - the reachable set
      g - per-level product-form factors
      l - level index, 0-based
      Returns:
      one unnormalised mass per local value of level l