Uniform minimization conjecture for light-traffic coefficients

Consider a redundancy system with NN servers and edge-selection probabilities P=(p{i,j})i,jP=(p_{\{i,j\}})_{i,j}, where i,j{1,,N}i,j\in\{1,\ldots,N\} and iji\ne j. For each q0q\geq 0, let αq(P)\alpha_q(P) denote the coefficient governing the light-traffic probability of having at least qq jobs. Let P=(p{i,j})i,jP'=(p'_{\{i,j\}})_{i,j} be the uniform policy, with

p{i,j}=1(N2).p'_{\{i,j\}}=\frac{1}{\binom{N}{2}}.

Uniform minimization conjecture. For every q0q\geq 0, the coefficient under the uniform policy equals the minimum over all edge-selection probability vectors:

αqαq(P)=min{αq(P)P=(p{i,j})i,j}.\alpha_q^*\coloneqq\alpha_q(P')=\min\left\{\alpha_q(P)\mid P=(p_{\{i,j\}})_{i,j}\right\}.

This optimization conjecture would imply the uniform sampling dominance conjecture in the light-traffic regime through the stated comparison of tail probabilities. The coefficients are continuous functions on the compact set of edge-selection probabilities, so a minimum exists; what remains open is proving that the uniform policy attains it for every qq.

Sources & referencesView supporting material

Primary source

Ellen Cardinaels, Sem Borst and Johan S. H. van Leeuwaarden, “Power-of-two sampling in redundancy systems: the impact of assignment constraints”, arXiv:2111.05777 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.