NWU speed-variation load conjecture for redundancy systems

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.

Sources & referencesView supporting material

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.