k-Server 问题

请求协议与配置 ​

给定度量空间公理库度量空间Metric space配备非负、对称、正定并满足三角不等式的距离函数的集合。 $(X,d)$、服务器数 $k$ 和初始配置 $C_0$。配置是 $X$ 上含重数的 $k$ 元集合；服务器可重合，若模型禁止重合必须另行说明。第 $t$ 轮先揭示请求点 $r_t\in X$，算法随后选择新配置 $C_t$，要求 $r_t\in C_t$。

从 $C_{t-1}$ 变到 $C_t$ 的成本，是旧服务器与新服务器之间最小完美匹配的距离和：

$$D(C_{t-1},C_t)=\underset{\pi \in S_k}{min}\sum _{i=1}^{k}d(x_i,y_{\pi (i)}).$$

标准请求只需把一台服务器移到 $r_t$，但用配置距离写法能消除服务器标签；同一次响应中绕路或额外移动不会比直接匹配更便宜。

若请求点已被占据，可以令 $C_t=C_{t-1}$，本轮成本为零。算法只看见 $r_1,\dots ,r_t$，不能用未来请求决定当前移动；这正是在线协议公理库在线算法模型Online algorithm model输入逐步揭示，算法必须在未知未来时作出通常不可撤回的决策。的约束。

竞争比与量词 ​

固定同一初始配置 $C_0$，令 $ALG(\sigma )$ 与 $OPT(\sigma )$ 分别是在线算法和预知完整序列的离线最小移动成本。确定算法若存在与序列无关的常数 $\beta$，使所有有限序列满足

$$ALG(\sigma )\le cOPT(\sigma )+\beta ,$$

就称为 $c$-competitive。若两侧初态不同，$\beta$ 必须吸收初始配置距离；不写初态便无法比较短序列。

随机算法面对 oblivious 对手时，先固定请求序列，再对算法内部随机性取期望：

$$\mathrm{\forall }\sigma :{\mathbb{E}}_r[AL{G}_r(\sigma )]\le cOPT(\sigma )+\beta .$$

能依据过去随机动作选择下一请求的 adaptive 对手改变了量词，不能直接沿用 oblivious 上界。竞争比的共同定义与势函数账本见竞争分析公理库竞争分析Competitive analysis在同一请求序列上比较在线算法总成本与预知未来的离线最优。。

两台服务器的直线轨迹 ​

在实线度量上，初态为 $C_0=\{0,10\}$，请求依次为 $4,7,2$。一种在线轨迹是：

1. 请求 4 时把 0 处服务器移到 4，付 4，配置变为 $\{4,10\}$；
2. 请求 7 时选择 10 处服务器，付 3，配置变为 $\{4,7\}$；
3. 请求 2 时移动 4 处服务器，付 2，总成本为 9。

第二步若改为把 4 移到 7，只付 3，却留下 $\{7,10\}$，第三步要再付 5。局部成本相同的选择会产生不同未来状态，而在线算法在第二步看不到请求 2；例子的重心不是某组数字，而是“当前服务点的选择同时决定下一轮配置”。

Paging 作为一致度量特例 ​

令 $X$ 是所有页面，任意不同页面距离均为 1，$k$ 台服务器表示缓存中的 $k$ 个页面。请求页已在配置中就是 hit；否则把某台服务器移到请求页，成本 1，对应淘汰一个旧页并装入新页。因此 paging 是 uniform metric 上的 k-server。

这个归约只对应缺页次数模型。若页面大小不同、换入成本不同或缓存有层级，距离未必是一致度量；若迁移成本不满足三角不等式，k-server 的度量论证也不能直接使用。

已知界与开放边界 ​

对至少含 $k+1$ 个点的一般度量，确定性竞争比下界为 $k$。经典 Work Function Algorithm 在一般度量上给出 $2k-1$ 的上界；“是否总存在 $k$-competitive 确定算法”是 k-server conjecture，不能把特殊度量结果写成一般问题已解决。

有限度量、树度量、一致度量和随机算法各有更强的专门结果，使用时必须连同度量类别、点数和对手模型陈述。竞争比只度量总移动距离；计算下一配置所需的时间与空间是另一层算法成本。

实现与建模边界 ​

连续空间中服务器位置可能是实数，但请求只在有限集合上时，最优策略可常规化为只在相关点移动；若允许预测、重新放置或资源增广，比较基准必须同步修改。请求批量揭示也不是同一在线模型。

配置含重数时，不能用普通集合去重；配置距离要解最小匹配，而不是按服务器数组下标逐项相减。证明中给服务器临时命名可以方便描述，但最终成本不应依赖标签排列。

参考资料

• Mark Manasse, Lyle McGeoch, Daniel Sleator, Competitive Algorithms for On-Line Problems, STOC, 1988.
• Elias Koutsoupias, Christos Papadimitriou, On the k-Server Conjecture, Journal of the ACM, 1995.
• Allan Borodin, Ran El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998.