fj_ordstat_exp.h File Reference

Mean of the k-th smallest of n independent EXPONENTIAL branch completion times, i.e. More...

#include <cmath>
#include <cstddef>
#include <vector>
#include "line/api/fj/fj_quorum_moments.h"
#include "line/api/fj/fj_types.h"
#include "line/num/number.h"
#include "line/util/error.h"

Include dependency graph for fj_ordstat_exp.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::fj

Functions
template<class T>
T	line::fj::fj_ordstat_exp (const std::vector< T > &ri, std::size_t k)
	Mean of the k-th smallest of n independent EXPONENTIAL branch completion times, i.e.

Variables
static const std::size_t	line::fj::FJ_ORDSTAT_MAX_EXACT = 15
	Branch count above which a genuine quorum leaves the exact alternating sum.

Detailed Description

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.

Templated port of matlab/src/api/fj/fj_ordstat_exp.m, cross-checked against jar/src/main/java/jline/api/fj/FJ_ordstat_exp.java.

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 header existed, which is what keeps the MMT fork-join fixed point bit-identical on a standard join.

The exact path is RATIONAL – reciprocals, sums and integer binomials only – so it holds in an exact field and is not gated on has_transcendental. Only the large-n fallback is, since fj_quorum_moments fits a standard deviation.

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

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

Definition in file fj_ordstat_exp.h.