Package jline.api.fj

Class FJ_ordstat_exp

java.lang.Object
jline.api.fj.FJ_ordstat_exp
public class FJ_ordstat_exp extends Object
Mean of the k-th smallest of n independent EXPONENTIAL branch completion times, i.e. the instant a k-of-n (quorum) join fires. k = n is the ordinary AND-join, the maximum, and k = 1 the minimum.

With lambda_i = 1/ri(i) and m = n-k stragglers allowed,

   E[X_(k)] = sum_{j=m+1..n} (-1)^(j-m-1) C(j-1,m) e_j,
   e_j      = sum_{|S|=j} 1 / sum_{i in S} lambda_i

the inclusion-exclusion identity for the order statistics of independent exponentials. At m = 0 it collapses to sum_j (-1)^(j-1) e_j, the classical expression for the maximum, TERM BY TERM: a full join therefore evaluates exactly as it did before this class existed.

The sum has 2^n terms and its signs alternate, so it is evaluated exactly only while the branch count is small. Beyond MAXEXACT branches a genuine quorum (k < n) is evaluated by FJ_quorum.quorumMoments(double[], double[], int) instead, whose Poisson-binomial recurrence adds no cancellation; a full join keeps the exact path at every n so that no existing result moves.

Port of matlab/src/api/fj/fj_ordstat_exp.m.

Reference: A. Thomasian, "Analysis of Fork/Join and Related Queueing Systems", ACM Computing Surveys 47(2), Article 17, 2014, Sec. 3 (Eq. 18-19).

  • Field Details

    • MAXEXACT

      public static final int MAXEXACT
      Branch count above which a genuine quorum leaves the exact alternating sum.
      See Also:

  • Constructor Details

    • FJ_ordstat_exp

      public FJ_ordstat_exp()

  • Method Details

    • fj_ordstat_exp

      public static double fj_ordstat_exp(double[] ri, int k)
      Parameters:
      ri - branch completion time means
      k - quorum, 1 <= k <= ri.length
      Returns:
      the mean instant the k-of-n join fires

    • fj_ordstat_exp

      public static double fj_ordstat_exp(Matrix ri, int k)
      Parameters:
      ri - branch completion time means, as a row or column matrix
      k - quorum, 1 <= k <= ri.length()
      Returns:
      the mean instant the k-of-n join fires