Package jline.api.fj

Class FJ_quorum

java.lang.Object
jline.api.fj.FJ_quorum
public class FJ_quorum extends Object
Completion time of a k-of-n (quorum) join over independent, not necessarily identically distributed branches.

Each branch is summarised by its first two moments and expanded into a discrete step CDF by a two-moment fit. The CDF of the k-th order statistic is then assembled by the inclusion-exclusion identity

   F_(k)(t) = sum_{i=k..n} (-1)^(i-k) * C(i-1, k-1) * e_i(F_1(t), ..., F_n(t))

where e_i is the i-th elementary symmetric polynomial of the branch CDFs, evaluated by the memoised recurrence in

invalid reference 
#symmetric
. For k = n this collapses to the product of the branch CDFs, i.e. the ordinary AND-join, and for k = 1 to 1 - prod(1 - F_i), i.e. the minimum.

For identically distributed branches the result agrees with FJ_order_stat.fj_order_stat_cdf(double, int, int), which is the closed binomial form of the same quantity; this class generalises it to heterogeneous branches, which is what an LQN AND-join with a quorum requires since its branches carry different demands.

Follows the formulation of Omari, Franks, Woodside and Pan, as implemented in LQNS 6.x (randomvar.cc, DiscreteCDFs::quorumKofN and DiscretePoints::estimateCDF).

  • Field Details

    • MAX_BRANCHES

      public static final int MAX_BRANCHES
      Largest branch count accepted by quorumKofN(jline.api.fj.FJ_quorum.StepCDF[], int).

      The evaluation is cubic in the branch count, so this bounds the work at roughly 1e8 elementary operations. An LQN AND-join with more branches than this is degenerate; the limit exists to turn a silent hang into an immediate, explicable failure.

      See Also:

  • Constructor Details

    • FJ_quorum

      public FJ_quorum()

  • Method Details

    • threePointFit

      public static FJ_quorum.StepCDF threePointFit(double mean, double variance)
      Two-moment fit of a branch completion time to a three-point discrete distribution.

      Matches the mean and variance exactly. A zero standard deviation degenerates to a single deterministic point, and a zero mean yields the empty step function.

      Parameters:
      mean - branch mean completion time, must be non-negative
      variance - branch variance, must be non-negative
      Returns:
      the fitted step CDF

    • add

      public static FJ_quorum.StepCDF add(FJ_quorum.StepCDF x, FJ_quorum.StepCDF y)
      Pointwise sum of two step functions on the union of their time grids.

    • multiply

      public static FJ_quorum.StepCDF multiply(FJ_quorum.StepCDF x, FJ_quorum.StepCDF y)
      Pointwise product of two step functions on the union of their time grids.

      An empty operand annihilates the product, matching the convention that an absent branch distribution contributes no mass.

    • quorumKofN

      public static FJ_quorum.StepCDF quorumKofN(FJ_quorum.StepCDF[] branches, int k)
      CDF of the k-th smallest of n independent branch completion times.

      Evaluated pointwise on the union of the branch grids. At each time the number of completed branches is Poisson-binomial, so its distribution is built by the recurrence q_j <- q_{j-1} * F_i + q_j * (1 - F_i) over branches i, and the k-th order statistic is the upper tail sum_{j>=k} q_j.

      This is the same quantity as the inclusion-exclusion identity sum_{i=k..n} (-1)^(i-k) C(i-1,k-1) e_i(F_1..F_n) used by LQNS, but every term here is a probability in [0, 1] and no term is subtracted, so it does not suffer the catastrophic cancellation that the alternating binomial sum incurs as n grows.

      Parameters:
      branches - the branch CDFs, one per branch
      k - the quorum count, in [1, branches.length]
      Returns:
      the step CDF of the k-th order statistic
      Throws:
      IllegalArgumentException - if k is out of range or there are more than MAX_BRANCHES branches

    • quorumMoments

      public static double[] quorumMoments(double[] branchMeans, double[] branchVariances, int k)
      Mean and variance of the completion time of a k-of-n join whose branches are given by their first two moments.

      This is the entry point used by the layered solver: each branch mean and variance comes from the residence time and variance accumulated along that branch of the activity graph.

      Parameters:
      branchMeans - per-branch mean completion times
      branchVariances - per-branch variances, same length as branchMeans
      k - the quorum count, in [1, branchMeans.length]
      Returns:
      a two-element array holding the mean and the variance of the join completion time