结果族 110：Optimal-order randomized k-server on arbitrary metrics · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
姊妹篇像一张保证书，说”这么省钱的随机调度方案一定存在”；本篇则把车真造出来：对任何一张距离写成分数的有限地图，同一套程序都能先做一次性准备，然后照着方案接单。更妙的是，接到第 t 单时的思考时间只随 t 的”位数”增长——第 10 亿单并不比第 1000 单多想多少。
关键词卡片
看个具体例子
设地图编码长为 L、服务器数 k=15。定理的数字版：第 t 单的思考耗时 @@M@@T(t)\le p\big(L+\lceil\log_2(t+1)\rceil\big)@@，p 是某个固定的多项式。代入 @@M@@t=10^9\approx 2^{30}@@：@@M@@\lceil\log_2(t+1)\rceil=30@@，而 @@M@@t=8@@ 时仅 4——订单量翻了上亿倍，单均思考量只多了约 26。期望花费同样有数字版：@@M@@\mathbb{E}[\text{cost}]\le C\cdot(\log_2 16)^2\cdot\mathrm{OPT}+B=C\cdot 16\cdot\mathrm{OPT}+B@@。
为什么值得关心
存在性定理常被笑称”纸上谈兵”；本篇说明平方对数竞争比不只存在，还能被一台统一的计算机一步步算出来，只是启动亏损 B 可能大得离谱——这是理论上的”能造”，不是性能调优。订单一个接一个到来时，算法既不必预知序列长度，也不必更换程序。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读说姊妹篇是”保证书”、本篇”把车真造出来”。换成半数学的说法：前文只断言存在一份理想的随机调度方案；本文给出一台机器——输入一张距离写成分数的有限地图，它先做一次性的准备，之后每来一个请求就吐出”移动哪个服务器”的指令，指令靠掷无偏硬币产生，且同一套规则通吃一切实例，不随地图偷换程序。
第二级台阶
用本科术语钉死几个概念。一致算法指单一程序处理所有输入，无需预知规模或序列长度；预处理指读入编码后开工前的一次性计算，其耗时以位操作数即位复杂度计量；有理度量是所有 pairwise 距离均为分数的有限度量空间，使机器能精确存储与比较。目标仍是竞争比：期望花费除以事后最优。
第三级台阶
定理在这样的语境下陈述：设输入（点数、服务器数、有理距离、初始位置）的二进制编码总长为 L，则存在单一随机在线算法，预处理至多 p(L) 位操作，服务第 t 个请求至多额外 p(L+⌈log₂(t+1)⌉) 位操作，并对一切与随机比特无关的有限请求序列，期望花费不超过 C·(log(k+1))²·OPT 加一个只依赖实例、不依赖序列的可加项 B。”请求独立于随机比特”挡住自适应对手；”B 不设界”与”计算量随请求计数的位数增长”这两处刻意放宽，挡住的是构造机器运行时间不受控、激活前需用固定标签应付海量请求的麻烦。结论即是导读那句话的严格版：平方对数竞争比可被一致计算实现，但启动亏损可能巨大。
把姊妹篇的存在性定理变成可执行算法：在有理有限度量上，单一一致随机算法经多项式预处理实现 @@M@@O(\log^2(k+1))@@ 竞争比，第 @@M@@t@@ 个请求的计算量仅随 @@M@@\lceil\log_2(t+1)\rceil@@ 多项式增长，代价是可能巨大的实例相关可加项。
姊妹篇证明了任意度量上存在 @@M@@O(\log^2(k+1))@@ 竞争比的随机 @@M@@k@@-server 策略，但其收尾依赖 Tychonoff 紧性论证，属于纯存在性结果：没有给出任何计算决策概率的程序。一个自然的问题随之而来：能否用有限计算和无偏随机比特，把这个保证落实为对所有有限有理度量统一适用的单一在线算法？直接相关的是 Coester–Cosson 的多项式时间实现，但其在一般 @@M@@n@@ 点度量上的竞争比仍带点数因子 @@M@@O(\log n\log^2 k)@@。有限策略综合另有传统：Mömke 把随机策略表为有限线性规划并做有界序列归约，Mikkelsen 发展了有限惰性任务系统的复位构造。本文沿此路线，首次在竞争比不含 @@M@@n@@ 的前提下实现一致计算。
主定理：存在绝对常数 @@M@@C@@ 与多项式 @@M@@p@@，对每个 @@M@@n\ge 3@@、@@M@@2\le k<n@@、集合 @@M@@X=\{1,\ldots,n\}@@ 上的有理度量 @@M@@d@@ 及初始位置组 @@M@@s@@（允许重复），记 @@M@@L@@ 为 @@M@@n,k,d,s@@ 的二进制编码总长，则存在单一一致随机在线算法：预处理至多 @@M@@p(L)@@ 次位操作；服务第 @@M@@t@@ 个请求至多额外 @@M@@p(L+\lceil\log_2(t+1)\rceil)@@ 次位操作；仅用无偏随机比特，每次恰移动一个服务器（允许零长移动）。对所有与随机比特无关的有限请求序列 @@M@@\sigma@@，
@@M@@D\mathbb{E}[\mathrm{cost}_{A,s}(\sigma)]\le C(\log(k+1))^2\,\mathrm{OPT}_s(\sigma)+B_{d,k,s},@@
其中 @@M@@B_{d,k,s}@@ 有限且与 @@M@@\sigma@@ 及其长度无关，算法无需预知序列长度。定理刻意保留两点自由：不对 @@M@@B@@ 的大小作任何界（可能大得离谱）；允许计算量随请求计数的二进制长度增长——算法可先用固定标签服务海量初始请求再切换，此代价全部记入 @@M@@B@@。
第一步把实值概率换成有限有理数据：固定视界 @@M@@H@@，把随机策略写成”前缀–构形边际概率与转移流”的有理线性系统，精确消元求出可行的最优竞争系数 @@M@@a\le C_0(\log(k+1))^2@@——存在性定理只用于保证该系统可行，既不需要知道 @@M@@C_0@@ 的数值，也不查询那个策略本身；再把条件概率舍入为 @@M@@b@@ 位二进小数（@@M@@2^b\ge kH^2@@），期望移动的额外损失不超过度量直径 @@M@@D@@。第二步解决”固定视界约束不了最优几乎不动而请求极长”的困难：请求流按首次凑满第 @@M@@k+1@@ 个不同点切成原生块，任何服务在每个完成块至少移动最小间距 @@M@@\delta@@；@@M@@R=\lceil kD/\delta\rceil@@ 个完成块构成一个纪元，迫使最优至少付 @@M@@kD@@。再设普适截断过滤器（filter）：维护全体”从互异起点出发、正移动不超过 @@M@@M@@ 的强惰性（strongly lazy）服务”的表项；请求若被所有这些服务覆盖则丢弃，否则保留并让未覆盖表项各分裂为 @@M@@k@@ 个子表项。分支树至多 @@M@@H=\sum_{i=0}^{M}k^i@@ 个节点，每个保留请求消耗一个永不复活的节点，故保留字长度恒不超过 @@M@@H@@，与原始流长无关。纪元内先按决策表服务，正移动数一超上限即切换到分页式标记回退（marking fallback），每块至多 @@M@@(k+1)D@@，由纪元积累的最优代价吸收表格重启费。第三步是一致调度：固定一个确定性位机器 @@M@@P@@ 构造上述表格；第 @@M@@t@@ 个请求时从头模拟 @@M@@P@@ 至多 @@M@@g(t)=\lfloor\log_2(t+1)\rfloor@@ 步，未完成就用标签 1 应付当前请求，完成后（激活时刻 @@M@@2^{T_P}-1@@）启用后缀例程；由于 @@M@@P@@ 的输出长度 @@M@@S=O(g(t)+1)@@，查表、过滤更新与 @@M@@b@@ 比特采样的全部位操作都被同一多项式 @@M@@p(L+\lceil\log_2(t+1)\rceil)@@ 控制。激活之前的海量固定标签移动全部进入可加项 @@M@@B_{d,k,s}@@。
本文与存在性篇同属结果族 110，只引用其”互异初始位置、零可加项”条款作可行性证书，不执行也不查询该策略；竞争比与点数 @@M@@n@@ 无关是相对 Coester–Cosson 的关键改进，代价是放弃对启动损失与激活时延的控制。两篇均暂无 Lean 形式化证明；按 OpenAI 官方声明，未经形式化的结果可能有问题。结论节明言遗留问题：启动移动的有用上界，以及仅依赖 @@M@@L@@ 的每请求多项式计算界。
问 1：证明里最脆弱的一环在哪里？
答：最要害的是普适截断过滤器：把”从互异起点出发、正移动不超过上限的强惰性服务”排成一棵深度受控、每节点至多 k 分支的树，声称每个保留请求永久杀死一个活节点，故保留字长度与原始流长无关（引言 Proof ideas 第二、三段）。这个”节点死而不复生”的组合不变量一旦在任何一条路径上失效，后面所有关于有限表格与固定字的论证都会塌掉。其次是纪元记账：每 (k+1) 个不同点构成一块、R 块构成一个纪元迫使最优付 kD——块与过滤字都由原始输入唯一决定，正是这套”随机切换时刻不影响被分析的固定字”的分离结构在支撑全部估计。
问 2：为什么必须允许 B 完全无界？
答：因为构造决策表的那台确定性位机器 P 的运行时间不受控：算法只能在第 t 个请求时从头模拟它 ⌊log₂(t+1)⌋ 步，完成之前一律用固定标签应付请求，这段时间的全部移动进入 B（定理后两段与 Proof ideas 末段明言”延迟激活是无界可加项换来的实现装置”）。若给 B 设多项式界，就等价于给 P 的停机时间设界，而这是现有技术给不出的——结论节把它列为公开问题。
问 3：与 Coester–Cosson 的多项式时间实现相比，真正的新意是什么？
答：交易点不同。Coester–Cosson 在一般 n 点度量上仍是 O(log n·log²k)，且每请求时间与历史长度无关、随机比特极少；本文牺牲这两点（时间允许随 log t 增长、B 无界），换到竞争比与点数 n 无关（History 节直接对比）。这是首个竞争比不含 n 的一致可计算实现。
问 4：这个结果最可能出错的模式是什么？
答：最大的级联风险在依赖链：有限有理线性系统的可行性直接引用姊妹篇的”互异起点、零可加项”条款作证书（History 节强调只用存在性、不用其概率），姊妹篇本身未经形式化，一处坍塌两篇皆倒。其次是位级簿记：把条件概率舍入为二进小数（2^b≥kH²）后的期望损失声称不超过直径 D，以及从固定视界到无界后缀的模式切换，这类精细账目是 AI 生成证明常见的出错点。
问 5：为什么允许每请求时间随 ⌈log₂(t+1)⌉ 增长，而不是常数或 L 的多项式？
答：调度规则是”第 t 单从头模拟 P 共 g(t) 步”，激活时刻约为 2^{T_P}−1；要每请求只花 p(L) 就得给 T_P 设界，而 T_P 依赖精确消元求解线性系统的全过程，目前无界。论文在结论中明言：仅依赖 L 的每请求多项式界是遗留问题。
问 6：谁会用到这个结果？
答：在线算法的可计算性路线：它把 Mömke 的有限策略线性规划、Mikkelsen 的复位构造推进到”竞争比与 n 无关”的设定，为其他在线问题（缓存、租借、任务系统）的”存在性转算法”提供了过滤器加回退加延迟激活的模板。实用层面它是理论上的”能造”，B 可能离谱，不宜直接落地。
总评
本文把平方对数 k-server 从纸上存在性推进到一致可计算，价值在消除 n 依赖；最大风险是其可行性证书整个押在未经形式化的姊妹篇上，且自身放弃了对启动损失与激活时延的一切控制。