Fair Resource Distribution Algorithm v1
Imagine a finite resource that you want to distribute amongst peers in a fair
manner. If you know the number of peers to be n, the problem becomes
trivial and you can assign every peer 1/n-th of the total. This way
every peer gets the same amount, while no part of the resource stays unused.
But what if the number of peers is only known retrospectively? That is, how
many resources do you grant a peer if you do not know whether there are more
peers or not? How do you define “fairness”? And how do you make sure as little
of the resource as possible stays unused?
The fairdist algorithm provides one possible solution to this problem. It
defines how many resources a new peer is assigned, considering the following
propertis:
- The total amount of resources already distributed to other peers. This is
also referred to by the term
consumption. - The number of peers that already got resources assigned.
- The amount of resources remaining. That is, the resources that are
remaining to be distributed. This is also referred to by the term
reserve.
The following is a mathematical proof of the properties of the fairdist
algorithm. For the reference implementation of the algorithm and information on
the different applications of it, see the
r-fairdist project.
Prerequisites
We define a set of symbols up front, to keep the proofs shorter. Whenever these symbols are mentioned, the following definition applies:
- Let \(c \in \mathbb{R}_{\geq 0}\) be a total amount of consumed resources.
- Let \(r \in \mathbb{R}_{\geq 0}\) be a total amount of reserved resources.
- Let \(n \in \mathbb{N}_0\) be a number of peers that consumed resources.
- Let \(A: \mathbb{N}_0 \to \mathbb{R}_{>0}\) be a function that computes the proportion of \(r\) a peer can consume, based on the number of peers \(n\) that currently have resources consumed.
- Let \(G: \mathbb{N}_0 \to \mathbb{R}_{>0}\) be a function that computes the proportion of \(c + r\) a peer is guaranteed, based on the number of peers \(n\) that currently have resources consumed.
The algorithm considers a total amount of resources, but splits it into two separate parts, the remaining reserve \(r\) and the consumed part \(c\). Their sum represents the total amount that was initially available. It then declares a function \(A\), which is the resource allocator. It will later on be used to calculate how many resources of the reserve a peer can allocate: \(\frac{r}{A(n)}\). That is, \(A\) defines the proportion of the reserve a new peer gets access to. The smaller it is, the more a peer gets.
Similarly, the guarantee \(G\) is used to declare a lower bound of the total resources the allocator \(A\) grants a new peer. That is, while \(A\) is a function applied to allocations, \(G\) is a property the allocator will guarantee you. Unlike an allocation, \(G\) will later on be calculated based on the total amount of resources: \(\frac{c + r}{G(n)}\). Again, the function defines the proportion that is guaranteed. So the smaller \(G\) is, the stronger the guarantee becomes.
Definition
The allocator \(A\) is said to guarantee the limit \(G\), if there exists a function \(R: \mathbb{N}_+ \to \mathbb{R}_{>0}\) so that for all \(c\), \(r\), and \(n\):
\[r \geq \frac{c}{R(n)}\]implies both:
- \[\frac{r}{A(n)} \geq \frac{c+r}{G(n)}\]
- \[r - \frac{r}{A(n)} \geq \frac{c + \frac{r}{A(n)}}{R(n+1)}\]
The idea here is to define a function \(A\) which calculates how many resources a new peer can allocate. That is, considering a new peer requests resources, it will get \(\frac{1}{A(n)}\) of the reserve. The first property of this implication guarantees that this allocation is bigger than, or equal to, the guaranteed total for each peer. The guaranteed total is calculated through \(G\) based on the total amount of resources (which is the consumption plus the reserve).
If you now pick an allocator \(A\) and a guarantee \(G\) that fulfil this definition, the idea is that this ensures you that the allocator \(A\) can be used to serve resource requests from new peers, and it ensures that regardless of how many peers will request resources, each one will be guaranteed an amount equal to, or bigger than, the guarantee \(G\).
This definition requires the existance of a reserve watermark \(R\). It uses this watermark as a selector for an inductive step. That is, if the requirements of this reserve selector are true, the second implication guarantees that they are true for an infinite number of following allocations. That is, the right hand side of the second implication matches exactly the requirement of the implication, once a single allocation was performed (i.e., a resource chunk was subtracted from the reserve and added to the total consumption, while the number of peers increased by one).
Note that if \(c\) is \(0\), then the requirement of the implication is true for all \(r\) and \(R\). This guarantees that there is always a situation where allocator \(A\) can actually be applied.
Lemma 1
To prove an allocator \(A\) guarantees \(G\), it is sufficient to show that \(R\) fulfils:
\[R(n) \leq \frac{G(n)}{A(n)} - 1\]and
\[A(n) \geq \frac{1+R(n+1)}{R(n+1)-R(n)}\]This lemma is used to make it easier to prove a specific allocator guarantees a specific limit. Without it, each proof of the different allocators would have to replicate it.
However, this lemma also gives a better feeling of what the different functions actually mean. For instance, it clearly shows \(A\) must always be smaller than \(G\), and that by a considerable amount. If \(A = G\), then no \(R\) would ever fulfil this requirement (remember: \(R(n) > 0\)). At the same time, you can see the closer \(A\) and \(G\) are together, the smaller \(R\) gets, and as such the requirements on the reserve get harder to fulfil.
The second requirement gives you a recursive equation to find an \(R\) for any allocator you pick. Hence, in combination both these requirements show you an iterative process to find \(A\) and \(R\), for any guarantee \(G\) you pick. However, the closer \(A\) and \(G\) get, the harder it becomes to solve the recursive equation.
Proof
To show this lemma is true, we must show both implications of the definition are true. As first step, we show the first implication is true, which is:
\[r \geq \frac{c}{R(n)} \implies \frac{r}{A(n)} \geq \frac{c+r}{G(n)}\]We show this b starting with the left-hand side and showing it implies the right hand side, using the requisite of this lemma.
\[\begin{align} r &\geq_{req} \frac{c}{R(n)}\\[8pt] R(n) &\geq \frac{c}{r}\\[8pt] \frac{G(n)}{A(n)} - 1 \geq_{req} R(n) &\geq \frac{c}{r}\\[8pt] \frac{G(n)}{A(n)} - 1 &\geq \frac{c}{r}\\[8pt] \frac{r G(n)}{A(n)} - r &\geq c\\[8pt] \frac{r G(n)}{A(n)} &\geq c+r\\[8pt] \frac{r}{A(n)} &\geq \frac{c+r}{G(n)}\\[8pt] \end{align}\]As second step, we need to show the second implication of the definition is true, which is:
\[r \geq \frac{c}{R(n)} \implies r - \frac{r}{A(n)} \geq \frac{c + \frac{r}{A(n)}}{R(n+1)}\]To prove this, we start with the second requisite of this lemma and then show it implies the right-hand side of the implication, using the requisite of the implication.
\[\begin{align} A(n) &\geq_{req} \frac{1+R(n+1)}{R(n+1)-R(n)}\\[16pt] A(n)R(n+1) - A(n)R(n) &\geq 1+R(n+1)\\[16pt] -A(n)R(n) &\geq 1+R(n+1) - A(n)R(n+1)\\[16pt] A(n)R(n) &\leq A(n)R(n+1)-R(n+1)-1\\[16pt] R(n) &\leq R(n+1) - \frac{R(n+1)}{A(n)} - \frac{1}{A(n)}\\[16pt] \end{align}\]\[\begin{align} \frac{c}{R(n)} &\geq \frac{c}{R(n+1) - \frac{R(n+1)}{A(n)} - \frac{1}{A(n)}}\\[16pt] r \geq_{req} \frac{c}{R(n)} &\geq \frac{c}{R(n+1) - \frac{R(n+1)}{A(n)} - \frac{1}{A(n)}}\\[16pt] r &\geq \frac{c}{R(n+1) - \frac{R(n+1)}{A(n)} - \frac{1}{A(n)}}\\[16pt] rR(n+1) - \frac{rR(n+1)}{A(n)} - \frac{r}{A(n)} &\geq c\\[16pt] rR(n+1) - \frac{rR(n+1)}{A(n)} &\geq c + \frac{r}{A(n)}\\[16pt] r - \frac{r}{A(n)} &\geq \frac{c + \frac{r}{A(n)}}{R(n+1)}\\[16pt] \end{align}\]Hint: The following introduction of \(c\) is correct, since \(R(n)\) is per definition greater than \(0\), so neither side can be 0.
Theorem
The following allocators each guarantee the specified limit:
\[\begin{align} A_1(n) &:= 2\\ G_1(n) &:= 2^{n+1} = \mathcal{O}(2^n)\\ \\ A_2(n) &:= n+2\\ G_2(n) &:= n^2+3n+2 = \mathcal{O}(n^2)\\ \\ A_3(n) &:= (n+2) \log_2(n+2) + (n+2)\\ G_3(n) &:= \mathcal{O}(n \log_2(n)^2)\\ \end{align}\]This theorem defines three different allocators for different guarantees. The last one provides the strongest guarantee. Both the allocation and the guarantee are quasilinear. It is thus a good fit for fair allocation schemes, while still being reasonably fast to compute.
The other two provide quadratic and exponential guarantees and are mostly listed for documentational purposes. With the quasilinear guarantees at hand, there is little reason to use the other two.
As you might notice, this theorem does not provide a solution where \(A\) and \(G\) become infinitesimally close. It remains open whether what this solution would look like. However, the listed quasilinear solution is good enough, that it is unlikely that better options exist, which can still be calculated in reasonable amounts of time.
Proof
We provide a function \(R\) for each pair. We then substitute them in Lemma 1 and show through equivalence transformations that the assertions are true.
Proof 1: Exponential Guarantee
- Allocator: \(A(n) := 2\)
- Guarantee: \(G(n) := 2^{n+1}\)
Let \(R(n) := 2^n - 1\).
Part 1:
\[\begin{align} R(n) &\leq_{lemma} \frac{G(n)}{A(n)} - 1\\[8pt] 2^n - 1 &\leq \frac{2^{n+1}}{2} - 1\\[8pt] 2^n &= \frac{2^{n+1}}{2}\\[8pt] 2^n &= 2^n\\[8pt] \end{align}\]Part 2:
\[\begin{align} A(n) &\geq \frac{1+R(n+1)}{R(n+1)-R(n)}\\[8pt] 2 &\geq \frac{1+(2^{n+1} - 1)}{(2^{n+1} - 1)-(2^n - 1)}\\[8pt] 2 &\geq \frac{2^{n+1}}{2^{n+1} - 2^n}\\[8pt] 2 &\geq \frac{2^{n+1}}{2^{n+1}(1 - \frac{1}{2})}\\[8pt] 2 &\geq \frac{1}{1 - \frac{1}{2}}\\[8pt] 2 &\geq 2\\[8pt] \end{align}\]Proof 2: Polynomial Guarantee
- Allocator: \(A(n) := n+2\)
- Guarantee: \(G(n) := n^2 + 3n + 2\)
Let \(R(n) := n\).
Part 1:
\[\begin{align} R(n) &\leq_{lemma} \frac{G(n)}{A(n)} - 1\\[8pt] n &\leq \frac{n^2 + 3n + 2}{n+2} - 1\\[8pt] n+1 &\leq \frac{n^2 + 3n + 2}{n+2}\\[8pt] (n+1)(n+2) &\leq n^2 + 3n + 2\\[8pt] n^2 + 3n + 2 &\leq n^2 + 3n + 2\\[8pt] \end{align}\]Part 2:
\[\begin{align} A(n) &\geq \frac{1+R(n+1)}{R(n+1)-R(n)}\\[8pt] n+2 &\geq \frac{1+(n+1)}{(n+1)-(n)}\\[8pt] n+2 &\geq \frac{n+2}{n-n+1}\\[8pt] n+2 &\geq n+2\\[8pt] \end{align}\]Proof 3: Quasilinear Guarantee
- Allocator: \(A(n) := (n+2) \log_2(n+2) + (n+2)\)
- Guarantee: \(G(n) := \mathcal{O}(n \log_2(n)^2)\)
Let \(R(n) := \log_2(n+1)\).
Part 1:
\[\begin{align} R(n) &\leq_{lemma} \frac{G(n)}{A(n)} - 1\\[8pt] \log_2(n+1) &\leq \frac{\mathcal{O}(n \log_2 (n)^2)}{(n+2) \log_2(n+2) + (n+2)} - 1\\[8pt] \log_2(n+1) + 1 &\leq \frac{\mathcal{O}(n \log_2 (n)^2)}{(n+2) \log_2(n+2) + (n+2)}\\[8pt] \log_2(n+1) + 1 &\leq \frac{\mathcal{O}(n \log_2 (n)^2)}{(n+2) (\log_2(n+2) + 1)}\\[8pt] \log_2(n+1) + 1 \leq \log_2(n+2) + 1 &\leq \frac{\mathcal{O}(n \log_2 (n)^2)}{(n+2) (\log_2(n+2) + 1)}\\[8pt] (\log_2(n+1) + 1)^2 &\leq \frac{\mathcal{O}(n \log_2 (n)^2)}{(n+2)}\\[8pt] (n+2) \cdot (\log_2(n+1) + 1)^2 &\leq \mathcal{O}(n \cdot \log_2 (n)^2)\\[8pt] \end{align}\]Part 2:
For this part, we rely on the following property:
\[\frac{1}{n+1} \leq \log(n+1) - \log(n) \leq \frac{1}{n}\]This is true for all logarithms for all \(n \in \mathbb{N}_+\).
We now show the second requirement of the Lemma is true. However, we cannot use equivalence transformations as in the other proofs. Hence, we show it by implication.
\[\begin{align} n+2 &= n+2\\[8pt] (n+2) (1+\log_2(n+2)) &= (n+2) (1+\log_2(n+2))\\[8pt] (n+2) (1+\log_2(n+2)) &= \frac{1+\log_2(n+2)}{\frac{1}{n+2}}\\[8pt] (n+2) \log_2(n+2) + (n+2) &= \frac{1+\log_2(n+2)}{\frac{1}{n+2}}\\[8pt] (n+2) \log_2(n+2) + (n+2) &\geq \frac{1+\log_2(n+2)}{\log_2(n+2) - \log_2(n+1)}\\[8pt] (n+2) \log_2(n+2) + (n+2) &\geq \frac{1+\log_2((n+1)+1)}{\log_2((n+1)+1) - \log_2(n+1)}\\[8pt] A(n) &\geq \frac{1+R(n+1)}{R(n+1)-R(n)}\\[8pt] \end{align}\]