NWU speed-variation load conjecture for redundancy systems

At least 5 years old · documented by

Let NN be the number of servers, let dd satisfy 1<d<N1<d<N, and suppose that job types are unknown. For each server i=1,…,Ni=1,\dots,N, let γi\gamma_i denote its load in the system with one replica and let γˉi\bar{\gamma}_i denote its load in the system with dd replicas. The speed variations are called NWU when they have the stated new-worse-than-used property.

NWU load conjecture. For NWU distributed speed variations, the loads satisfy

γˉi≥γi,i=1,…,N,\bar{\gamma}_i\geq \gamma_i,\qquad i=1,\dots,N,

and for strictly NWU distributed speed variations the inequalities are strict:

γˉi>γi,i=1,…,N.\bar{\gamma}_i>\gamma_i,\qquad i=1,\dots,N.

The conjecture concerns whether starting multiple replicas creates at least as much load at every server as the single-replica system for unknown job types. The supplied text gives no evidence that this conjecture has been proved or refuted.

References

Primary source

Youri Raaijmakers and Sem Borst, “Achievable Stability in Redundancy Systems”, arXiv:2008.03478 (2020).

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.