fj_quorum_moments.h File Reference

Mean and variance of a k-of-n (quorum) join completion time, from the mean and variance of each branch. More...

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

Include dependency graph for fj_quorum_moments.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::fj

Functions
template<class T>
FJQuorumMomentsResult< T >	line::fj::fj_quorum_moments (const std::vector< T > &branchMeans, const std::vector< T > &branchVars, std::size_t k)
	Mean and variance of a k-of-n (quorum) join completion time, from the mean and variance of each branch.

Variables
constexpr std::size_t	line::fj::FJ_QUORUM_MAX_BRANCHES = 512
	Branch counts above this are refused: evaluation is cubic in n.

Detailed Description

Mean and variance of a k-of-n (quorum) join completion time, from the mean and variance of each branch.

Templated port of matlab/src/api/fj/fj_quorum_moments.m, cross-checked against jar/src/main/java/jline/api/fj/FJ_quorum.java (identical three-point fit, merged grid and Poisson-binomial recurrence).

Each branch is expanded into a three-point discrete step CDF matching its first two moments. At any 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, and the k-th order statistic is the upper tail sum_{j>=k} q_j. At k = n this reduces to the product of the branch CDFs (the ordinary AND-join) and at k = 1 to 1 - prod(1 - F_i) (the minimum), two identities the port must reproduce.

The recurrence is the reason for the whole construction: it computes the same quantity as the inclusion-exclusion identity used by LQNS, but every term is a probability in [0,1] and none is subtracted, so it avoids the catastrophic cancellation the alternating binomial sum incurs as n grows.

static_assert(num_traits<T>::has_transcendental) – the three-point fit takes the standard deviation, so a single sqrt puts the whole function outside the field. Everything downstream of that sqrt is rational.

Follows Omari, Franks, Woodside and Pan, as implemented in LQNS 6.x (randomvar.cc).

Definition in file fj_quorum_moments.h.