上周事情比较多，导致这篇博文延后了，这周加紧补上。好久没有弄过逻辑证明，因此这部分读得比较累，好在还是硬着头皮啃了下来。

废话少说，切入正题。

DRF具备的属性

论文的中段主要证明了DRF具备的一些良好的性质，包括:

• Sharing Incentive: 如果用户可以在一个总资源只有\(\frac{1}{n}\)的资源下启动\(x\)个任务，那么在有\(n\)个user、可以使用全部资源的场景下，这个用户也可以启动不少于\(x\)的task。这个性质说明了应用该调度算法，合并更大的资源池，不会让整集群的吞吐变糟。
• Strategy-proofness: user无法通过虚假声明自己的资源使用量，来获得有利于自己的分配。即，在DRF下，即便用户虚假声明自己的任务资源使用量，也无法让其启动更多的task。
• Envy-freeness: 一个user不会”嫉妒”另一个user的分配结果，即如果User-A(为方便阐述，后面将用户A记为\(u_{A}\))使用分配给\(u_{B}\)的资源、不使用分配给自己的，无法启动更多的task(获得实际的好处)。
• Pareto efficiency: 也称为帕累托最优(Pareto Optimality)。假定固有的一群人和可分配的资源，从一种分配状态到另一种状态的变化中，在没有使任何人境况变坏的前提下，使得至少一个人变得更好。帕累托最优状态就是不可能再有更多的帕累托改进的余地；换句话说，帕累托改进是达到帕累托最优的路径和方法。 帕累托最优是公平与效率的“理想王国”。
• Single Resource Fairness: 当把资源退化成一维的场景的时候，分配结果也要满足max-min fairness。
• Bottleneck Fairness: 如果有一个资源是瓶颈，那么算法在这维资源的分配上满足max-min fairness。
• Population Monotonicity: 如果一个user退场、并释放自己的资源，那么在剩余user中重新分配资源后，没有一个user的状况会变差。DRF大多数情况下满足这个性质。

证明准备：Progressive Filling

首先在证明中将任务看作是可以连续可无限细分的¹，即可以启动0.x个的task。那么DRF可以转换成如下被称为Processive Filling的过程:

• 所有用户的Dominant Resource share(后面记为\(s\))同速率的上涨、并且每个用户的non-dominant resource也同比例增加，直到资源池中有某个纬度的资源(记为\(R_{k}\))被塞满;
• 将所有使用这个\(R_{k}\)的用户从列表中删除;
• 重复上述过程直至用户列表为空或者资源全部被塞满。

Theorem-1(max-min theorem): DRF分配结果等价于每个用户都存在资源瓶颈项的分配解。

证: 在Progressive Filling中，我们可以观察到分配结果中如果\(u_{j}\)的瓶颈在资源\(R_{k}\)上，那么其他对\(R_{k}\)有需求的用户\(u_{i}\)，必须满足\(s_{j} \ge s_{i}\)。否则的话，\(u_{i}\) 就应该分配更多资源、同时减少分配给\(u_{j}\)的资源（因为在\(R_{k}\)上\(u_{i}\)抢走了一些\(u_{j}\)的）。所以，当所有用户都有瓶颈资源项的时候，\(s\)最小的那个user无法再提高\(s\)了，因此是max-min faireness的(\(\Leftarrow\)成立)。反过来，对于一个DRF解，每个用户必然有一个资源瓶颈项\(R_{k}\)。否则的话，假定\(u_{i}\)没有，那么\(s_{i}\)就可以增加，说明还不是最终解，这和前面已经是一个解的假设是矛盾的(\(\Rightarrow\)成立)。\(\Box\)

Lemma-2: DRF分配结果中的每个user，都至少有一维资源被分配光了。

证: 很简单，假如不是如此，存在一个\(u_{i}\)还有资源可用，那么说明Progressive Filling算法还没结束，即\(s_{i}\)还可以继续上涨，和前面这已经是一个解的前提假设是矛盾的。\(\Box\)

各性质证明

Theorem-3(Pareto efficient): DRF的分配结果是Pareto efficient的。

证: 假如\(u_{i}\)还有帕累托改进的余地。根据Lemma-2，\(u_{i}\)必然有某个维度的资源\(R_{k}\)已经被分配完了。如果\(R_{k}\)只被\(u_{i}\)一个人使用，那么自然无法再提高\(s_{i}\)；但如果\(R_{k}\)被分配给了多人，那么提高\(u_{i}\)的分配量，必然降低也使用\(R_{k}\)的其他用户的\(s\)，这就不是帕累托改进了，因而发生了矛盾。\(\Box\)

Theorem-4(sharing incentive, bottleneck fairness): DRF满足sharing incentive和bottleneck fairness。

证: 考虑有\(n\)个用户，\(R_{k}\)是第一个被分配光的资源，设\(u_{i}\)为这个\(R_{k}\)中share最大的那个，记\(u_{i}\)使用\(R_{k}\)的占比为\(t_{i,k}\)，显然\(t_{i,k} \ge \frac{1}{n}\)(否则资源不会被分配光)，再由Dominant Resource Share的定义可知，\(s_{i} \ge t_{i,k} \ge \frac{1}{n}\)，由于Progress Filling中\(s\)是同速率增长的，因此所有用户的\(s \ge \frac{1}{n}\)。因此满足了sharing incentive。如果所有用户的瓶颈资源都出现在\(R_{k}\)上，就能推出每个用户都拿到了刚好\(\frac{1}{n}\)的\(R_{k}\)资源，满足bottleneck fairness。\(\Box\)

Theorem-5(envy freeness)：DRF是envy-free的。

证: 假设\(u_{i}\)想拿到\(u_{j}\)分配的资源，那么必然 ’\(u_{j}\)在所有资源维度上拿到的比例都要大于\(u_{i}\)‘ (*)，否则\(u_{i}\)拿到后也没法跑更多的任务。根据Theorem-1，在DRF分配结果中，任意一个用户\(u_{i}\)必然有个瓶颈资源\(R_{k}\)，在\(R_{k}\)下其他用户(包括\(u_{j}\))的\(s\)必然不高于\(u_{i}\)(\(s_{j} \le s_{i}\))，(*)的条件就不满足了。因此，\(u_{i}\)拿到\(u_{j}\)的资源也无法跑更多的任务，所以是envy-free的。\(\Box\)

Theorem-6(strategy-proofness): 在DRF中，用户无法虚报自己的资源需求，以获得更加有利的资源分配结果。

证: 假定\(u_{i}\)的真实资源需求为\(d_{i}\)，通过虚报为\(\hat{d}_{i}\)，使得对\(R_{k}\)获得的分配从\(a_{i,k}\)变成了\(\hat{a}_{i,k}\)。由题设可知，需要满足\(d_{i} \ne \hat{d}_{i}\)且\(\hat{a}_{i,k} > a_{i,k}(\forall k, d_{i,k} > 0)\)，即\(\hat{a}_{i} > a_{i}\)，\(u_{i}\)才有动机这么做。记\(R_{r}\)为\(u_{i}\)采用\(d_{i}\)的时候第一个被分配完毕的资源。假设只有\(u_{i}\)需要\(R_{r}\)，那么显然\(u_{i}\)已经能得到它能拿到的最大的了，虚报资源需求也没用；否则假定还有\(u_{j}\)分配得到了\(R_{r}\)，记分配到了\(a_{j,r} > 0\)且\(j \ne i\)。在这种情况下，设Progressive Filling在\(t\)时刻将\(R_{r}\)在\(u_{i}\)使用\(d_{i}\)申请的时候分配完，而在\(t'\)时刻、按照\(\hat{d}_{i}\)的需求将\(R_{r}\)分配完。由于\(\hat{a}_{i} > a_{i}\)，所以\(t'>t\)。这说明在时刻\(t'\)之前，在声明自己需要\(\hat{d}_{i}\)的情况下，\(u_{i}\)并未把\(R_{r}\)资源吃完。在\(t\)到\(t'\)之间的过程中，\(u_{j}\)就可以拿走一部分\(R_{r}\)资源，使得\(\hat{a}_{i,r} < a_{i,r}\)，出现矛盾。\(\Box\)

至此，还剩Single resource fairness和Population Monotonicity两条属性未证明，对于Single Resource Fairness，是不证自明的，在这里不做赘述。对于Population Monotonicity，DRF在满足strictly positive demand的情况下，是可以满足的。所谓strictly positive demand的条件，就是所有user的资源需求都是大于0的，即\(d_{i,k} > 0\)对任意\(u_{i}\)和\(R_{k}\)成立。

Theorem-7: 在strictly positive demands的前提下，DRF分配结果中所有用户的\(s\)相等，即\(\forall i,j\)，\(s_{i} = s_{j}\)。

证: Progressive Filling的过程中，所有user的\(s\)都是同步增长的，当第一个资源\(R_{k}\)被分配完毕后，所有的user的\(s\)都不能再增长了(因为\(d_{i,k} > 0\))，此时的结果就是DRF分配结果，因此大家的\(s\)都相等。\(\Box\)

Theorem-8,9(population monotonicity): DRF在strictly positive demands情况下，满足population monotonicity，否则不一定满足。

证: 在strictly positive demands下，意味着一个DRF分配结果中，所有用户都因为同一个资源的紧缺而无法继续提高\(s\)、而停留在\(s=\alpha\)上(Theorem-7)。假设一个用户退场并释放出他占据的资源，而DRF不满足Population monotonicy，那么就存在一个用户\(u_{i}\)，其最终分配结果\(s_{i} < \alpha\)，而其他用户能够提高自己的\(s_{j} > \alpha\)。这个和前面已经证明的Theorem-3是矛盾的，因为DRF下用户无法通过损害他人来获取自己的利益(帕累托改进的定义)。但不满足strictly positive demands的条件的时候，由于Theorem-7不一定成立，所以存在打破Population monotonicity的反例：假定总资源为<24, 24>，然后\(u_{1}\)的资源需求为<2, 0>，\(u_{2}\)为<1, 2>，\(u_{3}\)为<0, 2>。此时DRF的分配结果为<9, 6, 6>；\(u_{3}\)退出分配，则DRF得到分配结果为<8, 8>，\(u_{1}\)能拿到的资源反倒变少了。\(\Box\)

Theorem-8中的反例，原因在于\(u_{3}\)还在的时候，\(R_{2}\)资源会首先被分配完，导致此时每个用户都只能分配到6，但\(R_{1}\)还有剩余，而此时只有\(u_{1}\)可以分配，Progressive Filling得以继续，将剩余的\(R_{1}\)全部给了\(u_{1}\)。但\(u_{3}\)挪走后，\(R_{2}\)不再首先发生紧缺，\(u_{1}\)也就没办法占到便宜了。

至此，DRF的各项属性证明完毕，可以看出DRF具备的这些属性还是非常优良的，在”公平”和”效率”之间，寻求了一个比较好的平衡。个人以为尤其是Sharing Incentive，Pareto efficient和Strategy proofness三条，在现实中非常的重要。DRF能够从数理上证明自己的有效性，这也是为什么DRF会成为许多知名调度系统的核心算法。

下一篇博文将继续解读DRF算法，将其与另外的Asset Fairness和CEEI进行比对，加深对这些调度算法的理解。