K-server问题

引例和问题

考虑这样一个情境：如果你是一个军队的指挥官，要调运军力去往战场上不同的据点。战场局势瞬息万变，每隔一段时间，就会有新的据点需要占据。如何指挥军力去完成任务，使得军队移动的总距离尽可能小？

上面的例子所提出的问题，可以抽象为如下的模型：现有k个服务者(server)，一系列请求(request)会陆续到达。每当有一个请求到达，就要决定调动哪个服务者去服务该请求。服务者和请求可以视为度量空间中的点。最终的目标是使得对所有服务者调动的代价（比如移动的距离之和）尽可能小。

有很多实际应用场景可以规约到这个模型。比如，物资的运输、警力的紧急调度、服务器的资源管理，等等。

数学描述：

设$k > 1$是一个整数，$\mathcal{M}$是所考察的度量空间，在$\mathcal{M}$中任意两个点$a,b$之间的距离用定义在$\mathcal{M}$上的映射关系$d(a,b)$表示。$k$个移动的服务者是$\mathcal{M}$中的点。请求序列是$\sigma = { r_1, r_2, \ldots, r_n }$，其中$r_i \in \mathcal{M}$。如果一个服务者到达了某个请求$r$的位置，就称$r$被服务。通过移动服务者，算法须要连续地服务所有的请求。对任何给定的请求序列$\sigma$和$k$个服务者，$ALG(\sigma)$表示一个算法$ALG$移动服务者的总距离。算法的目标是最小化$ALG(\sigma)$。

其他补充：

• 度量空间可能是无限或有限的（分别对应于连续和离散的情况）
• (h,k)-server problem: 在线k-server算法比较的对象是离线h-server算法，$h \le k$

基本概念

离线最优算法

首先，k-server问题是在线问题，因为请求序列是随着时间的推进依次出现的，每当有一个请求出现，就须要决策哪个服务者去服务它。

离线的场景，没有时间的概念，整个请求序列$\sigma$在一开始就知道。当服务者的数量等于请求的数量时，可以用二分图的最小权完美匹配算法解决（$O(kn^2)$），其他的情况没有多项式时间算法。

一个简单的贪婪策略

考察下面的贪婪策略：每当有一个请求出现时，用与它最近的服务者去服务它。

很容易举出一个例子来说明这个贪婪策略会很差。设有两个服务者，请求出现的位置有3个，用$a,b,c$表示，它们位于直线上从左往右的方向，且$d(a,b) < d(b,c)$。那么无论两个服务者的初始位置在哪，对于请求序列$c,b,a,b,a,\ldots$，使用贪婪策略会导致一个服务者在到达$c$后就永远滞留在那里，另外一个服务者在$a,b$之间徘徊。显然，最优解的代价不会超过$d(a,b) + 2d(b,c)$，而贪婪策略则可能与最优解无限远。

k-server猜想

• k-server猜想：对于任何度量空间，k-server问题都存在k-竞争的在线算法。
• 无法推广到到非对称度量空间
• 对任何度量空间，已知最好的竞争比是$2k-1$ (work function算法)

确定算法的一个竞争比下界

• 对于至少有$k+1$个点的度量空间（请求出现的位置是离散且有限的），任何确定性k-server算法的竞争比不可能小于$k$
• 更强的结论：对于至少有$k+1$个点的度量空间，任何(h,k)-server问题的算法竞争比不可能小于$\frac{k}{k-h+1}$

简单环境下的k-server问题

坏消息：对于大多数几何结构，例如欧式平面，还没有任何k-竞争确定算法被发现。

好消息：对于欧式线，存在k-竞争算法，并且可以推广到树上。

线(Line)

双覆盖算法（Double-Coverage, DC） 如果请求落在所有服务者构成的凸包的外面，用与它最近的服务者去服务它；否则，请求一定落在两个相邻的服务者之间，用相等的速度将这两个服务者同时移向请求，直到其中一个到达它（如果两个服务者同时占据一个请求，就任选一个）。

DC算法是k-竞争的。

证明：

• 势函数方法(potential function method) （关于势函数方法应用于竞争比的分析，将在下次组会用一个经典模型来讲解）

势函数： \(\Phi = k \cdot M_{\text{min}} + \sum_{\text{DC}}\) 其中，$M_{\text{min}}$: OPT和DC算法服务器位置之间的最小费用匹配（即将一个服务者位置状态转移到另一个位置状态所需移动的最小距离）；$\sum_{\text{DC}}$: DC服务者两两之间的距离之和，即$\sum_{\text{DC}} = \sum_{i < j} d(s_i, s_j)$。

显然，$\Phi$非负。接下来须要证明：(i) 如果只有OPT移动了距离d，势函数最多会增加$kd$. (ii) 如果只有DC移动了距离d，势函数最少能减少$d$. （该证明模式被称为“交叉移动”，interleaving moving style）

证(i). 显然成立。只有OPT移动时，$\sum_{\text{DC}}$不变，而$M_{\text{min}}$增加不会超过d。

证(ii). 由于DC有两种移动方式，因此分别针对这两种情况讨论。

情况一：DC只移动一个服务者。此时DC移动的一定是所有服务者构成的凸包的极点处的服务者，那么该服务者一定是远离其他$k-1$个服务者，所以$\sum_{\text{DC}}$的增量是$(k-1)d$。另外，一定存在一个最小费用匹配，其中DC移动的服务者与该请求是相匹配的，因此$M_{\text{min}}$至少减少了$d$。于是，$\Phi$的减少量至少是$kd - (k-1)d = d$。

情况二：DC同时移动了两个服务者（设为$s_1, s_2$）。此时请求点落在$s_1, s_2$之间，这两个服务者同时以相反的方向向请求点移动，由于DC移动的总距离是$d$，因此它们各自移动的距离是$d/2$。在最小费用匹配中，$s_1, s_2$至少有一个与请求点匹配，因此$M_{\text{min}}$至少减少$d/2$；而另外一个点则可能远离匹配点，导致$M_{\text{min}}$至多增加$d/2$，所以$M_{\text{min}}$至少不会增加。对于$\sum_{\text{DC}}$，两个服务者对其他所有服务者的距离不变（它们各自的增加量和减少量相互抵消），但是它们两个之间的距离减少了$d$，因此整体上$\sum_{\text{DC}}$减少$d$，即$\Phi$减少量是$d$。

树(Tree)

• 不考虑树枝的权重
• 定义“邻居”：对一个服务者$s_i$，如果它到请求的最短路径上没有其他服务者，则称$s_i$是该请求的一个邻居。

树覆盖算法（DC-Tree） 每当有请求出现时，将该请求的所有邻居以相同的速度移向请求。

树覆盖算法是k-竞争的。

其他算法

推广到高维空间？

• 高效 = 计算复杂度不随着输入规模的增大而指数增加
• 坏消息：即便对于二维欧式空间，尚未发现高效的k-server算法
• 好消息：对于任意欧式空间的2-server问题，存在3-竞争的算法

设$\mathcal{M}$是任意欧式空间，对任意$x,y,r \in \mathcal{M}$，定义松弛$\text{slack}(x,y,r) = d(x,y) + d(x,r) - d(y,r)$。根据三角不等式，该函数非负。设$\gamma \in [0,1]$是一个非负实数。设$x,y$是所控制的两个服务者，且$x,y$分别表示它们的实时位置。给出如下算法：

$\gamma $松弛覆盖（Slack-Coverage,SC$_\gamma$）设r是当前要服务的请求，x与r的距离更近（如果与r的距离相等，随机选一个），将y向r移动$\gamma \cdot \text{slack}(x,y,r)$距离，同时选择x去服务r。

对任意欧式空间，SC$_{1/2}$是3-竞争的。

利用均衡原则的启发式算法

对任意有$k+1$个点的离散度量空间中的k-server问题，下面的懒惰算法（也叫延迟算法）能够达到k的竞争比。

平衡算法（Balance） 对每个服务者$s_i$，维护它目前为止行驶的总距离$D_i$. 然后用$D_i + d(s_i, r)$最小的服务者去服务请求$r$。

平衡算法是k-竞争的。

注意上面的算法都隐含如下的假设：当新的请求出现时，k个服务者都处于闲置状态。其实这个假设是不现实的，但是有了它可以便于分析。

功函数方法(Work Function Method)

符号说明

• $C$: 组态（configuration），表示服务者集合的（瞬时）位置状态。是一个多重集合，即集合中允许存在多个位于同一位置的服务者。$C$中的一个元素用小写字母表示
• 两个组态$X,Y$的距离用$D(X,Y)$表示，等于$X$和$Y$之间的最小权匹配
• 按时间先后到达的请求序列$\sigma = { r_1, r_2, \ldots, r_n }$

功函数

用$\sigma_i$表示前i个请求构成的请求序列$r_1, r_2, \ldots, r_i$，$\sigma_0$表示初始空的请求序列。设初始组态是$C_0$，k-服务者的功函数$w_{\sigma_i}(C)$定义为：离线情况下，从初始组态$C_0$处理完请求序列$\sigma_i$到达组态$C$所需要的最小代价。注意$C$不一定包含请求$r_i$的位置（或者$\sigma_i$中的任何一个请求）。

递推关系：

$w_{\sigma_0}(C) = D(C_0, C)$, 当$i = 0$

当$i > 0$时， \(w_{\sigma_i}(C) = \begin{cases} & w_{\sigma_{i-1}}(C), & \text{if} \quad r_i \in C \\ & \min_{x \in C}{ w_{\sigma_{i-1}}(C-x+r_i) + d(r_i, x) }, & \text{otherwise} \end{cases}\) 其中，$C-x+r_i$的含义是将组态$C$中某个服务者$x$移到请求$r_i$的位置。整个第二行表达式的含义是：既然$r_i$不在$C$中，那么我们先以最优的代价处理掉$\sigma_i$，到达某个组态$B$，再从$B$到达目标组态$C$。由于无论如何都要处理$r_i$，我们可以把组态B定为包含$r_i$且与C仅差一步的那个状态，这时B可以表达为$B = C - x +r_i$，到达B的最小代价为$w_{\sigma_i}(B) = w_{\sigma_{i-1}}(B)$，等式成立的原因是B中包含$r_i$。

另外，$OPT(\sigma_i) = \min_C w_{\sigma_i}(C)$

在线k-server功函数算法

功函数算法(WFA) 设$\sigma_i$是当前时刻收集到的请求序列，$C$是当前状态（处理完$\sigma_i$后的组态），当$r_{i+1}$到达时，按以下准则选择服务者$s$去处理请求： \(s = \arg \min \limits_{x \in C} \{ w_{\sigma_i}(C-x+r_{i+1}) + d(x, r_{i+1}) \}\)

可见，WFA背后的思想，其实就是动态规划。当然，对于在线的情况，由于无法预知未来信息，这种算法是一种近似的动态规划。

关于WFA的竞争性，有如下结论：

对任意度量空间，WFA是$(2k-1)$-竞争的。

证明的方法比较复杂，这里就不展开了。

现实中k-server问题的简单实例

进程调度

• 先来先服务(FCFS)
• 短作业优先(SJF)
• 优先级调度
  • 按新的更高优先级的进程能否抢占正在执行的进程分类：非抢占式优先级调度、抢占式优先级调度
  • 按进程创建后其优先级是否可以改变：静态优先级、动态优先级
• 高响应比优先：是对SJF算法的一种改进，改进点在于作业的优先级随着等待时间的增加而增加，有利于克服“饥饿”现象。作业的优先权由下式定义：$R_p = \frac{\text{等待时间} + \text{要求服务时间}}{\text{要求服务时间}}$，$R_p$又称作响应比。
• 时间片轮转：主要适用于分时系统。时间片的长短通常由以下因素决定：系统的响应时间、就绪队列中的进程数目和系统的处理能力。
• 多级反馈队列：集合了前几种算法的优点

磁盘调度

• FCFS
• 最短寻找时间优先(Shortest Seek Time First, SSTF)
• 扫描(SCAN, 又称电梯算法)
• 循环扫描(Circular SCAN)：扫描算法的一种变形

-----EOF-----