Containers/Guarantees for resources

This page describes how guarantees for resources can be implemented.

comment4,

Providing a guarantee through limiting

The idea of getting a guarantee is simple:

if any group Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g_i} requires a Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_i} units of resource from $R$ units available then limiting all the rest groups with $R-G_{i}$ units provides a desired guarantee

For $N$ groups in the system this implies solving a linear equation set to get limits $L_{i}$ like this:

${\begin{cases}L_{2}+L_{3}+\ldots +L_{N}=R-G_{1}\\L_{1}+L_{3}+\ldots +L_{N}=R-G_{2}\\\ldots \\L_{1}+L_{2}+\ldots +L_{N-1}=R-G_{N}\\\end{cases}}$

In a matrix form this looks like

$AL=G\;$

where

$A={\begin{bmatrix}0&1&1&\cdots &1&1\\1&0&1&\cdots &1&1\\&&\cdots \\1&1&1&\cdots &1&0\\\end{bmatrix}},L={\begin{bmatrix}L_{1}\\L_{2}\\\vdots \\L_{N}\end{bmatrix}},G={\begin{bmatrix}R-G_{1}\\R-G_{2}\\\vdots \\R-G_{N}\end{bmatrix}}$

and thus the solution is

$L=A^{-1}G\;$

Skipping boring calculations, the reverse matrix $A^{-1}\;$ is

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A^{-1} = \frac {1} {N - 1} \left( A - (N - 2) E \right) }

This solutions looks huge, but the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L} vector is calculated in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(N)} time:

void calculate_limits(int N, int *g, int *l)
{
        int sum;
        int i;

        if (N == 1) {
                l[0] = R;
                return;
        }

        sum = 0;
        for (i = 0; i < N; i++)
                sum += R - g[i];
        for (i = 0; i < N; i++)
                l[i] = (sum - (R - g[i]) - (N - 2) * (R - g[i]))/(N - 1);
}

Disadvantages of this approach

This approach has only one disadvantage: O(n) time needed to start a new container.