Dailin Li

Dailin Li

Reading, Thinking, Coding

中科大算法分析与设计课程 PPT 精读

45 minutes read

Published:

Note: 本文部分内容由 Gemini 3 Pro 生成，请注意鉴别。

课程资料和部分算法的可视化演示见附录。

分布式算法

生成树上的广播 Broadcast

1. 前置条件与目标

  • 前提：假定网络中已经建立好了一棵生成树（Spanning Tree）。父子关系（parent, children）已经确定。

  • 输入：根节点 $p_r$ 拥有消息 $M$。

  • 输出：网络中所有节点都收到消息 $M$。

2. 算法逻辑 (Algorithm 2.1)

PPT 中给出了伪代码和状态转换描述，核心逻辑非常简单，就是“收到即转发”：

  • 对于根节点 ($p_r$)：

    1. 直接把消息 $M$ 发送给所有孩子节点 (children).

    2. 任务结束，进入终止状态 (terminate).

  • 对于非根节点 ($p_i$)：

    1. 等待 (upon receiving) 从父节点 (parent) 传来消息 $M$。

    2. 一旦收到，立即将 $M$ 转发给自己的所有孩子节点。

    3. 任务结束，进入终止状态。

注意：物理上节点可能有很多连线，但逻辑上它只认生成树上的 parent 和 children 进行通信。

3. 复杂度分析 (重点考点)

PPT 明确给出了消息复杂度和时间复杂度，并强调了该算法在同步和异步模型下表现一致。

A. 消息复杂度 (Message Complexity)

  • 结论：$n-1$，即 $O(n)$。

  • 原理：生成树有 $n$ 个节点，必然有 $n-1$ 条边。算法保证消息 $M$ 在树的每一条边上恰好传输一次（从父到子）。

  • 对应之前的图解：这就是只数“发了几次包”。

B. 时间复杂度 (Time Complexity)

  • 结论：$h$ (或 $d$)，即树的高度 (Height/Depth)，$O(h)$。

  • 原理：广播是一层一层往下传的，最慢的那个节点（最坏情况）也就是树的最深处，所需时间取决于树有多深。

4. 证明逻辑 (数学归纳法)

PPT 花了很大篇幅（Lemma 2.1 和 Lemma 2.3）来证明时间复杂度。这里用到了你之前问的“容许执行” (Admissible Execution) 概念。

  • 同步模型证明 (Lemma 2.1)：

    • 定义：时间按“轮” (Round) 算。

    • 归纳法：

      • 基础：距离根节点 1 的节点（根的孩子），在第 1 轮收到。

      • 假设：距离为 $t-1$ 的节点在第 $t-1$ 轮收到。

      • 推导：因为第 $t-1$ 轮父节点收到了，它会在下一轮发给孩子，所以距离为 $t$ 的节点一定在第 $t$ 轮收到。

    • 结论：总时间 = 树的最大深度 $d$。

  • 异步模型证明 (Lemma 2.3)：

    • 定义：异步系统中，消息延迟在 $(0, 1]$ 之间。为了算最坏情况（Time Complexity），我们假设每一步都用到最大延迟 $1$。

    • 关键词：“至多在时刻 $t$ (at most at time t)”。

    • 逻辑：和同步模型一样，也是通过归纳法证明。如果父节点最晚在 $t-1$ 收到，再加上传输延迟至多为 1，那么子节点最晚在 $t$ 收到。

总结：这张 PPT 在考什么？

如果这是一道考试题，通常会考察以下几点：

  1. 伪代码：让你写出基于生成树的广播算法（参考上面的步骤 2）。

  2. 计算复杂度：问你总共发了多少个消息（$n-1$），最长花了多少时间（树高 $h$）。

  3. 证明：用数学归纳法证明为什么时间复杂度是 $O(h)$。一定要模仿 PPT 中的话术：“对距离 $t$ 使用归纳法…”。

生成树上的敛播 Convergecast

这段 PPT 内容讲解的是汇集（Convergecast），它是广播（Broadcast）的逆过程。如果说广播是“从上往下分发指令”，那么汇集就是“从下往上收集情报”。

为了帮助你应对考试，我将这段内容的逻辑、算法细节和考点提炼如下：

1. 核心概念：自底向上的“信息汇总”

  • 方向：从叶子节点（Leaves）开始，向根节点（Root）流动。

  • 目的：收集所有节点的信息，并在根节点汇总出一个全局结果（例如：求最大值、求和、计数、选举等）。

  • 例子：PPT 中使用的例子是“求最大值 (Global Max)”。

    • 每个节点都有一个初值 $x_i$。

    • 根节点想要知道全网最大的那个 $x$ 是多少。

2. 算法逻辑（以求最大值为例）

这个算法的执行流程非常像公司的“层层汇报”：

  1. 启动者（Initiators）：叶子节点。

    • 因为叶子没有孩子，不需要等任何人。

    • 叶子节点直接把自己的值 $x_i$ 发送给父亲。

  2. 中间层（Internal Nodes）：阻塞等待（Blocking Wait）。

    • 这是算法最关键的一步。

    • 如果节点 $p_j$ 有 $k$ 个孩子，它必须收到所有 $k$ 个孩子的消息后，才能进行下一步。

    • 计算：收到所有孩子的汇报值 ${v_{i1}, …, v_{ik}}$ 后，结合自己的值 $x_j$，计算局部最大值：$v_j = \max(x_j, v_{i1}, …, v_{ik})$。

    • 上报：将算出的 $v_j$ 发送给自己的父亲。

  3. 终结者：根节点。

    • 当根节点收到所有孩子的消息并计算出最大值后，算法结束，根节点得到了全局最大值。

3. 复杂度分析（必考点）

PPT 中给出的定理 Th 2.5 明确了其复杂度与广播完全一致，但原因不同：

  • Msg 复杂度：$n-1$ (即 $O(n)$)

    • 原因：除了根节点（Root）以外，每一个节点都要向它的父节点发送恰好 1 条消息（汇报结果）。

    • 全网 $n$ 个节点，也就意味着有 $n-1$ 次汇报发送。

  • 时间复杂度：$d$ (即 $O(h)$, 树的高度)

    • 原因：这也是由树的深度决定的。信息必须从最深的叶子节点（最底层），一层层处理、汇报，直到爬升到根节点。最长的路径就是树的高度 $d$。

4. 考试重难点

A. “阻塞等待”是考点

考试中可能会让你写伪代码或分析逻辑。一定要强调：非叶子节点必须等到收到“所有”孩子的消息才能上传。

  • 错误写法：收到一个孩子消息就往上发一个。

  • 后果：会导致根节点收到多次中间结果，导致消息复杂度爆炸（远大于 $n-1$），且破坏了算法的定义。

B. 广播与汇集的组合拳 (Broadcast + Convergecast)

PPT 最后提到“用途：初始化某一信息请求，然后用敛播响应”。这是一种非常经典的分布式模式：

  1. Phase 1 (Broadcast): 根节点发令：“大家把手里的数据报上来！”（自顶向下）

  2. Phase 2 (Convergecast): 节点收到命令后，开始采集数据并层层汇总提交。（自底向上）

C. 同步 vs 异步

PPT 提到“存在一个异步的敛播方法”。

  • 在同步系统中：我们可以按轮次来，第 1 轮叶子发，第 2 轮上一层发……直到根。

  • 在异步系统中：我们不需要时钟，依靠“收到所有孩子消息”这个事件来驱动算法运行。这再次证明了该算法的鲁棒性。

总结一张表

特性广播 (Broadcast)汇集 (Convergecast)
方向Root $\to$ Leaves (1对多)Leaves $\to$ Root (多对1)
触发条件收到父节点消息收到所有子节点消息
Msg 复杂度$n-1$$n-1$
时间复杂度$d$ (树高)$d$ (树高)
典型应用发布命令、更新配置收集投票、求和、求最大值

Alg 2.2 构造生成树（若同步为 BFS）

这份 PPT 的内容主要围绕如何在一个没有预设结构的连通网络中，构造出一棵以特定节点 $p_r$ 为根的生成树。

它从最基础的 Flooding（泛洪）算法讲起，逐步演进到具体的生成树构造算法（Algorithm 2.2），并深入分析了其正确性、复杂性以及在同步/异步系统下的不同表现。

以下是 PPT 逻辑的详细梳理：

1. 基础铺垫：Flooding 算法 (泛洪)

在构造树之前，PPT 先介绍了最暴力的消息传播方式。

  • 算法逻辑：

    • 特殊节点 $p_r$ 发送消息 $M$ 给所有邻居。

    • 当节点 $p_i$ 第一次收到 $M$ 时，把它转发给除了发送者以外的所有邻居。

  • 复杂度分析：

    • Msg 复杂度：$O(m)$。因为每条信道（边）最多传输 2 次消息（两端各发一次），总数为 $2m - (n-1)$。

    • 时间复杂度：$O(D)$，其中 $D$ 是网络直径。

2. 核心算法：构造生成树 (Algorithm 2.2)

这是本节的重点，是对 Flooding 算法的改进，增加了建立父子关系的逻辑。

A. 基本思想与握手机制

算法通过消息的确认机制来确定谁是谁的父亲，谁是谁的孩子。

  • 确立关系 (<parent>)：

    • 如果 $p_i$ 收到的 $M$ 是它平生收到的第一个 $M$，那么发送方 $p_j$ 就是它的父亲 (Parent)。

    • $p_i$ 立即回信 <parent> 给 $p_j$，并向其他邻居转发 $M$。

  • 拒绝关系 (<reject>)：

    • 如果 $p_i$ 已经收到过 $M$（说明已经有爹了），又收到了别人发来的 $M$，它就回信 <reject>。

    • 这意味着那条边不是生成树上的边（非树边）。

  • 终止条件：

    • 节点必须等到它发出的所有 $M$ 都收到了回复（无论是 <parent> 还是 <reject>），算法才算在本地终止。

B. 算法流程 (Code for $p_i$)

  • 根节点：发送 $M$ 给所有邻居，设 parent = i（自己）。

  • 非根节点：

    1. 收到第一个 $M$ $\rightarrow$ 认爹，回 <parent>，转发 $M$。

    2. 收到后续 $M$ $\rightarrow$ 回 <reject>。

    3. 收到 <parent> $\rightarrow$ 把对方加入 children 集合。

    4. 收到 <reject> $\rightarrow$ 把对方加入 other 集合。

    5. 当 children $\cup$ other 包含了除 parent 外的所有邻居时 $\rightarrow$ Terminate。

3. 正确性证明 (Correctness)

PPT 用反证法证明了该算法确实能构造出一棵树。

  1. 连通性 (Connectivity)：

    • 证明：假设有节点不可达。由于网络物理上是连通的，必然存在一条边连接“可达集”和“不可达集”。可达的那个节点最终会发 $M$，不可达的节点收到后就会加入可达集。矛盾。

  2. 无环性 (Acyclicity)：

    • 证明：假设有环。父子关系意味着“父亲先收到 $M$，孩子后收到 $M$”。如果有环，意味着 $p_1$ 在自己第一次收到 $M$ 之前就已经收到了 $M$，这在时序上是不可能的。矛盾。

4. 同步 vs 异步模型的区别 (难点与考点)

这是 PPT 中非常关键的一个对比分析。

特性同步模型 (Synchronous)异步模型 (Asynchronous)
树的形状BFS 树 (广度优先搜索树)任意生成树 (Arbitrary Tree)
原因它是按“轮”传播的。第 $t$ 轮收到消息的节点，距离根必定是 $t$。路径一定是最短的。消息速度快慢不一。一条“长链”上的消息可能传得比“短路”更快。
反例N/APPT 给出了 5 个顶点的完全图例子：消息可能沿着 $p_0 \to p_1 \to p_2 \to p_3 \to p_4$ 极速传播，形成一条链，尽管物理直径 $D=1$，但树高 $d=4$。
时间复杂度$O(D)$$O(D)$ (注意：这里的时间是指因果链时间，尽管树高可能是 $O(n)$，但最快的传播路径覆盖全网的时间仍受限于直径)
Msg 复杂度$O(m)$$O(m)$

5. 组合应用：请求与收集 (Request & Collect)

最后 PPT 将构造生成树（向下发）与汇集算法（向上收）结合起来。

  • 总消息复杂度：$O(m + n)$。

    • 构造树消耗 $O(m)$。

    • 汇集消耗 $O(n)$。

  • 总时间复杂度：

    • 同步模型：$O(D)$。因为构造的是 BFS 树，树高 $d \approx D$。

    • 异步模型：$O(n)$。因为构造出的树可能退化成链，树高 $d$ 可能达到 $n$。汇集需要从最底端爬上来，耗时 $O(n)$。

划重点：

  1. 握手过程：一定要搞清楚 <parent> 和 <reject> 什么时候发，这是算法 2.2 的核心。

  2. 异步的“反直觉”：异步构造出来的不是 BFS 树，这会导致树的高度 $d$ 可能远大于网络直径 $D$，进而影响后续在树上跑汇集算法的时间复杂度（从 $O(D)$ 恶化到 $O(n)$）。

  3. 常数因子：构造树比单纯 Flooding 稍微多一点点开销（因为要发确认回执），但在 $O$ 记号下都是 $O(m)$。

Alg 2.3 指定根时构造DFS生成树

这与之前的算法（Alg 2.2）有本质的区别。如果说 Alg 2.2 是“一群人同时喊话”（并行/BFS倾向），那么 Alg 2.3 就是“接力赛跑”或者“走迷宫”（串行/DFS）。

1. 核心差异：并行 vs. 串行

PPT 第 17 页明确指出了它与 Alg 2.2 的最大不同：

  • Alg 2.2 (构造任意/BFS树)：收到消息后，向所有邻居转发。试图同时增加同一层的所有节点（像水波纹扩散）。

  • Alg 2.3 (构造 DFS 树)：收到消息后，只向一个未访问过的邻居转发。每次只加一个节点（像一条贪吃蛇在游走）。

2. 算法逻辑：令牌传递 (Token Passing)

这个算法可以看作是一个“令牌（Token）”在网络中传递的过程。持有“令牌”（消息 $M$）的节点才有资格行动。

状态变量：

  • unexplored：还没联系过的邻居集合。这是 DFS 的核心，就像你走迷宫时手里拿的小本本，记着哪条路还没试过。

流程拆解：

  1. 收到 $M$（第一次，认爹）：

    • 如果你是第一次收到 $M$，发送者就是你的 parent。

    • 立即行动：查看 unexplored。

      • 如果有邻居：选一个 $P_k$，把 $M$ 传给它（继续深入）。

      • 如果没有邻居（死胡同）：给 parent 回复 <parent>（回溯）。

  2. 收到 $M$（非第一次，拒绝）：

    • 如果你已经有爹了，又收到 $M$，说明遇到了回边（Back-edge）。

    • 立即行动：给发送者回复 <reject>。

  3. 收到反馈（<parent> 或 <reject>）：

    • 这是 Alg 2.2 没有的逻辑重点。因为是串行的，你必须等待刚才那个邻居给你反馈，才能决定下一步做什么。

    • 如果收到 <parent>：说明那个邻居认你做爹了，把它加入 children。

    • 后续动作：

      • 看看 unexplored 还有没有人？

      • 有：选下一个，发 $M$（尝试另一条路）。

      • 没有（所有邻居都试过了）：

        • 如果你不是根：给你的 parent 发 <parent>（任务完成，把控制权交还给父亲，回溯）。

        • 如果你是根：Terminate（全网遍历结束）。

3. 复杂性分析（必考点）

PPT 第 20 页给出了结论，这里需要特别注意与之前算法的对比。

指标Alg 2.2 (泛洪/BFS)Alg 2.3 (DFS)为什么？
消息复杂度$O(m)$$O(m)$每条边最多跑 4 次消息：去($M$)、回(Reject/Parent)，双向各一次。
时间复杂度$O(D)$ (同步)$O(m)$这是巨大的性能下降！

  • 为什么时间复杂度是 $O(m)$？

    • 因为是串行的。

    • Alg 2.2 是“千军万马避白袍”，所有节点同时跑。时间取决于路程（直径 $D$）。

    • Alg 2.3 是“孤胆英雄”，同一个时刻网络里只有一个 $M$ 在跑（逻辑上）。它要走遍几乎每一条边，试探每一个节点。所以时间与边数 $m$ 成正比。

    • 注：PPT最后提到时间复杂度太差，可降至 $O(n)$，那是针对特殊优化的算法，但基础 DFS 就是 $O(m)$。

4. 考试中的“坑”与改进

PPT 提到了两个有趣的问题，可能是简答题的考点：

  1. “如何改进使 msg 的复杂性不是 4m？”

    • 思路：现在的逻辑是，即使我知道邻居 $P_j$ 是我的父亲，轮到我遍历邻居时，我可能还会傻乎乎地把 $M$ 发给 $P_j$，然后 $P_j$ 给我回 <reject>。

    • 改进：在初始化 unexplored 时，或者在确定 parent 时，直接把 parent 从 unexplored 集合里踢出去。这样就不会“父子互探”浪费消息了。

  2. 引理 2.10：在异步模型下构造 DFS 树

    • 考点：Alg 2.2 在异步下造不出 BFS 树，但 Alg 2.3 在异步下能造出 DFS 树。

    • 原因：因为 Alg 2.3 严格依赖“应答-发送”的握手机制来控制流程。它不依赖时钟，而是依赖“收到回复”这个事件。无论消息飞多慢，节点都会死等回复，所以顺序绝对不会乱。

总结

Alg 2.3 就是一个由 unexplored 集合驱动的、严格串行的、带有回溯机制的令牌传递过程。记住“一次只发给一个邻居，等回复后再发下一个”，你就掌握了它的精髓。

Alg 2.4 不指定根时构造DFS生成树

这比之前的算法更进了一步：之前的算法假设大家已经有一个共同的领导（根 $p_r$），而现在的算法要求大家一边选领导，一边组建团队（构造树）。

这是一个典型的“优胜劣汰”过程。以下是核心知识点梳理：

1. 核心思想：竞选与吞并

因为没有指定的根，所以每个节点都可以自发醒来，试图成为根（Leader）。

  • ID 为王：每个节点都有一个唯一的 ID。ID 越大，优先级越高（素质分越高）。

  • 扩散机制：节点试图将自己的 ID 像病毒一样传给邻居。

  • 吞并规则：当两个不同的 ID 在某个节点相遇时，发生“战斗”。大 ID 吞并小 ID。

2. 三大冲突处理规则 (必考逻辑)

当节点 $P_i$（当前信奉领袖 $leader_i$）收到邻居 $P_j$ 发来的新领袖 ID $y$ 时，会进行比较：

情况比较结果含义动作 (Action)
1. 吞并$y > leader_i$外来的和尚好念经。新领袖更强。改换门庭：



1. 更新 leader 为 $y$。



2. 认 $P_j$ 为父。



3. 重置 unexplored（关键！为了新领袖，要把所有邻居重新访问一遍）。



4. 继续帮 $y$ 传播。
2. 忽略$y < leader_i$哪来的小喽啰。我现在的领袖更强。无视：



不理会 $y$，停止 $y$ 在这边的传播。等着自己的强领袖 $leader_i$ 的消息传过去覆盖它。
3. 环路$y = leader_i$大水冲了龙王庙。是一家人。回退：



说明遇到了回边（Back-edge）。发送 <already>（相当于 <reject>），告诉对方“我也归顺 $y$ 了，别传了”。

3. 算法流程 (Alg 2.4)

这个算法其实是 Alg 2.3 (DFS) 的多实例并发版。

  • 初始化：醒来的节点把自己当成 Leader (leader := id)，开始尝试构建 DFS 树。

  • 被征服 (Upon receiving higher ID)：

    • 一旦收到比自己当前 Leader 更大的 ID，立马“叛变”。

    • 特别注意：unexplored 被重置为 all neighbors except Pj。这意味着之前的 DFS 进度作废，为了新 Leader，必须重新扫描邻居。

  • 终止：

    • 只有最终的真·Leader（全网 ID 最大的那个节点 $P_m$）会显式终止。

    • 其他节点只是处于“等待命令”的状态（在算法文本中没有显式 terminate，但逻辑上它们已成为树的一部分）。

4. 复杂性分析 (性能代价)

因为存在“推倒重来”的过程，这个算法的开销比指定根的 DFS 大得多。

  • 消息复杂度 (Msg Complexity)：$O(n \cdot m)$

    • 最坏情况下，每个节点都自发唤醒，试图构建一棵树。

    • 每次构建 DFS 树需要 $O(m)$ 的消息。

    • $n$ 个节点轮番上阵（从小到大被吞并），总共就是 $n \times O(m) = O(nm)$。

    • 注：PPT 中提到的 $O(pn^2)$ 是另一种基于节点数的估算，通常考试答 $O(nm)$ 更为准确且通用。

  • 时间复杂度：$O(m)$

    • 尽管消息量大，但从时间上看，最终那个最大的 ID ($P_m$) 像在走迷宫一样遍历全网，其路径长度受限于边数 $m$。

5. 正确性证明思路 (Lemma 2.12)

  • 最终赢家：全网 ID 最大的节点 $P_m$ 最终一定会醒来（自发或被叫醒）。

  • 无敌性：$P_m$ 的 ID 传播出去后，因为它是最大的，根据规则 ①，没有任何节点能拒绝它，也没有任何节点能覆盖它。

  • 结果：最终所有节点的 leader 都会变成 $P_m$，且形成的父子关系构成一棵以 $P_m$ 为根的 DFS 树。

总结

Alg 2.4 就是“谁大听谁的”。

  • 如果不指定根，代价就是消息量暴增（从 $O(m)$ 涨到 $O(nm)$）。

  • 考试坑点：当节点 $P_i$ 收到更大的 ID 时，不仅要换爹，还要重置 unexplored。这意味着它以前做过的探索工作全部白费，必须为新主子重新跑腿。

匿名环

这段 PPT（§3.2）深入探讨了匿名环（Anonymous Ring）中的核心理论限制，特别是“不可能三角”——在匿名、确定性、对称的网络中，无法完成领导者选举。

这部分内容是对刚才“破对称问题”的严谨数学形式化证明。以下是详细解读：

1. 环的形式化模型 (The Ring Model)

首先定义了我们研究的对象是什么：

  • 结构：$n$ 个处理器 $P_0, \dots, P_{n-1}$ 围成一个圈。

  • 方向与标号：

    • 每个节点都有“左手”和“右手”。

    • 左 (Left)：顺时针方向，连接 $P_{i+1}$，信道标号为 1。

    • 右 (Right)：逆时针方向，连接 $P_{i-1}$，信道标号为 2。

    • 注：下标运算都是模 $n$ 的（例如 $P{n-1}$ 的“左”是 $P_0$）。_

  • 为什么研究环？：因为环是最简单的拓扑结构。如果在环上都做不到（下界），那么在更复杂的任意网络上也做不到。

2. 关键术语定义 (必考概念)

这里定义了三个维度的概念，考试中经常会让你辨析：

术语定义通俗理解
匿名 (Anonymous)处理器没有唯一标识符 (UID)。大家都是克隆人，长得一模一样，代码一模一样。
一致性 (Uniform)算法不知道处理器总数 $n$。代码里没有硬编码 if (n == 5) 这样的逻辑。同一份代码能在任意大小的环上跑。
非一致性 (Non-uniform)算法已知处理器总数 $n$。代码里可以利用 $n$。比如针对 3 个人的环写一种代码，针对 4 个人的写另一种。

3. 不可能性定理 (Impossibility Theorem)

PPT 的核心结论是：对于环系统，不存在匿名的领导者选举算法。

为了证明这一点，PPT 采用了一种“杀鸡用牛刀”的反向策略——归约法：

  • 逻辑链条：

    • 如果我们在最有利的条件下（同步 + 非一致性/已知 $n$）都做不到。

    • 那么在更困难的条件下（异步 + 一致性/未知 $n$）肯定更做不到。

  • 证明目标：我们只需要证明“同步环系统中不存在匿名的、非一致性的领导者选举算法”即可。

4. 证明过程：对称性的诅咒

这个证明非常经典，利用了数学归纳法来证明所有节点永远保持“步调一致”。

引理 3.1 (Lemma 3.1)

在匿名同步环的所有容许执行中，对于每一轮 $k$，所有处理器的状态在第 $k$ 轮结束时都是完全相同的。

证明思路 (归纳法)：

  1. 基础情况 ($k=0$)：

    • 一开始大家都是初始状态。因为是匿名的，也没有 UID，所以大家的初始状态 $S_0$ 是一模一样的。

  2. 归纳假设：

    • 假设在第 $k-1$ 轮结束时，所有人的状态都一样，设为 $S_{k-1}$。

  3. 归纳步骤 (推导第 $k$ 轮)：

    • 因为大家状态 $S_{k-1}$ 一样，运行的代码也一样（匿名性质）。

    • 所以，大家决定发出的消息也一样：所有人都向左发消息 $m_L$，向右发消息 $m_R$。

    • 接收阶段：

      • 每个人从左边收到的，是邻居发出的 $m_R$。

      • 每个人从右边收到的，是邻居发出的 $m_L$。

    • 状态转换：

      • 每个人的输入是 ${ \text{收到 } m_R, \text{收到 } m_L }$。

      • 每个人的当前状态是 $S_{k-1}$。

      • 根据状态机函数 $NextState(S_{k-1}, \text{Input})$，大家算出来的新状态 $S_k$ 必然还是一模一样的。

定理 3.2 (结论)

  • 根据引理，无论跑多少轮，所有节点的状态永远相同。

  • 矛盾点：领导者选举算法要求最终有一个节点进入“Leader”状态，其他节点进入“Follower”状态。

  • 推论：如果节点 A 变成了 Leader，那么根据对称性，节点 B、C、D… 也必须同时变成 Leader。

  • 结果：大家都成了 Leader，这违反了“唯一性”，选举失败。

总结

这段 PPT 实际上判了匿名网络的“死刑”（在确定性算法下）：

只要网络是匿名且对称（环）的，且是同步运行的，所有节点就像在这个“无限镜廊”里照镜子，你做什么动作，镜像就做什么动作，永远无法选出唯一的那个“王”。

要想打破这个僵局，必须引入：

  1. 唯一 ID（这就是为什么之前的 Alg 2.4/2.5 能成功）。

  2. 随机化（大家掷骰子，赌运气打破对称）。

  3. 非对称的拓扑结构（如果不是环，是对称性较差的图，可能不需要 ID）。

异步环 LCR 算法：一个 $O(n^2)$ 算法

这段 PPT 进入了异步环（Asynchronous Ring）的深水区，重点讲解了著名的 LCR 算法（由 Le Lann, Chang 和 Roberts 提出）。

这是分布式算法中“领导者选举”最基础、最经典的算法。为了让你能轻松理解，我将这段内容拆解为三个部分：前提设定、算法机制（大鱼吃小鱼）、以及复杂度分析（为什么最坏是 $O(n^2)$）。

1. 前提设定：告别匿名，引入 ID

上一节（§3.2）刚证明了“匿名环选不出领导”。既然匿名不行，这节课（§3.3）一开始就引入了唯一标识符（Unique ID）。

  • 假设：每个处理器 $P_i$ 都有一个独特的 $id_i$。

  • 一致性（Uniform）算法的新定义：

    • 算法代码里不知道环的总人数 $n$。

    • 只要给每个 ID 配上对应的状态机，算法就能跑。这意味代码是通用的，不管你是 3 个人的环还是 100 万人的环，代码逻辑都一样。

2. LCR 算法核心：大鱼吃小鱼

LCR 算法的思想非常简单粗暴，就是“优胜劣汰，强者生存”。这是一个单向通信算法（只向左发，从右收）。

规则逻辑：

  1. 发起（Start）：每个节点醒来后，把自己的 ID 写在纸条上，传给左边的邻居。

  2. 筛选（Filter）：当你收到右边传来的 ID（设为 $id_{recv}$）时，和自己的 ID（$id_{self}$）比一比：

    • 吞噬（Discard）：如果 $id_{recv} < id_{self}$ —— “你比我弱，没资格当领导”。直接把纸条撕了，不转发。

    • 转发（Forward）：如果 $id_{recv} > id_{self}$ —— “你比我强，请通过”。把纸条传给左边的邻居。

    • 加冕（Win）：如果 $id_{recv} == id_{self}$ —— “我的纸条转了一圈回来了！”。说明我比环上所有人都强（否则早被截胡了）。宣布自己是 Leader。

  3. 终止（Terminate）：新 Leader 产生后，发一个 <Leader> 消息转一圈，通知其他人“选举结束，我是老大”。

3. 复杂度分析：为什么是 $O(n^2)$？

这是 PPT 的重点，也是考试计算题的高频考点。

A. 最好情况 (Best Case)

  • 场景：ID 顺着传输方向递增排列（例如 $1 \to 2 \to 3 \to \dots \to n$）。

  • 每个人的 ID 传给左边，立刻遇到比自己大的，立刻被吞噬。只有最大的那个 $n$ 能跑完一圈。

  • 消息数：$O(n)$。

B. 最坏情况 (Worst Case)

PPT 第 18 页专门画图分析了这个情况。

  • 场景：ID 逆序排列（或者说按传输方向递减）。

    • 假设环是 $P_0, P_1, \dots, P_{n-1}$。

    • 传输方向是 $P_0 \to P_{n-1} \to \dots \to P_1 \to P_0$（也就是 $P_0$ 发给 $P_{n-1}$，虽然 PPT 文字说是发给左邻居，但为了凑最坏情况，只要理解为每个 ID 都要跑很远才会被拦住）。

  • 具体过程：

    • 最大 ID ($n-1$)：无人能挡，跑满全场 $n$ 步。

    • 第二大 ID ($n-2$)：它能跑过 $n-3, n-4 \dots 0$，直到撞上 $n-1$ 才被吃掉。跑了 $n-1$ 步。

    • 第三大 ID ($n-3$)：跑了 $n-2$ 步。

    • …

    • 最小 ID (0)：刚出门就被邻居吃掉，跑 1 步。

  • 计算总和：

    \[Total = n + (n-1) + (n-2) + \dots + 1 = \frac{n(n+1)}{2} \approx \Theta(n^2)\]

4. 总结

这段 PPT 实际上在告诉你：

  1. LCR 算法是基于 ID 的，解决了匿名不可能性的问题。

  2. 它的逻辑是单向的“过滤”：只有比当前节点大的 ID 才能通过。

  3. 它的效率不够高：虽然平均情况下是 $O(n \log n)$（PPT 还没讲到，但通常会提到），但在最坏情况下会退化成 $O(n^2)$。

接下来的章节（$O(n \log n)$ 算法）：

因为 $O(n^2)$ 太慢了，后面的 HS 算法（Hirschberg-Sinclair）会引入双向通信和分阶段探测，把复杂度降到 $O(n \log n)$。这节课是给后面的优化算法做铺垫的“反面教材”。

异步环 HS 算法：一个 $O(n\lg n)$ 算法

这段内容介绍的是著名的 Hirschberg-Sinclair (HS) 算法。这是一个用于异步环形网络的领导者选举算法，它通过“更聪明”的消息传递策略，将消息复杂度从 LCR 算法的 $O(n^2)$ 降低到了 $O(n \log n)$。

以下是基于你提供的 PPT 内容整理的算法核心解析：

1. 核心思想与概念

  • 改进思路：LCR 算法的问题在于每个节点都试图把 ID 传遍全网。HS 算法引入了阶段 (Phase) 和邻居 (Neighborhood) 的概念，采用“双向试探”的策略。

  • k-邻居 (k-neighborhood)：

    • 一个处理器 $P_i$ 的 k-邻居是一个集合，包含环上距离它至多为 $k$ 的所有节点。

    • 集合大小为 $2k+1$ 个处理器（左边 $k$ 个 + 右边 $k$ 个 + 自己）。

  • 分阶段执行：

    • 算法按阶段 $l$ ($l=0, 1, 2, …$) 执行。

    • 在第 $l$ 阶段，节点试图成为其 $2^l$-邻居 范围内的临时领袖 (Temporary Leader)。

    • 只有在第 $l$ 阶段获胜（成为临时领袖）的节点，才有资格进入第 $l+1$ 阶段。这意味着随着阶段增加，竞争者（发起者）越来越少。

2. 算法详细流程 (Alg 3.1)

算法通过 probe（探测）和 reply（应答）两种消息来实现。

消息结构

probe 消息包含三个关键域：<probe, id, l, hop>。

  • id：发起者的标识符。

  • l：当前阶段数。

  • hop：跳步计数器，初始为 0，每转发一次加 1。

执行步骤

  1. 初始阶段 (Phase 0)：

    • 每个节点醒来后，向左和向右两个方向各发送一个距离为 $2^0=1$ 的 probe 消息。

  2. 探测阶段 (Phase $l$) 的转发规则：

    • 当节点收到来自邻居的 <probe, j, l, d> 时，比较消息中的 $j$ 和自己的 $id$：

      • 如果 $j = id$：说明消息转了一圈回来了（且未被“没收”），终止算法，宣布自己是 Leader。

      • 如果 $j < id$：说明发起者比自己弱（或者比路径上遇到的某个节点弱），没收 (Confiscate) 此消息，不再转发。

      • 如果 $j > id$：说明发起者比自己强，继续判断跳数：

        • 若 hop ($d$) $< 2^l$：帮它转发到下一个邻居，hop 加 1。

        • 若 hop ($d$) $\ge 2^l$：说明已经到达了该阶段探测的边界（最后一个邻居）。此时不再向前发，而是向回发送 reply 消息给发起者。

  3. 晋级逻辑 (进入下一阶段)：

    • 发起者 $P_i$ 等待回复。

    • 如果 $P_i$ 从左和右两个方向都收到了 reply，说明它在当前 $2^l$-邻域内是 ID 最大的。

    • 于是它成为该阶段的临时领袖，进入阶段 $l+1$，向两个方向发送距离为 $2^{l+1}$ 的新 probe。

3. 复杂性分析 (为什么是 $O(n \log n)$?)

正确性

  • 最大 ID 的节点发出的 probe 消息永远不会被没收（因为它比所有人都大）。

  • 它最终会通过所有阶段，直到消息绕环一周返回自己，成为唯一的 Leader。

消息复杂度证明

算法的总消息数 = 所有阶段的消息数之和。

  1. 单阶段消息上限：

    • 在第 $l$ 阶段，每个发起者最多发送 $4 \times 2^l$ 条消息（向左去 $2^l$ 回 $2^l$ + 向右去 $2^l$ 回 $2^l$）。

  2. 发起者数量上限 (Lemma 3.3)：

    • 这是一个关键引理：在第 $k$ 阶段结束时，存活的临时 Leader 数量至多为 $n/(2^k+1)$。

    • 原因：任何两个在第 $k$ 阶段存活的临时 Leader，它们的 $2^k$-邻域是不能重叠且还要有个缓冲区的（因为如果重叠或相邻，其中一个较小的 ID 就会被另一个较大的 ID 在探测时“击杀”）。所以每 $2^k+1$ 个节点里最多只有 1 个幸存者。

  3. 总消息数计算 (Theorem 3.4)：

    • 由于每次探测距离翻倍 ($2^l$)，总阶段数约为 $\log n$。

    • 第 $l$ 阶段的总消息数 $\approx$ (发起者数量) $\times$ (每人发的消息数)

      \[\approx \frac{n}{2^{l-1}} \times (4 \cdot 2^l) = O(n)\]

    • 每一阶段的消息复杂度都是线性的 $O(n)$。

    • 总共有 $\log n$ 个阶段，再加上最终 Leader 发送的 terminate 消息（共 $4n$ 条）。

    • 因此，总消息复杂度 = $\sum O(n) = O(n \log n)$。

  4. 时间复杂度：

    • 只盯着最终 Leader 看，因为它最终成为 Leader 了算法才能结束。

    • 它从局部 Leader 走向最终 Leader，需要经过 $\lg(n − 1)$ 个阶段，在第 $l$ 个阶段， 它至少需要经过 $2*2l$ 个时刻才能确认自己还保持着局部 Leader 的身份，最终再发送自己是终极 Leader 的通知。

    • 所以时间复杂度是 $\sum_{l=0}^{\lg(n−1)} 2 \cdot 2l + n = 3n − 4 = O(n)$。

总结

HS 算法通过指数级扩大探测范围 ($2^l$) 和 双向确认机制，快速淘汰了大量较小的 ID 节点，避免了 LCR 算法中每个节点都可能跑长途的情况，从而实现了 $O(n \log n)$ 的消息复杂度。

异步环：下界 $\Omega(n \log n)$

这段 PPT 的内容非常硬核，是在严格证明为什么在异步环中，任何基于一致性（Uniform）算法的领导者选举，其消息复杂度（Message Complexity）的下界（Lower Bound）一定是 $\Omega(n \log n)$。

这意味着：不管你设计多么聪明的算法（比如之前的 HS 算法已经做到了 $O(n \log n)$），你也无法做得比 $\Omega(n \log n)$ 更好（例如做到 $O(n)$ 是不可能的）。

证明采用了构造法和递归的思想。以下是通俗易懂的证明逻辑拆解：

1. 核心思路：构造“最坏情况” (Constructive Proof)

证明的目标是构造一个特定的环 $R$ 和一个特定的调度（Schedule），使得算法在这个环上必须发送足够多的消息。

策略：分治法逆向构造

  1. 拆解：假设我们已经知道对于大小为 $n/2$ 的环，最坏情况下至少要发 $M(n/2)$ 条消息。

  2. 拼接：我们把两个大小为 $n/2$ 的环（$R_1$ 和 $R_2$）剪断，然后首尾相连拼成一个大小为 $n$ 的大环 $R$。

  3. 欺骗：因为算法是一致性的（不知道环的大小），且系统是异步的（消息可以无限延迟），我们可以先让 $R_1$ 和 $R_2$ 里的节点以为自己还在原来的小环里，各自跑完所有的“冤枉路”（耗费 $2 \times M(n/2)$）。

  4. 强迫通信：最后，我们连通这两个环的接口，迫使为了选举出全局唯一的 Leader，消息必须穿过接口传遍半个环，产生额外的 $\Theta(n)$ 消息。

最终得到递归公式：

\[M(n) = 2 M(n/2) + \Theta(n)\]

这个递归式的解正是 $M(n) = \Theta(n \log n)$。

2. 关键概念：开调度 (Open Schedule)

  • 定义：如果在某个调度 $\sigma$ 中，环上存在一条边 $e$，在这个调度执行期间，没有任何消息通过这条边（既没发过去也没发过来），那么这个调度叫开调度，边 $e$ 叫开边。

  • 作用：开边就像是一个“切口”。因为没有消息通过它，我们可以随时把这个切口切开，把它和其他环的切口接起来，而不会破坏原本已经在环内部发生的事件逻辑（因为两边的节点本来就没有通过这条边交流）。

3. 证明三步曲 (The 3-Step Construction)

假设我们要证明大小为 $n$ 的环至少需要 $M(n)$ 的消息。我们假设归纳假设对 $n/2$ 成立。

Step 1: 各自为政 (The Independent Executions)

  • 取两个大小为 $n/2$ 的环 $R_1$ 和 $R_2$。

  • 让它们分别执行各自的“开调度” $\sigma_1$ 和 $\sigma_2$。

  • 消息量：$R_1$ 贡献 $M(n/2)$， $R_2$ 贡献 $M(n/2)$。

  • 状态：此时，我们将 $R_1$ 的开边 $e_1$ 和 $R_2$ 的开边 $e_2$ 剪开，用两条新边 $e_p$ 和 $e_q$ 将它们连成大环 $R$。因为 $\sigma_1$ 和 $\sigma_2$ 执行期间没有消息通过开边，所以节点根本不知道环已经变了。它们以为自己还在小环里。

Step 2: 保持静止 (Silent Configuration)

  • 我们运行算法直到系统进入“静止”状态（$\sigma_3$）。

  • 所谓静止，就是除非有新的消息从外部（即通过连接边 $e_p$ 或 $e_q$）传进来，否则内部节点不再自发产生消息。

  • 目的：把系统推到一个临界点，大家都在等消息。

Step 3: 强迫通信 (Forcing Communication)

这是最精彩的一步（Claim 3.8）。

  • 假设全局最大的 Leader ID 在 $R_1$ 里。

  • 此时 $R_2$ 里的所有节点都还不知道 Leader 是谁（因为 Step 1 里它们只看到了 $R_2$ 内部的局部 Leader）。

  • 根据题目要求（所有节点必须知道 Leader ID），必须有消息从 $R_1$ 穿过连接边 ($e_p$ 或 $e_q$) 传给 $R_2$。

  • 技巧：我们在 $e_p$ 和 $e_q$ 两条连接边中，只开放一条（比如 $e_p$），另一条继续保持“断开/阻塞”状态。

  • 因为 $R_2$ 里的节点要得知 Leader，消息必须从 $e_p$ 进来，一路传遍 $R_2$ 的大部分节点。

  • 这会迫使产生额外的 $\approx n/4$ 条消息（$\Theta(n)$ 量级）。

  • 此时，另一条边 $e_q$ 依然没有任何消息通过，所以对于大环 $R$ 来说，它依然是一个“开调度”（$e_q$ 是开边）。这保证了归纳法可以继续向上推导到 $2n$。

总结

  • $\Omega(n \log n)$ 下界并非巧合，而是由递归结构决定的。

  • 证明核心：利用异步延迟（让消息在切口处排队不发）和一致性（节点无法区分环的大小），我们可以把两个“被欺骗”的子环拼起来，让它们先白白浪费消息选出局部 Leader，最后再强迫它们通信选出全局 Leader。

  • 考试重点：理解 $M(n) = 2M(n/2) + O(n)$ 这个递归关系的物理含义。

    • $2M(n/2)$: 两个子环内部的内耗。

    • $O(n)$: 跨环通信的额外开销。

同步环 Non-uniform Alg：上界 $O(n)$

在异步环中，我们已经证明了消息复杂度的下界是 $\Omega(n \log n)$。但是，一旦引入同步（Synchronous）假设（所有节点有时钟，按轮次 Step-by-Step 执行），游戏规则就变了。我们可以利用“时间”来传递信息，从而将消息复杂度降低到惊人的 $O(n)$。

以下是对这段 PPT 核心内容的详细解读，特别是那个 $O(n)$ 算法的原理及最后两个问题的答案。

1. 同步模型的潜力：用“沉默”传递信息

在异步系统中，如果没有收到消息，你不知道对方是“没发消息”还是“消息还在路上”。

但在同步系统中，如果在特定轮次没有收到消息，你可以确定地知道：“对方没发消息”。

这使得我们可以设计出“时间换消息”的策略：

  • 上界（好消息）：存在消息复杂度为 $O(n)$ 的算法。这是最优的（因为至少要通知一圈人，少于 $n$ 不可能）。

  • 代价（坏消息）：虽然省了消息，但时间复杂度可能会变得非常非常大，它不再只依赖于节点数 $n$，而是依赖于 ID 的数值大小。

2. 非均匀算法 (Non-uniform Algorithm) 详解

PPT 介绍的第一个算法是“非均匀”的，意味着所有节点必须知道环的大小 $n$，且必须同时启动。

算法逻辑：按 ID 值排队发言

这个算法的核心思想是：“谁 ID 小，谁先说话；没人说话，就进入下一轮。”

算法将时间划分为若干个 阶段 (Phase)，每个阶段包含 $n$ 个轮次 (Round)。

  • Phase 0（第 $1$ 到 $n$ 轮）：

    • 只有 ID = 0 的节点有资格行动。

    • 如果网络中有 ID 为 0 的节点，它发送消息转一圈，当选 Leader。

    • 如果没有，所有人保持沉默，空转 $n$ 轮。

  • Phase 1（第 $n+1$ 到 $2n$ 轮）：

    • 只有 ID = 1 的节点有资格行动。

    • 如果有，发消息，当选。

    • 如果没有，继续沉默。

  • …

  • Phase i（第 $n \cdot i + 1$ 到 $n \cdot i + n$ 轮）：

    • 只有 ID = i 的节点有资格行动。

执行过程示例

假设环上有 3 个节点，ID 分别为 ${5, 10, 100}$，$n=3$。

  1. Phase 0, 1, 2, 3, 4：这些阶段对应的 ID 都不存在。网络一片死寂，没有任何消息传输。大家只是在默默数轮次。

  2. Phase 5：

    • 轮到了 ID 为 5 的节点。

    • 它发现“现在是 Phase 5，而且我的 ID 是 5”。

    • 它发送一条消息 <Leader, 5>。

    • 这条消息花 $n$ 轮转一圈。

    • 其他节点收到消息后，知道 Leader 产生了，算法终止。

3. 复杂度分析

这是这个算法最极端的特征：

  • 消息复杂度 (Msg Complexity)：$O(n)$

    • 为什么？ 因为在前面的所有空阶段，大家都在“沉默”，发送的消息数为 0。

    • 只有当最小 ID 的那个节点醒来时，它发了一条消息，这条消息被转发 $n$ 次回到原点。

    • 总消息数 = $n$。非常完美。

  • 时间复杂度 (Time Complexity)：$O(n \cdot \min(ID))$

    • 为什么？ 假设最小的 ID 是 $m$。

    • 我们需要干等前 $m$ 个阶段（Phase 0 到 Phase $m-1$），每个阶段耗时 $n$ 轮。

    • 总轮数 $\approx n \times (m+1)$。

    • 缺陷：如果 ID 的数值非常大（比如最小 ID 是 $2^{64}$），即使 $n$ 很小，这个算法也要跑几十亿年。这在实际中是不可接受的，但在理论上证明了 $O(n)$ 消息是可能的。

4. 回答 PPT 最后的问题 (考点解析)

PPT 最后提出了两个关键问题，这是理解该算法设计的核心：

问题 ①：为什么 id 为 i 的节点要在 phase i 发 msg？

  • 答案：为了利用时间同步来区分身份，从而避免显式的 ID 比较。

  • 解析：在匿名或互不知晓 ID 的网络中，节点无法知道谁的 ID 最小。通过“约定”每个 ID 只能在特定的时间窗口（Phase）发送，我们实现了一种隐式的选举：

    • 如果 Phase $i$ 有人发声，说明 $i$ 就是最小值（因为比 $i$ 小的 Phase 都没声音）。

    • 如果大家乱发，就必须像 LCR 算法那样通过消息碰撞（$O(n^2)$）来比大小。

    • 这里是用等待时间换取了消息数量的减少。

问题 ②：为什么每个 phase 要 n 轮？

  • 答案：为了保证较低优先级的节点能收到较高优先级节点的“胜选通知”，从而停止发送自己的消息。

  • 解析：

    • 假设最小 ID 是 $i$，次小 ID 是 $i+1$。

    • 在 Phase $i$ 开始时，节点 $i$ 发出消息。这条消息要在环上走一圈通知所有人“Leader 已经产生了（是 $i$），大家可以洗洗睡了”，这需要 $n$ 轮。

    • 如果 Phase $i$ 的长度小于 $n$（比如只有 $n/2$ 轮）：

      • 节点 $i$ 的消息才走到一半，Phase $i+1$ 就开始了。

      • 此时节点 $i+1$ 还没收到通知，以为前面没人，它也会发出自己的消息。

      • 这样网络里就有了多条消息，消息复杂度就超过 $O(n)$ 了。

    • 因此，必须留足 $n$ 轮，确保高优先级的抑制信号能覆盖全网。

总结

这个算法是一个极端的理论模型：

  • 优点：消息极少 ($n$)。

  • 缺点：时间极长（依赖 ID 值），且需要知道 $n$（非一致性）。

  • 下一步：PPT 后面提到的“均匀算法（弱同步）”将会尝试解决不知道 $n$ 或者不同时启动的问题，通常会通过指数增长的方式来逼近。

同步环 Uniform Alg：上界 $O(n)$

与之前的 Non-uniform 算法相比，它有两个重大突破：

  1. 无需知道环大小 $n$。

  2. 弱同步模型：节点可以在任意轮次醒来（自发或被叫醒），不需要像阅兵一样同时开始。

这个算法非常巧妙，它利用了 “变量速度” (Variable Speeds) 的概念——让小 ID 的消息跑得快，大 ID 的消息跑得慢。

以下是详细解读：

1. 核心思想：不同 ID，不同速度

这是整个算法的灵魂。

  • 唤醒阶段 (Phase 1 / Wake-up Msg)：

    • 当一个节点刚醒来（不管是自然醒还是被叫醒），它发出的第一条消息叫“唤醒消息”。

    • 速度：正常速度（每轮走 1 步）。

    • 目的：赶紧去把所有还在睡觉的节点叫醒。如果一个节点在收到唤醒消息之前还没醒，那它就丧失了选举资格，只能当个“传声筒” (Relay)。只有那些自发醒来的才有资格当 Leader。

  • 延迟阶段 (Phase 2 / Delayed Msg)：

    • 一旦消息到达了一个已经醒着的节点，它就变身了。

    • 规则：源自 ID 为 $i$ 的消息，在每个节点转发前，必须滞留 $2^i - 1$ 轮。

    • 速度：每 $2^i$ 轮才能走一步。

    • 结果：ID 越小，$2^i$ 越小，跑得越快；ID 越大，$2^i$ 越大，跑得越慢（几乎是在爬）。

2. 算法流程 (Alg 3.2)

  • 初始化：

    • waiting 集合：用来存放那些正在“坐牢”（被延迟）的消息。

    • asleep：标记是否醒来。

  • 收到消息后：

    • 如果之前在睡觉：醒来 (asleep=false)。如果是被消息叫醒的，min=infinity（失去资格）。

    • 没收规则：

      • 如果收到的 ID m < min（比我见过的最小 ID 还小）：说明这是个强力候选人，更新 min=m，并把这个消息加入 waiting 列表开始延迟计时。

      • 如果收到的 ID m > min：吞并（Swallow）。比我见过的最强者还弱，没必要传了。

      • 如果 m = id：我是 Leader！

  • 发送规则：

    • 检查 waiting 里的消息。如果某个消息已经滞留够了 $2^m - 1$ 轮，把它放出来发给左邻居。

3. 复杂性分析（为什么是 $O(n)$?）

证明过程非常繁琐，PPT把它分成了三类消息来算总账。

  • 第一类消息 (唤醒消息)：

    • 这是在第一阶段（大家都还没醒透）跑的消息。

    • 上限：$n$。

    • 原因：每个节点最多只转发 1 个唤醒消息。因为一旦转发过，它就醒了，之后的都是第二阶段消息。

  • 第二类消息 (早期淘汰赛)：

    • 定义：在最终 Leader 的消息进入第二阶段之前，其他输家发出的消息。

    • 上限：$n$。

    • 计算技巧：利用级数求和。因为 ID 为 $i$ 的消息每 $2^i$ 轮才发一次，所以在有限的 $n$ 轮里，它发的次数很少。所有 ID 加起来不超过 $n$。

  • 第三类消息 (终局之战)：

    • 定义：在最终 Leader 的消息进入第二阶段之后，所有还在跑的消息。

    • 上限：$2n$。

    • 计算技巧：同样利用速度差异。Leader (ID=0) 跑得飞快，那些大 ID (ID=k) 还在慢吞吞地爬。在 Leader 跑完一圈的时间里，大 ID 根本跑不了几步。

    • 公式推导结果显示总和 $\le 2n$。

  • 总消息复杂度：$n + n + 2n = 4n$，即 $O(n)$。

4. 思考题解答

PPT 最后留了两个思考题，也是考试可能的简答题：

(1) 为何非唤醒 msg 要延迟 $2^i - 1$ 轮？

  • 答案：为了制造速度差，从而抑制大 ID 的消息传播。

  • 解析：如果不延迟，所有 ID 的消息都疯跑，那就是 $O(n^2)$（像 LCR 算法）。通过让大 ID 延迟指数级时间，我们可以保证小 ID（Leader）在跑完一圈宣布胜利之前，大 ID 们只跑了很短的距离就被 Leader 的消息“追尾”并消灭了。这直接把消息量从 $n^2$ 压到了 $n$。

(2) 如何修改算法 3.2 来改善时间复杂度？

  • 现状：当前时间复杂度是 $O(n \cdot 2^{min_id})$。如果最小 ID 很大，时间会很久。

  • 改进思路：

    • 方案 1：引入 Relay（中继）状态

      核心思路： “只有竞争者需要思考（延迟），路人只管传话（不延迟）。”

      • 原算法的问题：

        • PPT 中提到，第二阶段的消息在每一个节点（无论该节点是否醒着，是否参与竞选）都要延迟 $2^i-1$ 轮。

        • 这就好比：不仅候选人要犹豫，连负责送信的邮递员每走一步都要在原地等上 $2^i$ 分钟，这显然浪费时间。

      • 改进逻辑：

        • 我们将节点分为两类：

          1. 参与者 (Participant)：自发唤醒的节点，试图成为 Leader。

          2. 中继者 (Relay)：被唤醒的节点，或者已经淘汰的节点。

        • 新规则：消息只有在经过参与者时才需要延迟 $2^i$ 轮（为了让更小的 ID 有机会追上来）；而在经过中继者时，立刻转发（只消耗 1 轮传输时间）。

      • 复杂度推导：

        • 假设总节点数为 $n$，其中有 $N$ 个是自发唤醒的参与者（$N \le n$）。

        • 消息绕环一圈，会经过 $N$ 个参与者，和 $n-N$ 个中继者。

        • 原时间：$n \times 2^i$ （所有 $n$ 个点都延迟）。

        • 新时间：$N \times 2^i + (n - N) \times 1$。

        • 当 $N$ 很小时（参与者少），提升非常明显。

    • 方案 2：修改延迟函数 $f(id)$

      核心思路： “不要以此消彼长，改用更温和的刹车（延迟）。”

      这是一种典型的 时间-空间权衡。

      • 原算法的权衡：

        • 延迟函数 $f(id) = 2^{id}$ （指数级）。

        • 效果：跑得慢的（大 ID）被跑得快的（小 ID）迅速消灭。

        • 结果：消息极少 $O(n)$，但时间极慢 $O(n \cdot 2^{id})$。

      • 改进逻辑：

        • 如果我们把延迟函数改成线性的，比如 $f(id) = c \cdot id$。

        • 时间复杂度：降低了。最坏时间变成了 $O(n \cdot id)$，比指数级快多了。

        • **代价：提高了 msg 复杂度”。

        • 因为：延迟变短了 -> 大 ID 跑得快了 -> 在被小 ID 追上之前，大 ID 跑的距离更远了 -> 网络中被转发的消息总数增加了。

同步环 基于比较的算法：下界 $\Omega(n \log n)$

这一节的内容非常深入且理论化，旨在论证为什么“只要算法是基于比较的（Comparison-based），无论你怎么设计，其消息复杂度下界一定是 $\Omega(n \log n)$”。

这直接打破了之前同步算法可以做到 $O(n)$ 的幻想——那个 $O(n)$ 算法之所以能做到，是因为它作弊了（它利用了 ID 的数值来编码时间，不仅仅是比较 ID 大小）。如果我们禁止这种作弊行为，回到纯粹的比较（谁大谁小），那么 $\Omega(n \log n)$ 这个魔咒又回来了。

这段 PPT 充满了形式化定义和引理。为了帮助你理解，我将核心逻辑拆解为以下几个关键步骤：

1. 核心定义：什么是“基于比较的算法”？

PPT 花了很大篇幅（第 25-29 页）来定义这个概念。

  • 直观理解：算法只关心 ID 的相对大小（谁比谁大），而不关心 ID 的具体数值（是 100 还是 1000）。

  • 形式化定义：

    1. 序等价 (Order Equivalent)：如果两个环 $R_1$ 和 $R_2$ 的节点 ID 排列顺序是一样的（例如 $R_1=[10, 50, 20]$，$R_2=[1, 5, 2]$，虽然数值不同，但 $10<20<50$ 和 $1<2<5$ 的相对关系一致），那么这两个环是“序等价”的。

    2. 行为相似 (Similar Behavior)：如果两个环序等价，那么算法在这两个环上应该做出完全相同的动作（比如都在第 3 轮发消息，都在第 5 轮选出 Leader）。

    3. 基于比较：如果在所有序等价的环上，算法的行为都相似，那么这个算法就是基于比较的。

这为什么重要？

因为这限制了算法的能力。算法不能说“如果我的 ID 是 5，我就等 5 秒”。它只能说“如果我的 ID 比邻居小，我就闭嘴”。

2. 核心工具：k-邻居与主动轮 (k-neighborhood & Active Round)

为了证明下界，我们需要度量节点获得了多少信息。

  • k-邻居：节点 $P_i$ 左右各延伸 $k$ 步所看到的局部视野。

  • 主动轮 (Active Round)：

    • 在同步系统中，很多轮次可能大家都在沉默（没有发消息）。

    • 主动轮是指至少有一个节点发送消息的那些轮次。

    • 关键点：信息只有在主动轮里才能传播。一个节点在经历 $k$ 个主动轮后，最多只能知道它 $k$-邻居范围内的信息（因为信息传播速度限制）。

Lemma 3.16 & 3.17 的含义：

这两个引理证明了一个直观的结论：如果两个节点（不管是在同一个环还是不同的环）看到的 $k$-邻居视野是一样的（或序等价的），那么在前 $k$ 个主动轮里，它们的行为必须是一模一样的。

3. 构造下界：高度对称的环 $S_n$

这是证明中最精彩的部分（第 38-43 页）。为了让算法“痛苦”，我们需要构造一个环，使得环上有很多节点的局部视野看起来是一样的。

构造方法：二进制逆序 (Bit Reversal)

  • 对于节点 $i$ ($0 \le i < n$)，其 ID 不是 $i$，而是 $rev(i)$。

  • $rev(i)$：把 $i$ 的二进制表示倒过来读。

    • 例如 $n=8$ (3位二进制)。

    • $1$ 的二进制是 001 -> 倒过来是 100 -> $rev(1) = 4$。

    • $3$ 的二进制是 011 -> 倒过来是 110 -> $rev(3) = 6$。

为什么用这个？

这个构造生成的环 $S_n$ 具有极高的自相似性。

  • 引理 3.19 (PPT 未详述但被引用)：在这个特殊的环 $S_n$ 中，对于任意小的 $k$（只要 $k \le n/8$），环上会有大量（超过 $n/k$ 个）节点的 $k$-邻居视野是序等价的。

4. 最终证明逻辑 (The Grand Finale)

结合上述所有工具，我们可以推导出 $\Omega(n \log n)$：

  1. 只要视野一样，行为就一样：在环 $S_n$ 上，因为有 $\approx n/k$ 个节点的 $k$-邻居视野看起来一样。

  2. 大家一起发消息：根据 Lemma 3.17，如果在第 $k$ 个主动轮里有一个节点发消息，那么这 $\approx n/k$ 个“克隆人”也会同时发消息。

  3. 计算总和：

    • 在第 $1$ 个主动轮，至少 $\approx n/1$ 个消息。

    • 在第 $2$ 个主动轮，至少 $\approx n/2$ 个消息。

    • …

    • 在第 $k$ 个主动轮，至少 $\approx n/k$ 个消息。

  4. 求和：

    \[Total \approx \sum_{k=1}^{n} \frac{n}{k} = n \sum_{k=1}^{n} \frac{1}{k} \approx n \ln n\]

    • 这就是著名的调和级数求和。

    • 结论：总消息数至少是 $\Omega(n \log n)$。

总结

这段 PPT 实际上是在告诉我们：

  1. 没有捷径：如果你只能比较 ID 大小（不能利用 ID 数值做哈希或计时），那么你就无法打破对称性带来的冗余。

  2. 对称性的代价：在高度对称的环（如 $S_n$）中，很多节点会误以为自己处在相同的环境中，从而做出相同的动作（发消息），导致消息量爆炸。

  3. $\Omega(n \log n)$ 是铁律：无论是异步还是“受限的同步”（基于比较或时间受限），这个下界都存在。只有利用 ID 数值的非均匀同步算法（上节课那个 $O(n)$）才能打破这个限制。

考试要点：

  • 理解 基于比较 的定义（序等价）。

  • 理解 主动轮 的概念（只有发消息的轮才算数）。

  • 记住结论：基于比较的算法下界是 $\Omega(n \log n)$。

同步环 时间受限算法：下界 $\Omega(n \log n)$

这段 PPT 介绍了时间受限算法 (Time-Bounded Algorithm) 在同步环形网络中的消息复杂度下界。

核心结论是：即使算法的时间复杂度与 ID 无关（仅受限于环大小 $n$），只要它能解决领导者选举问题，它的消息复杂度下界依然是 $\Omega(n \log n)$。

1. 为什么需要这一节？

  • 背景：前几节展示了一个消息复杂度 $O(n)$ 但时间复杂度依赖于 ID 大小的算法（$O(n \cdot 2^{ID})$）。

  • 问题：我们能否设计一个既省消息（接近 $O(n)$），又省时间（时间只跟 $n$ 有关，跟 ID 无关）的算法？

  • 答案：不可能。 这一节就是证明这个“不可能”。它指出，只要你限制了时间（不让它随 ID 无限增长），你就必须付出 $\Omega(n \log n)$ 的消息代价。

2. 核心定义

  • 时间受限 (Time-Bounded) [Def 3.4]:

    • 算法的运行时间 $r(n)$ 只依赖于环的大小 $n$，而与具体的 ID 数值无关。

    • 即使 ID 取自无限的自然数集合 $\mathbb{N}$，算法也必须在有限的 $r(n)$ 轮内终止。

  • 基于 t-比较 (t-Comparison Based) [Def 3.5]:

    • 如果一个算法在前 $t$ 轮的行为只取决于 ID 的相对大小（序等价），而与具体数值无关，那它就是“基于 t-比较”的。

    • 直观理解：如果算法被迫在 $t$ 轮内结束，它就来不及利用 ID 的具体数值（比如利用 ID 来计时），只能退化成“比大小”的游戏。

3. 证明思路：Ramsey 定理的降维打击

证明的核心逻辑是“归约 (Reduction)”：

我们将“时间受限算法”归约为“基于比较的算法”。既然我们已经证明了基于比较的算法下界是 $\Omega(n \log n)$，那么时间受限算法也逃不掉。

证明步骤：

  1. 利用 Ramsey 定理 (Lemma 3.22)：

    • Ramsey 定理：在足够大的集合中，总能找到一个高度有序的子集。

    • 应用：虽然自然数集合 $\mathbb{N}$ 很大，算法 $A$ 可能会对不同的 ID 数值有不同的处理逻辑。但是，Ramsey 定理告诉我们，一定存在一个巨大的 ID 子集 $C_n$（大小为 $n^2 + 2n$），在这个子集里，算法 $A$ 的行为表现得像是一个在前 $r(n)$ 轮内“只会比大小”的算法（基于 $r(n)$-比较的算法）。

    • 结果：对于来自 $C_n$ 的 ID，算法 $A$ 退化成了基于比较的算法。

  2. 映射与构造 (Theorem 3.23)：

    • 我们构造一个新的算法 $A’$。当 $A’$ 处理 ID $i$ 时，它模拟原算法 $A$ 处理 ID $c_i$（$C_n$ 中的第 $i$ 个数）的行为。

    • 因为 $A$ 在 $C_n$ 上表现得像基于比较的算法，所以 $A’$ 就是一个标准的基于比较的算法。

    • 根据之前的 Theorem 3.18（基于比较的算法下界是 $\Omega(n \log n)$），$A’$ 至少发送 $\Omega(n \log n)$ 条消息。

    • 因为 $A’$ 只是 $A$ 的一个映射，所以原算法 $A$ 在处理 $C_n$ 这个特定子集时，也至少发送 $\Omega(n \log n)$ 条消息。

4. 总结与启示

这段证明揭示了分布式算法中的一个深刻权衡（Trade-off）：

  • 如果要消息少 ($O(n)$)：你必须利用 ID 的数值来换取时间（像之前的 $O(n \cdot 2^{ID})$ 算法），导致时间可能无限长。

  • 如果要时间短 (只与 $n$ 相关)：你不能充分利用 ID 的数值信息（被 Ramsey 定理限制），只能退化成比较 ID 大小，从而导致消息复杂度至少是 $\Omega(n \log n)$。

结论：在同步环中，时间效率和消息效率不可兼得。你要么忍受极慢的运行速度，要么忍受较高的通信开销。

因果关系

这段PPT的内容主要讲解了分布式系统中的因果关系（Causality），特别是著名的Happens-Before关系。这是理解分布式系统如何定序（Ordering）的基石。

以下是这段PPT的详细解读：

1. 为什么我们需要因果关系？（物理时钟不可靠）

PPT首先解释了为什么在分布式系统中，我们不能依赖物理时间（墙上时钟）来同步事件。

  • 相对论影响（物理层面的不确定性）：

    举例张三和李四，即使使用了同步时钟，如果李四以接近光速移动，时间会发生相对论效应（时间膨胀）。当李四的表显示5点时，张三可能已经等了很久了。这说明相对速度不同会导致时钟漂移，物理时间不可靠。

  • 计算机系统的不确定性（系统层面的不确定性）：

    现代计算机非常复杂，存在CPU竞争、中断（Interrupts）、页错误等机制。这意味着即使两个机器收到相同的信号（如赛跑的小旗），它们的执行时间也是无法预料的，不可能指望它们在物理上的“同一时刻”做出反应。

结论： 我们无法在物理时间上观察到一个全局一致的状态。因此，必须寻找另一种机制来定序，即因果相关（Causality）。

2. 基本定义

为了描述因果关系，PPT定义了以下符号：

  • P：处理器（节点）的集合 ${P_1, P_2, \dots, P_n}$。

  • E：所有事件的集合。$E_p$ 表示在处理器 $p$ 上发生的所有事件。

  • 定序（Ordering）：

    • 本地序 ($<_p$)：在同一个节点 $p$ 上，事件是有先后顺序的（全序）。

    • 消息序 ($<_m$)：如果 $e_1$ 发送消息，$e_2$ 接收该消息，则 $e_1$ 一定在 $e_2$ 之前发生。

3. Happens-Before 关系 ($\rightarrow$ 或 $<_H$)

这是分布式系统中最核心的概念（通常称为Lamport因果关系）。它通过传递闭包将本地序和消息序结合起来。

Happens-Before 关系遵循三条规则：

  • 规则 1（本地顺序）： 如果 $e_1$ 和 $e_2$ 在同一个处理器上，且 $e_1$ 先于 $e_2$ 执行，则 $e_1 \rightarrow e_2$。

  • 规则 2（消息传递）： 如果 $e_1$ 发送消息 $m$，而 $e_2$ 接收该消息 $m$，则 $e_1 \rightarrow e_2$。

  • 规则 3（传递性）： 如果 $e_1 \rightarrow e_2$ 且 $e_2 \rightarrow e_3$，则 $e_1 \rightarrow e_3$。

重要特性：

  • 偏序关系： $<_H$ 是一种偏序关系。这意味着并不是所有的事件都可以比较。

  • 并发（Concurrency）： 如果两个事件 $e$ 和 $e’$，既没有 $e \rightarrow e’$，也没有 $e’ \rightarrow e$，则称这两个事件是并发的。它们之间没有因果依赖。

4. H-DAG（Happens-Before 有向无环图）

为了形式化描述，我们可以将这种关系画成一个有向无环图（DAG）：

  • 顶点（Nodes）： 事件集合 $E$。

  • 边（Edges）： 如果存在本地执行顺序 ($<_p$) 或消息传递关系 ($<_m$)，则画一条有向边。

总结： 这段内容的核心思想是，在没有完美物理时钟的分布式系统中，我们利用“消息发送一定早于接收”这一公理，构建了一个逻辑上的时间顺序（Happens-Before），用来代替不准确的物理时间。

Lamport 时间戳

这段 PPT（§4.2.1）介绍的是分布式系统中大名鼎鼎的 Lamport 逻辑时钟（Lamport Timestamps）。

它是为了解决上一节提到的物理时钟不可靠问题而诞生的。它的目标很简单：既然物理时间靠不住，那我们就造一个“逻辑时间”，只要能体现出事件的先后因果顺序（Happens-Before）就行。

以下是核心知识点拆解：

1. 为什么要设计这个算法？

  • 目标：把松散的“偏序关系”（Partial Order，即上一节的 H 关系）变成严格的“全序关系”（Total Order）。

  • 作用：比如在资源分配（互斥锁）中，如果不分个绝对的先来后到，就会乱套。我们需要给每一个事件都打上一个独一无二的标签，让大家排好队。

2. 算法核心逻辑（必考点）

Lamport 算法不依赖绝对时间，而是依赖计数器。

  • 三个角色：

    1. 节点（进程）：每个人手里有一个计数器 my_TS（初始化为 0）。

    2. 事件：发生事件 $e$，就给它贴个标签 e.TS。

    3. 消息：发消息 $m$ 时，把当前的时间戳 m.TS 带在身上传出去。

  • 计数规则（Slide 18）：

    这是算法的灵魂，像两人对表一样：

    1. 发生本地事件：计数器加 1 (my_TS++)。

    2. 发送消息：先加 1，然后把新值贴在消息上发出去。

    3. 接收消息（最关键）：

      • 当你收到一条消息，上面写着时间 m.TS。

      • 你看一眼自己的表 my_TS。

      • 同步逻辑：取两者中的最大值 max(m.TS, my_TS)。

      • 推进一步：在最大值的基础上再加 1。

      • 通俗理解：如果收到的信是“2025年”写的，而你以为现在是“2024年”，那你必须立马把日历翻到“2026年”，以保证你收到信的时间肯定晚于写信的时间。

      Initially：my_TS=0; 
      On event e： 
          if ( e是接收消息m ) then 
              my_TS = max ( m.TS, my_TS ); //取msg时戳和节点时戳的较大者作为新时戳 
          my_TS++; 
          e.TS＝my_TS; //给事件e打时戳 
          if ( e是发送消息m ) then 
              m.TS＝my_TS; //给消息m打时戳

3. 因果性保证（Slide 19）

这个算法保证了一个性质：

  • 若 $e_1 \rightarrow e_2$（因果上 $e_1$ 在先），则 $TS(e_1) < TS(e_2)$。

    • 因为本地事件会 +1，发消息到收消息也会至少 +1，所以时间戳一定会增长，不会倒流。

4. 解决“撞车”：扩展的全序（Slide 20）

  • 问题：如果有两个互不相干的节点（并发事件），它们可能刚好都把计数器加到了 5。这时候谁在前谁在后？

  • 解决方案：“拼爹”（拼节点 ID）。

    • 改进后的时间戳格式：时间.ID（如 PPT 中的 4.3）。

    • 比较规则：先比时间戳大小；如果时间戳一样，再比节点 ID 大小。

  • PPT 里的例子（事件 $e_8$）：

    • 节点 ID = 3。

    • 当前自己的 my_TS = 1。

    • 收到的消息 m.TS = 3。

    • 计算：max(3, 1) + 1 = 4。

    • 最终结果：时间是 4，ID 是 3 $\rightarrow$ 标记为 4.3。

总结

Lamport 时间戳的精髓在于：它不代表真实的物理时间，它只代表“逻辑上的进度”。

通过 max + 1 的操作，它强行把所有因果相关的事件拉开距离，保证了“果”的时间戳一定大于“因”。

向量时间戳

这部分 PPT (§4.2.2) 主要介绍了 向量时间戳 (Vector Timestamp, VT)。它的出现是为了解决 Lamport 时间戳无法准确判定两个事件是否“并发”的缺陷，并用于检测分布式系统中的“违反因果关系”错误。

以下是这段 PPT 的详细解读：

1. 为什么我们需要向量时间戳？(Lamport 的缺陷)

PPT 开篇指出 Lamport 时间戳有一个致命的逻辑不对称性：

  • 如果事件 $e1$ 因果上先于 $e2$ ($e1 \rightarrow e2$)，那么 $e1$ 的时间戳一定小于 $e2$。

  • 但是，如果 $e1$ 的时间戳小于 $e2$，不能推导出 $e1$ 因果上先于 $e2$。它们可能是互不相关的并发事件。

因此，仅靠 Lamport 时间戳，我们无法画出准确的事件关系图，也无法判定两个事件是否真的有因果联系。

2. 核心案例：对象迁移中的“违反因果”

PPT 使用了一个生动的例子来说明如果无法捕捉因果关系，会发生什么错误：

  • 场景：

    1. 迁移：P1 把对象 O 发送给 P2 (消息 M1)。

    2. 通知：P1 告诉 P3 “对象 O 现在在 P2 那里” (消息 M2)。

    3. 请求：P3 收到通知后，向 P2 请求访问对象 O (消息 M3)。

  • 故障 (Bug)：

    • 在网络中，消息 M3 (请求) 比 消息 M1 (对象本身) 先到达 了 P2。

    • P2 收到请求时，对象 O 还没运到。于是 P2 报错说“查无此对象”。

  • 本质原因：

    • 在因果上，M1 应该先于 M3 ($M1 \rightarrow M3$)。

    • 但在 P2 的物理接收顺序上，M3 先于 M1 ($r(M3) < r(M1)$)。这就是违反因果序。

3. 解决方案：向量时间戳 (VT)

为了检测这种错误，我们需要一种机制，满足：当且仅当 $e1.VT < e2.VT$ 时，事件 $e1$ 因果先于 $e2$。

3.1 什么是向量时间戳？

它不再是一个整数，而是一个整数数组。

  • 数组长度等于系统中节点的个数。

  • VT[i] = k 表示：当前节点知道在节点 i 上已经发生了 k 个事件。

3.2 算法实现

每个节点维护一个局部向量 my_VT，初始全为 0。

  • 发生本地事件：把自己位置的计数器加 1 (my_VT[self]++)。

  • 发送消息：把自己位置的计数器加 1，把自己的 my_VT 附在消息上发出去。

  • 接收消息：

    1. 对比消息里的向量 m.VT 和自己的 my_VT。

    2. 对每一位取最大值：my_VT[i] = max(m.VT[i], my_VT[i])。

    3. 把自己位置的计数器加 1。

Initially：my_VT=[0,…,0]; 
On event e： 
	if ( e是消息m的接收者 ) then 
		for i=1 to M do //向量时戳的每个分量只增不减 
			my_VT[ i ] = max( m.VT[i], my_VT[i] ); 
			my_VT[ self ]++; //设变量self是本节点的名字 
	e.VT＝my_VT; //给事件e打时戳 
	if ( e是消息m的发送者 ) then 
		m.VT＝my_VT; //给消息m打时戳

4. 如何判定关系？(核心逻辑)

有了向量，我们就可以精确判定两个事件的关系：

  • 因果先后 ($e1 \rightarrow e2$)：如果 V1 的每一位都小于等于 V2 的对应位，且至少有一位严格小于，则 V1 因果先于 V2。

  • 并发 ($e1 || e2$)：如果 V1 既不小于 V2，V2 也不小于 V1（即有的位 V1 大，有的位 V2 大），则两者并发。这是 Lamport 时间戳做不到的。

5. 回到案例：如何检测错误？

PPT 最后展示了如何用 VT 解决之前的对象迁移 Bug：

  • P2 的视角：

    • P2 先收到了 P3 的请求 M3，其时间戳为 (3, 0, 3)。

    • 后收到了 P1 的对象 M1，其时间戳为 (1, 0, 0)。

  • 检测逻辑：

    • 比较向量：(1, 0, 0) < (3, 0, 3)。

    • 结论：M1 在因果上必须先于 M3。

    • 但实际接收顺序是 M3 先到。P2 一看 M3 的时间戳，发现它依赖的 M1 还没到（违反了因果序），系统就可以通过缓存 M3 等待 M1 到达来避免报错。

总结

这部分 PPT 讲述了利用向量时间戳来捕捉分布式系统中的并发关系和因果依赖，从而能够检测并处理由于网络延迟导致的消息乱序（违反因果关系）问题。

因果通信

这段 PPT (§4.2.3) 主要讲解了分布式系统中的因果通信 (Causality Communication)。它的核心目的是解决网络中消息乱序到达的问题，确保应用层接收消息的顺序符合“因果关系”。

简单来说，如果消息 A 导致了消息 B（即 A $\rightarrow$ B），那么接收者必须先处理 A，再处理 B，即使网络先把 B 送到了。

以下是详细解读：

1. 核心理念：抑制与缓冲

  • 问题：网络传输是不可控的，处理器无法选择消息到达物理网卡的顺序。

  • 解决：我们不能改变“到达顺序”，但可以改变“传递（Deliver）给应用程序的顺序”。

  • 手段：如果发现一个消息来得太早（它的“因”还没到），就把它先缓冲（Buffer） 起来，也就是抑制（Delay） 它的传递，直到它所有的“前驱”消息都到齐了，再按顺序提交给应用。

  • 对比 FIFO：

    • FIFO（如 TCP）只保证同一个发送者的消息有序（利用序列号）。

    • 因果通信要保证整个系统中所有节点的因果有序（利用向量时间戳）。

2. 核心数据结构

为了实现这一点，算法在每个节点 $P$ 上维护了两个关键数组：

  1. earliest[1..M]：

    • 这是一个“预估表”。earliest[k] 记录了本地节点认为节点 $k$ 下一个将要交付的消息的时间戳下界。

    • 换句话说，它代表了本地节点目前对全局进度的“期待值”。

  2. blocked[1..M]：

    • 这是一个“候车室”。blocked[k] 是一个队列，用来存放从节点 $k$ 收到的、但还不能立即交付的乱序消息。

3. 算法流程 (Alg. Causal Msg delivery)

当节点收到一个来自 $p$ 的消息 $m$ 时，执行以下步骤：

  1. 接收与入队：

    • 首先更新 earliest[p]（更新对 $p$ 的期待值）。

    • 无条件将消息 $m$ 放入 blocked[p] 队列中等待检查。

  2. 安全检查 (死循环检查)：

    • 检查所有阻塞队列，看有没有消息变成了“安全”状态（即非阻塞）。

    • 什么是安全？

      • 对于队列 $k$ 里的头消息 $m’$，我们需要检查除 $k$ 和自己以外的所有其他节点 $i$。

      • 检查条件：not_earliest(earliest[i], earliest[k], i)。

      • 直观解释：我们检查消息 $m’$ 所携带的向量时间戳。如果 $m’$ 依赖于节点 $i$ 的某个事件（由 $m’.TS[i]$ 表示），而本地记录的 earliest[i] 显示那个事件还没发生（或者消息还没传过来），那么 $m’$ 就不安全，必须继续等。

      • 只有当所有依赖都满足了，消息才会被移出队列，Deliver 给应用。

  3. 更新进度：

    • 一旦消息 $m’$ 被交付，就要更新 earliest[k]，通常是加 1（向量加法），表示“我已经处理完这个了，准备接收下一个”。

4. 实例演示 (P1, P2, P3 场景)

PPT 第 38-39 页展示了一个经典的违反因果序后被纠正的例子：

  • 场景：

    • $P_1$ 发送消息 $m_2$（时间戳 1,1,0），它依赖于 $P_2$ 的某个事件（中间位是 1）。

    • $P_2$ 发送消息 $m_1$（时间戳 0,1,0）。

    • 在因果上，$m_1 \rightarrow m_2$。但在 $P_3$ 这边，$m_2$ 先到了。

  • 第一步：$m_2$ 先到 (乱序)

    • $P_3$ 收到 $m_2 (1,1,0)$。

    • 检查安全：$m_2$ 要求 $P_2$ 的分量是 1。但 $P_3$ 本地记录的 earliest[2] 是 (0,1,0)（注：这里PPT示例数值可能有些混淆，核心意思是本地只知道 $P_2$ 的初始状态，不知道它发过消息）。

    • 判定：$P_2$ 上有一个更早的消息还没到（即 $m_1$）。

    • 动作：将 $m_2$ 锁在 blocked[1] 队列里，不交付。

  • 第二步：$m_1$ 终于到了

    • $P_3$ 收到 $m_1 (0,1,0)$。

    • 检查安全：$m_1$ 不依赖其他未达消息。

    • 动作：Deliver $m_1$。

    • 更新：更新 earliest[2]，表示 $P_2$ 的进度推进了。

    • 回头检查：现在再看 blocked[1] 里的 $m_2$。因为 $m_1$ 已经处理过，本地关于 $P_2$ 的状态已经更新，$m_2$ 的依赖被满足了。

    • 动作：Deliver $m_2$。

5. 潜在问题

  • 死锁风险：如果某个节点长时间不发消息，其他节点的 earliest 数组就无法更新，导致依赖该节点的其他消息一直被卡在阻塞队列里。

  • 解决：通常这种算法用于组播 (Multicast)，或者节点需要定期发送心跳包来更新时间戳。

概率算法

数字概率算法

这段内容主要讲述了数字概率算法（Numerical Probabilistic Algorithms）的原理及其在三个主要领域的应用：$\pi$值的计算、数值积分以及概率计数（包括集合势的估计和去重计数）。

1. $\pi$ 值的计算 (蒙特卡洛方法)

这是蒙特卡洛算法最经典的入门案例。

  • 原理：

    在一个边长为 $2r$ 的正方形内画一个半径为 $r$ 的内切圆。

    • 正方形面积 $S_{square} = 4r^2$

    • 内切圆面积 $S_{circle} = \pi r^2$

    • 圆与正方形的面积比为 $\pi / 4$

  • 算法过程 (Darts)：

    假设向这个正方形随机投掷 $n$ 支飞镖，假设击中正方形内任意一点的概率相等。

    1. 随机产生点 $(x, y)$，其中 $0 \le x, y \le 1$（为了简化，只看第一象限）。

    2. 判断点是否在圆内：如果 $x^2 + y^2 \le 1$，则计数 $k$ 加 1。

    3. 最终 $\pi$ 的近似值为 $4k/n$。

  • 精度：实验表明，随着投掷次数 $n$ 的增加，计算结果越接近真实值。例如 $n=10$ 亿时，可以精确到小数点后 4 位。

2. 数值积分 (计算定积分)

概率算法常用于计算定积分 $\int_0^1 f(x) dx$，即求曲线 $y=f(x)$ 下方的面积。

  • 算法 1: 投点法 (Hit-or-Miss)

    • 原理：类似于求 $\pi$。在单位正方形内随机投点，计算落入函数曲线 $y=f(x)$ 下方（即阴影部分）的点的比例。

    • 公式：$Integral \approx k/n$。

    • 误差：如果 $n \ge I(1-I)/\epsilon^2\delta$，则绝对误差超过 $\epsilon$ 的概率不超过 $\delta$。

  • 算法 2: 平均值法 (Crude Monte Carlo)

    • 原理：在积分区间 $[a, b]$ 上随机均匀取点，求这些点上的函数值 $f(x)$ 的算术平均值，再乘以区间宽度 $(b-a)$。

    • 对比：Crude 算法通常比 Hit-or-Miss 更有效，方差更小。

  • 与确定性算法 (如梯形法则) 的对比：

    • 低维情况：在同样的精度下，确定性算法（如梯形法）通常需要的迭代次数更少。

    • 高维优势：确定性算法在处理多重积分（高维）时，采样点随维数呈指数增长；而蒙特卡洛算法对维数不敏感，非常适合 4 维或更高维度的积分计算。

    • 特殊函数：对于波动极大的函数（如 $sin^2(100! \pi x)$），梯形法则可能完全失效（返回0），而概率算法能给出更好的近似。

3. 概率计数 (Probabilistic Counting)

这部分解决了当数据量极大（如海量集合）时，如何估计集合大小的问题。

  • 生日悖论 (The Birthday Paradox)

    • 问题：随机选出 25 个人，至少有两个人生日相同的概率是多少？

    • 结论：直觉上认为概率很小，但实际上概率约为 57%（大于 50%）。

    • 启示：这利用了“碰撞”原理，可以通过第一次发生重复采样时的样本量来反推总集合的大小。

  • 估计集合的势 (Set Cardinality)

    • 算法 SetCount：对集合 $X$ 进行有放回的随机均匀采样，直到出现第一个重复元素。设此时共采样了 $k$ 次。

    • 估算公式：集合大小 $|X| \approx 2k^2/\pi$。

  • 多重集合中不同元素计数 (Distinct Elements / WordCount)

    • 场景：统计莎士比亚全集中有多少个不同的单词。由于内存限制，不能存储所有单词。

    • 算法思路 (LogLog/HyperLogLog 的前身)：

      1. 使用哈希函数 $h(x)$ 将单词映射为二进制串。

      2. 对于每个单词，找到其哈希值中第一个为 1 的位的位置（记为 $\pi(h(x), 1)$）。

      3. 维护一个位数组 $y$，将对应位置置为 1。

      4. 最终返回数组 $y$ 中第一个为 0 的位置（记为 $k$）。

    • 原理：

      • 如果算法返回 $k=4$，说明哈希值以 1, 01, 001 开头的单词都出现过，但以 0001 开头的单词没出现过。

      • 出现以 0001 开头（概率 $1/16$）的事件没发生，说明总单词数 $n$ 大概不超过 $2^4$。

      • 估算结果：互不相同的单词数 $n$ 大致在 $2^{k-2}$ 到 $2^k$ 之间。更精确的估计是 $n \approx 2^k / 1.54703$。

    • 优势：空间复杂度仅为 $O(\lg N)$，远优于排序法的 $O(N)$。

Sherwood 算法

课件详细介绍了 Sherwood 算法 的概念、原理以及具体的应用实例（特别是随机预处理技术）。

Sherwood 算法是一类概率算法，它的核心目标不是为了求近似解，而是为了消除确定性算法中“最好情况”和“最坏情况”之间的差异，使得算法的执行时间相对均匀，不再依赖于具体的输入实例。

以下是对课件内容的详细解析和总结：

1. Sherwood 算法的核心思想

  • 背景：很多确定性算法（如快速排序、二叉搜索树操作）在处理某些特定输入（“坏实例”）时，效率会非常低（最坏情况复杂度），但在平均情况下效率很高。

  • 目的：引入随机性，将算法在“坏实例”上的高耗时风险平摊到所有实例上。

  • 效果：

    • 不再有“最坏情况的实例”，只有“最坏情况的随机数选择”（但这发生的概率极低）。

    • 虽然平均执行时间可能会因为引入了随机数生成等操作而略微增加，但它保证了算法性能的稳定性。

2. 随机预处理 (Stochastic Preprocessing)

这是实现 Sherwood 算法的一种通用技术。

  • 基本原理：

    1. 变换 ($u$)：将原始输入实例 $x$，利用一个随机数 $r$，通过函数 $u(x, r)$ 变换为一个随机实例 $y$。这个 $y$ 应该服从均匀分布。

    2. 求解 ($f$)：使用原有的确定性算法 $f$ 来求解随机实例 $y$，得到结果 $s = f(y)$。

    3. 还原 ($v$)：利用函数 $v(r, s)$，将 $y$ 的解 $s$ 还原为原实例 $x$ 的解。

  • 算法流程 (伪代码 RH(x))：

      1. 获取输入 x 的规模 n。
  2. 随机选择一个元素 r (随机种子)。
  3. y = u(x, r);  // 将 x 转化为随机实例 y
  4. s = f(y);     // 用确定性算法求 y 的解
  5. return v(r, s); // 还原为 x 的解

    即 $f(x) = v(r, f(u(x, r)))$ 。

3. 具体应用实例

实例 1：选择和排序 (Selection and Sorting)

  • 场景：比如快速排序（Quicksort），如果输入数组已经是排好序的，效率会退化到 $O(n^2)$。

  • Sherwood 策略：在排序前，先调用 Shuffle 函数（洗牌算法）。

  • 做法：随机打乱数组中元素的顺序。这样无论原始输入是什么样（即使是恶意的最坏序列），经过打乱后都变成了随机排列，从而保证快速排序能以 $O(n \log n)$ 的平均时间运行。

实例 2：离散对数计算 (Discrete Logarithm)

  • 问题：已知 $a = g^x \mod p$，求 $x$。

  • 难点：简单的确定性算法在某些特定 $a$ 值下运行很快，但在另一些值下运行极慢（最坏情况）。我们希望执行时间与具体的 $a$ 无关。

  • Sherwood 改造 (dlogRH)：

    1. 随机化：随机选一个整数 $r$。

    2. 构造新实例：计算 $b = g^r \mod p$，然后计算 $c = b \cdot a \mod p$。

      • 原理推导：$c = g^r \cdot g^x = g^{r+x} \mod p$。

    3. 求解：用确定性算法求 $c$ 的离散对数 $y$。此时 $y = r + x$。

    4. 还原：计算 $x = (y - r) \mod (p-1)$。

  • 意义：通过乘以 $g^r$，将求解 $a$ 的对数转化为了求解随机数 $c$ 的对数，平滑了计算时间。

实例 3：加密计算 (隐私保护)

课件最后提出了一个非常有意思的应用场景——外包计算。

  • 场景：你需要计算 $f(x)$，但计算能力不足，或者没有高效算法。别人有计算能力，你却不想让他知道你的原始数据 $x$。

  • 方法：

    1. 你自己做一步简单的随机变换 $y = u(x, r)$（加密）。

    2. 把 $y$ 发送给拥有计算能力的人（云服务器/第三方）。

    3. 对方计算 $f(y)$ 并返回结果。对方只看到了随机的 $y$，无法反推 $x$。

    4. 你自己计算 $v(r, f(y))$ 得到最终结果 $f(x)$。

  • 条件：这要求 $u(x, r)$ 的分布独立于 $x$，即起到“盲化”数据的作用。

实例 4：有序静态链表搜索

  • 问题背景：

    • 数据结构：静态链表 val[1..n] 和 ptr[1..n]，其中 val 存储数值，ptr 存储下一个元素的索引。表中的元素是有序的，即 val[head] ≤ val[ptr[head]] ≤ ...。

    • 搜索问题：给定一个关键字 x，在链表中找到其索引 i，使得 val[i] = x。

    • 挑战：虽然链表有序，但因为是链式存储，不能直接像数组那样进行 $O(\log n)$ 的二分查找。如果直接顺序查找，最坏时间复杂度是 $\Omega(n)$。

  • 算法对比

    课件中展示了三种不同思路的算法：

    1. $O(n)$ 的确定性算法 (Sequential Search)

      • 算法 A (A(x))：从链表头 head 开始，顺着 ptr 指针逐个比较，直到找到 x。

      • 性能：

        • 最坏时间 $w_A(n) \propto n$。

        • 平均时间 $m_A(n) \propto n/2$。

        • 缺点：如果目标元素在链表尾部，效率极低。

    2. $O(n)$ 的概率算法 (Sherwood Algorithm)

      • 算法 D (D(x))：引入随机性来打破“从头开始”的僵局。

        1. 随机选取数组中的一个索引 i。

        2. 比较 x 和 val[i]（记为 y）：

          • Case 1 ($x < y$)：如果 x 比随机点小，说明 x 在前面。只能老老实实从头 head 开始搜。

          • Case 2 ($x > y$)：如果 x 比随机点大，说明 x 在后面。可以从随机点 ptr[i] 开始往后搜（跳过了前面一段，节省了时间）。

          • Case 3 ($x = y$)：运气爆棚，直接找到了。

      • 性能：

        • 最坏时间 $w_D(n) \propto n$（比如随机选到了第一个元素，或者 x 就是最后一个元素）。

        • 平均时间 $m_D(n) \approx n/3$。

        • 优势：平均性能优于单纯的确定性算法 A。

    3. 平均时间为 $O(\sqrt{n})$ 的确定性算法

      • 算法 B (B(x))：尝试通过预处理来加速。

        1. 取前 $\sqrt{n}$ 个物理位置上的元素（即 val[1..√n]），把它们当作随机抽样点。

        2. 在这 $\sqrt{n}$ 个点中，找到不超过 x 的最大值 y，记下其下标 i。

        3. 从 i 开始调用 Search 继续往后找。

      • 原理：这相当于把链表分成了 $\sqrt{n}$ 个段，先通过采样快速定位到 x 所在的“段”，然后再在段内进行顺序查找。

      • 性能：

        • 采样消耗 $\sqrt{n}$。

        • 段内查找平均消耗 $n / \sqrt{n} = \sqrt{n}$。

        • 总平均时间 $m_B(n) \propto 2\sqrt{n}$。

      • 本质：这其实利用了 val 数组中物理存储的随机性来模拟索引结构。

  • 核心结论

    • 确定性算法 A：最简单，但受限于链表结构，平均性能一般 ($n/2$)。

    • Sherwood 算法 D：通过引入随机起点，不仅消除了对特定最坏实例的依赖，还将平均查找长度降低到了 $n/3$。

    • 优化算法 B：利用“采样+分段”的思想，打破了线性查找的限制，将平均时间复杂度从 $O(n)$ 降低到了 $O(\sqrt{n})$。

总结

Sherwood 算法通过“随机预处理”技术，主动打破输入数据的特定模式，将算法的性能与输入数据的具体值解耦。它是一种“以退为进”的策略：虽然稍微增加了平均处理时间，但彻底消除了最坏情况发生的可能性，使算法更加健壮。

Las Vegas 算法：8 皇后问题

以下是关于 Las Vegas 算法 及其在 8 皇后问题 (8-Queens Problem) 中应用的详细解析，基于你提供的课件内容。

1. Las Vegas 算法 vs Sherwood 算法

课件开头对比了这两类概率算法，这是理解它们各自定位的关键。

  • Las Vegas (LV)：

    • 特点：绝不给错解。要么给出正确解，要么根本不给解（失败/僵局）。

    • 效率：通常能获得比确定性算法更高效的平均性能。

    • 时间上界：可能不存在。因为可能一直随机失败，一直重试，理论上最坏时间是无穷大。

    • 失败处理：一旦失败（陷入僵局），通常的做法是从头再来（重新运行同一实例），因为下一次随机决策可能就会避开死胡同。成功的概率随着尝试时间的增加而增加。

  • Sherwood：

    • 特点：总是给出正确解，目的是消除最坏情况。

    • 效率：平均性能一般不比确定性算法优（主要是为了稳定性）。

    • 时间上界：可以计算出一个确定的执行时间上界。

2. Las Vegas 算法的一般形式与性能分析

  • 函数定义：LV(x, y, success)，其中 success 为 true 表示找到解，false 表示失败。

  • 关键指标：

    • $p(x)$：算法一次运行成功的概率。

    • $s(x)$：成功时的期望时间。

    • $e(x)$：失败时的期望时间。

  • 顽固算法 (Obstinate)：

    • 策略：一直调用 LV 直到 success 为真。

    • 期望时间 $t(x)$ 公式：

      \[t(x) = s(x) + \frac{1-p(x)}{p(x)} e(x)\]

    • 解读：总时间 = 一次成功的时间 + (平均失败次数 $\times$ 一次失败的时间)。要最小化 $t(x)$，需要在成功率 $p(x)$ 和单次运行时间之间做折中。有时候降低 $p(x)$（快速失败）反而能减少总时间，因为 $e(x)$ 变小了。

3. 经典案例：8 皇后问题

8 皇后问题要求在 $8 \times 8$ 的棋盘上放置 8 个皇后，使其互不攻击（行、列、对角线均无冲突）。

A. 传统回溯法 (Backtracking)

  • 策略：从第一行开始逐行放置。如果当前行找不到安全位置，就回退到上一行，移动上一行皇后的位置。

  • 效率：平均需要搜索约 114 个结点才能找到一个解。

B. 纯 Las Vegas 算法 (QueensLv)

  • 策略 (贪心 + 随机)：

    • 逐行放置皇后。

    • 对于第 $k+1$ 行，计算所有安全位置（nb 个）。

    • 如果 nb > 0：在这些安全位置中随机均匀选择一个放置皇后。

    • 如果 nb = 0：死局。当前尝试失败，算法终止（返回 false）。

  • 性能：

    • 成功率 $p \approx 0.1293$（约 13%）。

    • 期望节点数 $t(x) \approx 55.93$。

    • 结论：比纯回溯法（114 个结点）快了一倍左右。

C. 混合策略 (Hybrid / 折中算法)

这是课件的重点改进方案。

  • 问题：纯 LV 算法一旦失败就得从头再来（太消极）；纯回溯法一步步试错太慢（太乐观）。

  • 改进思路：先用 LV 算法随机放置前 $k$ 个皇后（stepVegas），剩下的 $8-k$ 个皇后用回溯法放置。

    • 如果随机放置的前 $k$ 个位置太烂，导致后面无解，回溯法会返回失败，然后整个算法重新随机前 $k$ 个。

  • 关键参数 stepVegas：预先随机放置几个皇后最好？

    • 实验数据 (8 皇后)：当 stepVegas = 2 或 3 时，期望节点数降至约 28~29，远优于纯回溯 (114) 和纯 LV (56)。

    • 实验数据 (12 皇后)：当 stepVegas = 5 时效果最好，时间从纯回溯的 125ms 降至 37ms。

    • 实验数据 (20 皇后)：混合算法找一个解比确定性回溯快约 1000 倍！

  • 结论：通常一半略少的皇后使用随机放置，剩余的使用回溯法，效果最佳。

4. 总结

Las Vegas 算法在解决如 N 皇后这类解分布不均匀且搜索空间巨大的问题时非常有效。通过引入随机性，它能跳过复杂的搜索树分支。而将 Las Vegas 与确定性回溯结合（混合策略），则能通过随机性快速深入搜索树的深层，同时利用回溯法的完备性来搜索局部解，从而获得极大的性能提升。

Las Vegas 算法：模 $p$ 平方根

这段PPT（§4.2）主要讲解了数论中的模 $p$ 平方根问题，以及在 $p$ 为奇素数时如何求解平方根，特别是针对计算困难的情况（$p \equiv 1 \pmod 4$）提出了一种 Las Vegas 概率算法。

以下是详细的知识点拆解：

1. 基本概念与定义 (Slide 84-87)

首先定义了什么是“模 $p$ 的平方根”：

  • 二次剩余 (Quadratic Residue)：设 $p$ 是奇素数，对于整数 $x \in [1, p-1]$，如果存在整数 $y$ 使得 $y^2 \equiv x \pmod p$，则称 $x$ 是模 $p$ 的二次剩余。

  • 平方根：上述的 $y$ 即为 $x$ 模 $p$ 的平方根。

  • 非二次剩余：如果不存在这样的 $y$，则 $x$ 是非二次剩余。

核心定理：

  1. 数量定理：

    • 任何一个二次剩余 $x$ 恰好有两个 不同的平方根。

    • 这两个根互为相反数（模 $p$ 意义下），即如果 $y$ 是根，则 $p-y$ 也是根。

  2. 分布定理：

    • 在 $[1, p-1]$ 中，恰有一半的数是二次剩余，另一半是非二次剩余。

  3. 判定定理 (欧拉判别法)：

    • $x$ 是模 $p$ 的二次剩余 $\iff x^{\frac{p-1}{2}} \equiv 1 \pmod p$。

    • $x$ 是非二次剩余 $\iff x^{\frac{p-1}{2}} \equiv -1 \pmod p$。

2. 计算平方根的难题 (Slide 88)

虽然判定 $x$ 是否有根很容易（用欧拉判别法），但求出根 $y$ 却不一定容易。这取决于 $p$ 的形式：

  • 情况 1：$p \equiv 3 \pmod 4$

    • 这种情况很容易，有直接的公式求解（PPT中略过，通常是 $y \equiv \pm x^{(p+1)/4}$）。

  • 情况 2：$p \equiv 1 \pmod 4$

    • 没有有效的确定性算法。

    • 必须使用 Las Vegas 概率算法。

3. Las Vegas 求解算法 (Slide 89-93)

针对 $p \equiv 1 \pmod 4$ 的困难情况，PPT 介绍了一种基于扩域运算的概率算法。

A. 算法核心思想

算法类似于复数运算，构造了一个扩域 $\mathbb{Z}_p[\sqrt{x}]$。

定义二元组 $(a, b)$ 表示数 $a + b\sqrt{x}$。

定义乘法规则：

\[(a, b) \times (c, d) = (ac + xbd, ad + bc)\]

注：这其实就是 $(a+b\sqrt{x})(c+d\sqrt{x})$ 展开后的实部和虚部，其中 $\sqrt{x}^2$ 替换为 $x$。

B. 数学推导 (Why it works)

我们需要求 $y$ 使得 $y^2 \equiv x$。

算法随机选取一个数 $a$，然后计算 $(a + \sqrt{x})^{\frac{p-1}{2}}$。

设计算结果为 $c + d\sqrt{x}$（即二元组 $(c, d)$）。

根据推导：

  1. 将未知的真根 $y$ 代入 $\sqrt{x}$ 的位置（因为 $y^2 \equiv x$）。

  2. 根据费马小定理，$z^{p-1} \equiv 1$，所以 $z^{\frac{p-1}{2}} \equiv \pm 1$。

  3. 我们有两个方程：

    • $c + dy \equiv (a + y)^{\frac{p-1}{2}} \equiv \pm 1 \pmod p$

    • $c - dy \equiv (a - y)^{\frac{p-1}{2}} \equiv \pm 1 \pmod p$

  4. 关键点：如果 $(a+y)$ 和 $(a-y)$ 的勒让德符号不同（即一个是二次剩余，一个不是），那么上述两个式子右边一个是 $1$，一个是 $-1$。

  5. 两式相减：

    \[(c + dy) - (c - dy) \equiv 1 - (-1) \implies 2dy \equiv 2 \implies dy \equiv 1 \pmod p\]

    或者反过来得到 $dy \equiv -1$。

  6. 只要 $d \neq 0$，我们就可以通过求逆元算出 $y = \pm d^{-1} \pmod p$。

C. 算法流程 (rootLV)

  1. 随机选择：随机选一个整数 $a \in [1, p-1]$。

  2. 极小概率直接命中：如果 $a^2 \equiv x \pmod p$，那 $a$ 就是根，直接返回。

  3. 计算：计算 $(a, 1)^{\frac{p-1}{2}}$，得到结果 $(c, d)$。这里用到快速幂模运算。

  4. 判断：

    • 如果 $d = 0$，说明随机选的 $a$ 不好（导致 $c+dy$ 和 $c-dy$ 同号），失败 (Success = false)。

    • 如果 $d \neq 0$，说明成功。解线性方程求出 $y$（即计算 $d$ 模 $p$ 的逆元）。

  5. 概率：算法成功的概率接近 0.5。如果失败，重新选一个 $a$ 再试一次即可。平均调用 2 次就能找到解。

总结

这段内容展示了数论在算法设计中的应用。对于模 $p$ 平方根问题，利用 $x$ 是二次剩余这一性质，通过构造扩域并在其中进行指数运算，可以将“求根问题”转化为“以 50% 概率解线性方程”的问题。这就是典型的 Las Vegas 算法：要么给出正确解，要么报告失败（然后重试），绝不给错误解。

Las Vegas 算法：整数的因数分解

以下是关于整数因数分解及其Dixon 算法的详细解析：

1. 整数因数分解问题概述

  • 目标：给定一个大于 1 的合数 $n$，找到它的一个非平凡因数（即不是 1 和 $n$ 本身的因数）。

  • 分解过程：

    1. 素性检测 (prime(n))：首先判定 $n$ 是否为素数（常用 Monte Carlo 算法）。

    2. 分裂 (split(n))：如果 $n$ 是合数，找到它的一个因子。

  • 朴素算法：从 2 到 $\sqrt{n}$ 逐一试除。

    • 最坏时间复杂度：$O(\sqrt{n})$。对于大整数（如 50 位十进制数），计算时间是指数级的，无法接受。

    • 结论：目前没有多项式时间算法能分解 $n$。

2. 数学基础：模 $n$ 的二次剩余

Dixon 算法依赖于数论中的一个重要性质。

  • 定义：如果 $x^2 \equiv y \pmod n$，则 $y$ 是 $x$ 模 $n$ 的平方，或者说 $x$ 是 $y$ 模 $n$ 的平方根。

  • 合数的性质：

    • 如果 $n = p \times q$（$p, q$ 为不同奇素数），则每个二次剩余恰好有 4 个 平方根。

    • 这意味着对于同一个 $y$，可能存在 $a$ 和 $b$ 使得 $a^2 \equiv b^2 \pmod n$，但 $a \not\equiv \pm b \pmod n$。

  • 核心原理：

    如果我们能找到两个数 $a$ 和 $b$，满足：

    1. $a^2 \equiv b^2 \pmod n$

    2. $a \not\equiv \pm b \pmod n$

    那么 $n$ 一定整除 $(a^2 - b^2) = (a+b)(a-b)$。

    此时，$\gcd(a+b, n)$ 就能给出 $n$ 的一个非平凡因子。

3. Dixon 因数分解算法详解

Dixon 算法通过随机寻找“平滑数”来构造满足上述核心原理的 $a$ 和 $b$。

关键概念：$k$-平滑 ($k$-smooth)

如果一个整数的所有素因子都包含在前 $k$ 个素数之中，则称该整数为 $k$-平滑。例如，前 3 个素数为 2, 3, 5。那么 $12 = 2^2 \times 3$ 是 3-平滑的，而 $35 = 5 \times 7$ 不是。

算法步骤

  • Step 1: 收集关系式 (Collection Phase)

    • 随机选择整数 $x \in [1, n-1]$。

    • 计算 $y = x^2 \pmod n$。

    • 检查 $y$ 是否为 $k$-平滑。如果是，将 $(x, y)$ 这一对及其因数分解记录下来。

    • 目标是收集 $k+1$ 个这样的关系式。

  • Step 2: 线性代数消元 (Linear Algebra Phase)

    • 对于收集到的每个 $y_i$，我们只关心其素因子的指数是奇数还是偶数。构造一个 $(k+1) \times k$ 的 0-1 矩阵。

    • 因为行数 ($k+1$) 大于列数 ($k$)，根据线性代数原理，这些行在模 2 意义下必然 线性相关。

    • 使用高斯消元法找到这些线性相关的行，这意味着这些行的对应 $y_i$ 乘积是一个完全平方数。

  • Step 3: 计算因子 (Factor Computation)

    • 令 $a$ 为相关行对应 $x_i$ 的乘积。

    • 令 $b$ 为相关行对应 $y_i$ 的乘积开平方（因为 $y_i$ 乘积的素因子指数均为偶数，开方很容易）。

    • 此时满足 $a^2 \equiv b^2 \pmod n$。

    • 计算 $\gcd(a+b, n)$。如果结果不是 1 或 $n$，则找到了非平凡因子。

4. 实例演示 (n = 2537)

  • 设置：$k=7$，前 7 个素数为 ${2, 3, 5, 7, 11, 13, 17}$。

  • Step 1：收集到 8 个 $x$，它们的平方 $x^2 \pmod n$ 都是 7-平滑的。

    • 例如：$1003^2 \equiv 1584 \equiv 2^4 \cdot 3^2 \cdot 11 \pmod{2537}$。

  • Step 2：发现第 1, 4, 8 个方程对应 $y$ 的乘积是完全平方数。

    • $y_1 \cdot y_4 \cdot y_8 = (2^4 \cdot 3^2 \cdot 11) \cdot (2^4 \cdot 11) \cdot (3^4) = 2^8 \cdot 3^6 \cdot 11^2 = (2^4 \cdot 3^3 \cdot 11)^2$。

  • Step 3：

    • $a = x_1 \cdot x_4 \cdot x_8 = 1003 \cdot 2419 \cdot 2200 \pmod{2537}$。

    • $b = \sqrt{y_1 y_4 y_8} = 2^4 \cdot 3^3 \cdot 11$。

    • 计算 $\gcd(a+b, 2537) = 43$。成功分解！

5. 性能分析

  • $k$ 的选择：这是一个权衡。

    • $k$ 越大，随机选的 $x^2 \pmod n$ 越容易是 $k$-平滑的（容易收集），但后续矩阵处理越慢。

    • $k$ 越小，矩阵小，但很难找到 $k$-平滑数。

  • 最佳实践：通常取 $k \approx \exp(\sqrt{\ln n \ln \ln n})$。

  • 复杂度：Dixon 算法期望时间复杂度约为 $O(\exp(\sqrt{2 \ln n \ln \ln n}))$，比朴素算法快得多，但仍是亚指数级的。

Monte Carlo 算法

以下是关于 Monte Carlo (蒙特卡洛) 算法 的核心概念、误差放大机制以及有偏算法的详细解析。

1. Monte Carlo 算法概述

Monte Carlo (MC) 算法是一类概率算法。与确定性算法不同，它不能保证总是给出正确的答案。

  • 特性：它偶尔会犯错，且出错时没有警告信息。

  • 目标：无论针对何种输入实例，它都能以高概率找到正确解。

  • 适用场景：当无法找到有效的确定性算法来获取正确答案时使用。

2. 核心定义

为了衡量 MC 算法的质量，引入了以下定义：

  • p-正确 (p-correct)：如果一个 MC 算法返回正确解的概率不小于 $p$（其中 $1/2 < p < 1$），则称该算法是 $p$-正确的。

    • 优势 (Advantage)：算法的优势定义为 $p - 1/2$。只要 $p > 0.5$，算法就比瞎猜（50%概率）要好。

  • 一致性 (Consistent)：如果一个 MC 算法对同一个实例绝不给出两个不同的正确解（即正确解是唯一的），则称该算法是一致的（或相容的）。

3. 一般 MC 算法的精度提升：多数投票法

对于一个一致的、$p$-正确的算法（$p>0.5$），我们可以通过重复调用并取出现频数最高的解来提高其正确率。

  • 原理：既然算法正确的概率大于错误概率，重复多次后，正确答案出现的次数在统计上应该最多。

  • 示例 (MC3)：

    • 假设有一个 75%-correct 的算法。

    • 重复运行 3 次，设结果为 $t, u, v$。

    • 如果其中有两个或三个结果相同，就返回那个结果。

    • 效果：正确率从 75% 提升到了约 84% (27/32)。

  • 定理：无论算法的优势 $\epsilon$ ($p = 0.5 + \epsilon$) 多么微小，只要 $\epsilon > 0$，就可以通过重复调用足够多的次数，将错误概率 $\delta$ 降到任意小。

    • 代价：对于优势很小的算法，可能需要调用很多次（例如数百次）才能达到理想的精度。

4. 有偏算法 (Biased Algorithms)：更高效的提升

对于某些特定的 MC 算法，我们不需要“少数服从多数”，只需要“一次成功”即可确认答案。这类算法提升精度的效率远高于普通算法。

A. 偏真算法 (True-biased)

主要用于判定问题（返回 True/False）。

  • 定义：

    • 当算法返回 True 时，解总是正确的。

    • 当算法返回 False 时，解可能是错误的。

  • 策略：重复运行多次。只要有一次返回 True，就断定结果为 True；只有所有次都返回 False，才认为结果是 False。

  • 效率：不需要统计频数。重复 6 次即可将 55% 的正确率提升到 99%。

B. 偏 $y_0$ 算法 ($y_0$-biased)

这是偏真算法的推广形式，不再局限于判定问题。

  • 定义：存在一个特定解 $y_0$（通常代表某种“成功”或“发现因子”的状态）。

    • 如果算法返回的结果是 $y_0$，则它总是正确的。

    • 如果算法返回非 $y_0$，则有可能是错误的。

  • 正确性证明：

    • 如果实例 $x$ 不属于特定子集 $X$，算法总是返回正确解（此时正确解就是 $y_0$）。

    • 如果实例 $x$ 属于 $X$（正确解是 $y_0$），算法可能返回错误解（非 $y_0$）。

    • 因此，只要返回了 $y_0$，它一定是真解。

  • 策略：重复调用 $k$ 次，优先返回 $y_0$。如果某次结果为 $y_0$，则直接返回 $y_0$。

  • 误差降低：重复 $k$ 次后，错误概率迅速降低为 $(1-p)^k$。例如 $p=0.55$，重复 4 次即可达到 95% 的正确率。

总结对比

算法类型一致的 p-正确算法 (普通)偏真 / 偏 y0​ 算法 (有偏)
判决机制多数投票 (返回频数最高的解)优先命中 (一旦出现 $y_0$/True 即返回)
收敛速度较慢 (需要数百次重复来显著提升微小优势)极快 (指数级降低错误率，几次重复即可)
前提条件$p > 1/2$ (优势必须存在)$p > 0$ (只要有非零概率返回 $y_0$ 即可)

Monte Carlo 算法：主元素问题

1. 问题定义

主元素：在一个包含 $n$ 个元素的数组 $T[1..n]$ 中，如果某个元素 $x$ 的出现次数严格大于 $n/2$，则称 $x$ 为主元素。

  • 注：如果数组中存在主元素，那么它一定是唯一的。

2. 基础算法 maj(T)

这是一个简单的概率算法，试图通过随机采样来找到主元素。

  • 算法流程：

    1. 随机采样：从数组中随机选择一个下标 $i$ ($1 \le i \le n$)。

    2. 计数验证：令候选元素 $x = T[i]$，遍历整个数组统计 $x$ 出现的次数 $k$。

    3. 判定：如果 $k > n/2$，返回 true；否则返回 false。

  • 算法性质分析：

    • 偏真性 (True-biased)：

      • 如果算法返回 true，说明找到了一个出现次数确实超过一半的元素，结论绝对正确。

      • 如果算法返回 false，数组可能仍然含有主元素，只是刚才随机运气不好，没抽中它而已。

    • 正确率：

      • 如果数组确实有主元素，因为主元素占比超过一半，所以随机抽中它的概率 $p > 1/2$。

      • 因此，该算法是一个 $1/2$-正确 的算法（单次失败概率 $< 1/2$）。

3. 算法改进：重复调用 (maj2 和 majMC)

单次运行 50% 的错误率（漏报率）在实际应用中是无法接受的。利用 Monte Carlo 算法的特性，我们可以通过独立重复试验来指数级降低错误率。

A. maj2(T)：重复两次

  • 逻辑：先调用一次 maj(T)，如果成功则返回；如果失败，再调用一次。

  • 概率分析（假设存在主元素）：

    • 第一次就选中的概率：$p > 1/2$。

    • 第一次没选中，第二次选中的概率：$(1-p)p$。

    • 总成功率：$p + (1-p)p = 1 - (1-p)^2 > 1 - (1/2)^2 = 3/4$。

    • 即：重复两次，正确率提升至 75% 以上。

B. majMC(T, ε)：重复 k 次

为了满足任意给定的错误率上限 $\epsilon$（例如 $\epsilon = 0.001$），我们可以动态计算需要的重复次数。

  • 重复次数 $k$：

    由于 $k$ 次独立采样均失败的概率小于 $2^{-k}$，为了使 $2^{-k} < \epsilon$，我们需要取 $k = \lceil \lg(1/\epsilon) \rceil$。

  • 算法流程：

    循环 $k$ 次，每次都随机采一个样并验证。只要有一次验证成功，就返回 true。如果 $k$ 次全败，才返回 false。

  • 时间复杂度：

    • 单次验证需要遍历数组，耗时 $O(n)$。

    • 重复 $k$ 次，总时间复杂度为 $O(n \lg(1/\epsilon))$。

4. 总结

  • 这是一个典型的 Monte Carlo 算法：它通过牺牲确定性（存在极小的概率找不到解）来换取实现的简单性。

  • 有偏性：它是单侧错误的，只会出现“有主元素但没找到”（False Negative），绝不会出现“没有主元素却说有”（False Positive）。

  • 对比：课件最后提到，其实对于主元素问题，存在时间复杂度为 $O(n)$ 的确定性算法（如 Boyer-Moore 投票算法）。这里使用 MC 算法主要是为了作为教学案例，展示概率算法如何通过重复执行来提高可靠性。

Monte Carlo 算法：素数测定

课件详细介绍了素数判定（Primality Testing）的演变过程，从简单的概率算法到 Fermat 测试，再到更健壮的 Miller-Rabin 算法。

1. 简单的概率算法与 Fermat 小定理

  • 背景：直接判定一个大数 $n$ 是否为素数很难。

  • Fermat 小定理：如果 $n$ 是素数，那么对于任意 $a \in [1, n-1]$，都有 $a^{n-1} \equiv 1 \pmod n$。

  • Fermat 测试：

    • 随机选一个 $a$，计算 $a^{n-1} \pmod n$。

    • 如果结果不是 1，那么 $n$ 肯定是合数（正确）。

    • 如果结果是 1，那么 $n$ 可能是素数（也可能是伪素数）。

  • 缺陷：存在Carmichael 数（如 561），它们虽然是合数，但对几乎所有的底数 $a$ 都满足费马小定理。对于这些数，Fermat 测试会失效，无法通过重复测试来任意降低错误率。

2. Miller-Rabin 测试 (强伪素数测试)

为了解决 Carmichael 数的问题，引入了更强的测试条件。

A. 强伪素数定义

对于奇数 $n$，设 $n-1 = 2^s \cdot t$（其中 $t$ 为奇数）。

如果 $n$ 是素数，那么对于任意 $a \in [2, n-2]$，必然满足以下两个条件之一：

  1. $a^t \equiv 1 \pmod n$

  2. 存在某个 $r \in [0, s-1]$，使得 $a^{2^r \cdot t} \equiv n-1 \equiv -1 \pmod n$

如果 $n$ 是合数但满足上述条件，则称 $n$ 为以 $a$ 为底的强伪素数。

B. 算法逻辑 (MillRab)

  1. 将 $n-1$ 分解为 $2^s \cdot t$。

  2. 随机选择 $a$。

  3. 计算 $x = a^t \pmod n$。

  4. 如果 $x=1$ 或 $x=n-1$，则通过测试（可能为素数）。

  5. 重复做平方运算 $x = x^2 \pmod n$ 最多 $s-1$ 次。如果中间出现了 $n-1$，则通过测试。

  6. 如果直到最后都没出现 $n-1$，则返回 false（肯定是合数）。

C. 错误率与优势

  • 定理：对于任意大于 4 的奇合数 $n$，其强伪证据（即能骗过算法的 $a$）的数量不超过总数的 1/4。

  • 结论：Miller-Rabin 算法是一个 3/4-正确 的算法。

    • 只要随机选 $a$，它判定合数为合数的概率至少是 75%。

    • 这比 Fermat 测试强得多，因为不存在类似 Carmichael 数那样的“无敌合数”。

3. 重复调用 (RepeatMillRob)

  • 策略：独立重复运行 Miller-Rabin 测试 $k$ 次。

  • 正确率：

    • 如果 $n$ 是合数，连续 $k$ 次都碰巧选到强伪证据（骗过算法）的概率小于 $(1/4)^k = 4^{-k}$。

    • 取 $k=10$，错误率小于百万分之一。

    • 取 $k=150$，错误率小于 $4^{-150}$，这在实际上比计算机硬件出错的概率还要低。

  • 时间复杂度：

    • 主要是模幂运算。每次测试耗时 $O(\lg^3 n)$（如果是朴素乘法）。

    • 总时间为 $O(k \lg^3 n)$。对于上千位的数字，计算速度完全可以接受。

总结

Miller-Rabin 算法是目前工业界（如 RSA 加密密钥生成）最常用的素数判定算法。它虽然是概率算法（偏假），但通过少量的重复测试，可以将错误率降低到工程上可以忽略不计的程度，且效率远高于确定性算法。

Monte Carlo 算法：矩阵乘法验证

这段 PPT (§5.3) 介绍了一个经典的 Monte Carlo 算法（通常被称为 Freivalds 算法），用于快速验证两个矩阵相乘的结果是否正确。

这是一个极其巧妙的算法，展示了概率算法如何将计算复杂度从 $O(n^3)$ 降低到 $O(n^2)$。

1. 问题背景：矩阵乘法验证

  • 输入：三个 $n \times n$ 的矩阵 $A, B, C$。

  • 问题：判定 $A \times B$ 是否等于 $C$？

  • 传统做法：

    • 直接计算 $A \times B$，然后逐个元素对比结果与 $C$ 是否一致。

    • 代价：矩阵乘法的时间复杂度是 $O(n^3)$（即便用 Strassen 算法也是 $O(n^{2.81})$）。当 $n$ 非常大时，计算代价极高。

  • 新思路：使用 Monte Carlo 算法，在 $O(n^2)$ 时间内解决问题，但要接受极小的出错概率。

2. 核心算法：引入随机向量

算法的核心在于不直接计算矩阵乘积，而是引入一个随机的 $0/1$ 向量 $X$，将矩阵等式验证转化为向量等式验证。

  • 判定依据：将判定 $AB = C$ 改为判定 $X(AB) = XC$。

  • 结合律的妙用 (The Trick)：

    • 如果我们先算 $AB$，那复杂度还是 $O(n^3)$。

    • 利用结合律，我们可以先算 $XA$，再算 $(XA)B$。

    • 计算顺序：

      1. 计算 $R_1 = X \times A$ —— 向量乘矩阵，复杂度 $O(n^2)$。

      2. 计算 $R_2 = R_1 \times B$ —— 向量乘矩阵，复杂度 $O(n^2)$。

      3. 计算 $R_3 = X \times C$ —— 向量乘矩阵，复杂度 $O(n^2)$。

    • 总复杂度：$O(n^2)$。

3. 算法流程 (goodproduct)

  1. 随机化：生成一个长度为 $n$ 的随机向量 $X$，每个元素随机取 0 或 1。

  2. 验证：检查是否满足 $(XA)B = XC$。

  3. 输出：

    • 如果相等，返回 true（可能 $AB=C$，也可能出错了）。

    • 如果不等，返回 false（肯定 $AB \neq C$）。

4. 误差分析与算法性质

PPT 通过一个具体的数值例子（Slide 141-142）展示了两种情况：

  • 漏判 (False Positive)：$AB \neq C$，但选到了特定的 $X$（如 $X=(1,1,0)$），导致 $XAB$ 恰好等于 $XC$。算法错误地返回了 true。

  • 正确识别：换一个 $X$（如 $X=(0,1,1)$），就能检测出 $AB \neq C$。

偏假算法 (False-biased / One-sided Error):

  • 若返回 false：说明 $XAB \neq XC$，则必然有 $AB \neq C$。结论绝对正确。

  • 若返回 true：说明 $XAB = XC$，但这不能保证 $AB = C$（存在 50% 的概率是误判）。

  • 单次错误率：如果 $AB \neq C$，单次随机测试出错（没检测出来）的概率 $\le 1/2$。

5. 精度改进 (RepeatGoodProduct)

为了降低那 50% 的错误率，我们采用重复测试的方法。

  • 策略：重复运行 $k$ 次算法，每次使用独立的随机向量 $X$。

  • 逻辑：

    • 只要有一次发现不等（返回 false），就立即断定 $AB \neq C$。

    • 如果 $k$ 次都返回 true，才敢说 $AB = C$。

  • 错误率：连续 $k$ 次都“倒霉”没检测出错误的概率是 $1/2^k$。

    • 当 $k=20$ 时，出错概率小于 百万分之一。

    • 此时总时间复杂度为 $O(k n^2)$。

总结

对于大矩阵验证，$O(k n^2)$ 远远快于 $O(n^3)$。这个算法完美体现了 Monte Carlo 算法的哲学：用极小的、可控的错误概率，换取巨大的计算速度提升。

往年题例子

一、给出一个计算图的最小顶点覆盖的近似算法，并说明其时间复杂度及近似比。

VertexSet approxVertexCover ( Graph g ) { 
  cset=∅； 
  e1=g.e； 
  while (e1 != ∅) { 
    从e1中任取一条边(u,v)； 
    cset=cset∪{u,v}； 
    从e1中删去与u和v相关联的所有边； 
  } 
  return c 
}

  1. 时间复杂度分析

    算法需要遍历所有边，若用邻接表表示，时间复杂度为 $O(V + E)$。

  2. 近似比证明

    • 算法选出的所有边 $(u, v)$ 组成了一个边集 $M$（正好是一个匹配）。对于 $M$ 中的每一条边，算法都将它的两个端点加入了 $A(G)$。所以 $A(G) = 2 \cdot |M|$。

    • 考虑最优顶点覆盖 $OPT(G)$。根据顶点覆盖的定义，$OPT(G)$ 必须覆盖图中的每一条边，当然也包括 $M$ 中的边。因为 $M$ 是一个匹配，其中的边两两互不相连，所以 $OPT(G)$ 必须为 $M$ 中的每一条边至少选择一个顶点才能覆盖住它们，因此 $OPT(G) \ge |M|$。

    • 联立得 $\dfrac{A(G)}{OPT(G)} \le 2$。

二、设集合 S 和 T 中各有 n 个互不相同的元素，要求： (1)写一 Monte Carlo 算法判定 S 和 T 是否相等；(2)分析算法出错的概率；(3)算法是否有偏，若有偏，偏什么？

这是一个非常经典的随机化算法问题，通常使用多项式恒等测试（Polynomial Identity Testing）的思路来解决。

以下是基于蒙特卡洛（Monte Carlo）方法的解答：

(1) 蒙特卡洛算法设计

我们要利用多项式的性质：如果两个集合相等，那么以这两个集合元素为根构成的多项式应该是恒等的。

算法流程：

  1. 定义域选择：选择一个足够大的素数 $q$（建议 $q \gg n$，例如 $q > n^2$ 或更大，以降低冲突概率）。

  2. 随机采样：从整数域 ${0, 1, 2, \dots, q-1}$ 中均匀随机地选取一个整数 $r$。

  3. 多项式求值：

    • 计算集合 $S$ 对应的多项式在 $r$ 处的值：$V_S = \prod_{s \in S} (r - s) \pmod q$

    • 计算集合 $T$ 对应的多项式在 $r$ 处的值：$V_T = \prod_{t \in T} (r - t) \pmod q$

  4. 判定：

    • 如果 $V_S \neq V_T$，返回 FALSE（判定 $S \neq T$）。

    • 如果 $V_S = V_T$，返回 TRUE（判定 $S = T$）。

(2) 算法出错概率分析

我们需要分两种情况讨论：

  1. 情况一：当 $S = T$ 时（即两集合确实相等）

    • 此时对于任意的 $x$，多项式 $\prod(x-s)$ 和 $\prod(x-t)$ 是完全相同的。

    • 因此 $V_S$ 必定等于 $V_T$。

    • 算法总是返回 TRUE。

    • 出错概率为 0。

  2. 情况二：当 $S \neq T$ 时（即两集合不相等）

    • 构造差值多项式 $Q(x) = \prod_{s \in S} (x - s) - \prod_{t \in T} (x - t)$。

    • 由于 $S$ 和 $T$ 中各有 $n$ 个元素，$Q(x)$ 是一个最高次数不超过 $n$ 的非零多项式（因为 $S \neq T$，根据多项式的唯一分解定理，这两个多项式不恒等）。

    • 根据代数基本定理，一个 $n$ 次非零多项式在域 $\mathbb{F}_q$ 上至多有 $n$ 个根。

    • 算法出错（即产生“假阳性”，误报 $S=T$）的条件是：我们随机选取的 $r$ 恰好是 $Q(x)$ 的一个根，即 $Q(r) \equiv 0 \pmod q$。

    • 随机选取的 $r$ 共有 $q$ 种可能，而坏的 $r$（根）至多有 $n$ 个。

    • 出错概率：

      \[P(\text{Error}) = P(V_S = V_T \mid S \neq T) \le \frac{n}{q}\]

结论：算法的出错概率至多为 $\frac{n}{q}$。只要 $q$ 选得足够大（例如 $q \approx 2n$ 或更大），出错概率就可以控制在很小的范围内。

(3) 算法是否有偏？若有偏，偏什么？

根据上一题 PPT 中的定义逻辑：

  • 偏真 (True-biased)：当返回 TRUE 时解总是正确的（即没有假阳性，只有假阴性）。

  • 偏假 (False-biased)：当返回 FALSE 时解总是正确的（即没有假阴性，只有假阳性）。

分析本算法：

  • 当算法返回 FALSE ($V_S \neq V_T$) 时：

    这说明两个多项式在 $r$ 点的值确实不同，因此两个集合一定不相等。

    $\implies$ 返回 FALSE 总是正确的。

  • 当算法返回 TRUE ($V_S = V_T$) 时：

    这可能是因为 $S=T$，但也可能是 $S \neq T$ 却运气不好撞到了多项式的交点（根）。

    $\implies$ 返回 TRUE 时可能是错误的。

结论：

该算法是 偏假的 (False-biased)。

(注：这里的“偏假”是指算法在输出 False 结果时是绝对可信的，或者说算法的错误只会出现在将 False 的实例误判为 True 的方向上。这对应于标准复杂度类中的 co-RP 算法。)

三、为什么说若一个 NPC 或者 NPH 问题在多项式时间内可解当且仅当 NP = P？

  • 充分性（若问题多项式可解 $\rightarrow P=NP$）：

    • 根据定义，NP-Hard（或 NPC）问题是所有 NP 问题中最难的问题。对于任意一个 NP 问题 $L$，都存在一个多项式时间的归约算法将其转化为该 NP-Hard 问题。

    • 如果这个 NP-Hard 问题存在多项式时间的求解算法，那么对于任何 $NP$ 问题，我们都可以先通过归约将其转化为该问题，再进行求解。整个过程的时间复杂度仍为多项式级别。

    • 这意味着 $NP \subseteq P$。由于 $P \subseteq NP$ 总是成立，因此可得 $P=NP$。

  • 必要性（若 $P=NP \rightarrow$ 问题多项式可解）：

    • 若 $P=NP$，则所有 NP 问题都可以在多项式时间内解决。

    • 对于 NPC 问题，因其属于 NP，故显然可解。

    • 对于常见的 NP-Hard 优化问题，它们通常可以通过多项式次调用其对应的 NPC 判定版本来解决（例如通过二分法确定最优解）。因此，在 $P=NP$ 的前提下，这类 NP-Hard 问题也是多项式时间可解的。

四、考察上界 O(n) 的同步环非均匀算法。修改该算法，使得每个阶段中可以有 k 条消息在转发，并分析时间复杂度和消息复杂度。

这是一道关于同步环非均匀算法（Synchronous Ring Non-uniform Algorithm） 改进的经典题目。

原算法（上界为 $O(n)$ 的算法）极其保守，每个阶段（Phase）只允许 1 个特定的 ID 候选人发起消息，导致消息复杂度极低（$O(n)$），但时间复杂度极高（依赖于最小 ID 的值，即 $O(n \cdot m)$）。

将算法修改为 “每个阶段处理 $k$ 个候选人”（即批量处理 ID），是典型的时间与消息复杂度的权衡（Time-Message Trade-off）。

1. 算法修改方案

原算法中，第 $i$ 阶段（Phase $i$）专门用于检测 ID 为 $i$ 的节点。

修改后的算法将 ID 空间划分为大小为 $k$ 的块。

  • 阶段划分：算法按阶段 $p = 0, 1, 2, \dots$ 运行。

  • 候选人范围：第 $p$ 阶段负责检测 ID 在范围 $[p \cdot k, (p+1) \cdot k - 1]$ 内的节点。

  • 节点行为：

    • 在第 $p$ 阶段开始时，如果一个节点的 ID 属于当前阶段的范围，它就作为候选人发起一个包含自己 ID 的消息。

    • 转发规则（抑制策略）：

      • 当节点收到一个消息时，将消息中的 ID 与自己的 ID 进行比较。

      • 只有当 收到 ID < 自身 ID 时，才将消息转发给下一个邻居（保持求最小 ID 的逻辑）。

      • 否则，吞并（丢弃）该消息。

  • 终止：如果一个节点收到了自己的 ID，它宣布当选 Leader，算法终止。

  • 阶段时长：每个阶段持续 $n$ 轮，以确保消息能完整绕环一周。

2. 复杂度分析

假设环上节点的最小 ID 为 $m$。

时间复杂度：$O(n \cdot m/k)$

  • 分析：

    • 算法会一直运行空阶段，直到进入包含最小 ID $m$ 的那个阶段。

    • 包含 $m$ 的阶段序号为 $p = \lfloor m / k \rfloor$。

    • 在该阶段之前，有 $\lfloor m / k \rfloor$ 个阶段是空的（无人发起消息，网络保持沉默）。

    • 每个阶段耗时 $n$ 轮。

  • 计算：

    \[\text{Total Time} \approx (\lfloor \frac{m}{k} \rfloor + 1) \times n \approx O(\frac{n \cdot m}{k})\]

  • 结论：时间复杂度相比原算法降低了 $k$ 倍。

消息复杂度：$O(n \cdot k)$

  • 分析：

    • 在前 $p$ 个空阶段中，没有任何消息发送（消息数为 0）。

    • 在第 $p$ 阶段（活跃阶段），ID 在范围 $[p \cdot k, (p+1) \cdot k - 1]$ 内的所有节点都会发起消息。

    • 最坏情况下，该范围内可能存在 $k$ 个节点（即 $m, m+1, \dots, m+k-1$ 都在环上）。

    • 在这个阶段内，这就变成了一个简单的 LCR 算法（在 $n$ 个节点的环上，有 $k$ 个发起者）。

    • 最坏情况构造：假设这 $k$ 个节点的 ID 在环上是逆序排列的（沿着消息发送方向，先遇到大 ID，再遇到小 ID）。

      • 最小的 ID $m$ 会跑满一圈（$n$ 步）。

      • 次小的 ID 会跑很远直到遇到最小 ID。

      • …

      • 最大的候选 ID 也可能跑很远。

      • 每个消息最多跑 $n$ 步，共有 $k$ 个消息。

  • 计算：

    \[\text{Total Messages} \le k \times n = O(n \cdot k)\]

  • 结论：消息复杂度随着 $k$ 的增加而线性增加。

3. 总结

修改后的算法展示了分布式计算中经典的权衡 (Trade-off)：

  • 通过引入参数 $k$，我们牺牲了消息复杂度（从 $O(n)$ 增加到 $O(nk)$），换取了时间复杂度的显著降低（从 $O(nm)$ 降低到 $O(nm/k)$）。

  • 当 $k=1$ 时，退化回原算法。

  • 当 $k=n$（或 $k$ 覆盖所有 ID）时，变成标准的 LCR 算法（时间 $O(n)$，消息 $O(n^2)$）。

五、已知对于 MST 启发的 ∆TSP 问题有 $R_{MST}^\infty = 2$，请构造一个实例，使其渐近性能比为 2。

这是一个关于度量旅行商问题（$\Delta\text{TSP}$）中 最小生成树（MST）算法 最坏情况性能比的经典构造实例。该算法的渐近性能比 $R_{\infty}^{\text{MST}} = 2$。

以下是该实例的标准化数学描述与分析：

1. 实例构造 (Instance Construction)

考虑一个包含 $n$ 个顶点的完全图 $G = (V, E)$，其中 $n$ 较大。顶点集合定义如下：

  • 中心顶点：$O$

  • 外围顶点：$L = {L_1, L_2, \dots, L_{n-1}}$，这些顶点在逻辑上排列成一个环。

距离函数 $d(u, v)$

定义各点对之间的度量距离，使其满足三角不等式：

  1. 辐射边：$d(O, L_i) = 1$，对于所有 $i = 1, \dots, n-1$。

  2. 环邻边：$d(L_i, L_{i+1}) = 1$（其中 $L_n \equiv L_1$），即环中相邻的叶顶点距离为 1。

  3. 其余边：$d(L_i, L_j) = 2$，对于所有非相邻的叶顶点对（即 $|i-j| \pmod{n-1} \neq 1$）。

2. 算法步骤与成本计算

2.1 最小生成树 (MST) 的计算

由于所有连接 $O$ 与 $L_i$ 的边权均为最小（等于 1），且连接所有叶顶点的边权至少为 1。

  • 构造：MST 是以 $O$ 为中心的星形图（Star Graph），包含边 ${(O, L_i) \mid i=1, \dots, n-1}$。

  • MST 成本：

    \[W(\text{MST}) = \sum_{i=1}^{n-1} d(O, L_i) = n - 1\]

2.2 启发式游程 (MST 加倍与捷径)

算法通过加倍 MST 的边构造欧拉回路，再通过“跳过”重复顶点（Shortcut）生成 TSP 游程。

  1. 欧拉游程：$O \to L_1 \to O \to L_2 \to O \dots \to L_{n-1} \to O$。其总长度为 $2 \times W(\text{MST}) = 2(n-1)$。

  2. 构造坏情况捷径：

    我们可以选择访问叶顶点的顺序 $\pi$，使得没有任何两个连续访问的叶顶点在原环中是相邻的。

    • 例如，在 $n$ 足够大时，选取 $\pi$ 使得 $d(L_{\pi(k)}, L_{\pi(k+1)}) = 2$。

    • 启发式游程路径：$O \to L_{\pi(1)} \to L_{\pi(2)} \to \dots \to L_{\pi(n-1)} \to O$。

  3. 近似解成本：

    \[C_{\text{MST}} = d(O, L_{\pi(1)}) + \sum_{k=1}^{n-2} d(L_{\pi(k)}, L_{\pi(k+1)}) + d(L_{\pi(n-1)}, O)\] \[C_{\text{MST}} = 1 + (n-2) \times 2 + 1 = 2n - 2\]

3. 最优解 (Optimal Tour)

一个接近最优的 TSP 游程是沿着外围环移动，最后通过中心点 $O$ 返回。

  • 最优路径示例：$L_1 \to L_2 \to \dots \to L_{n-1} \to O \to L_1$。

  • 最优解成本：

    \[C_{\text{OPT}} = (n-2) \times 1 \text{ (相邻叶顶点边)} + 1 \text{ (从 } L_{n-1} \text{ 到 } O) + 1 \text{ (从 } O \text{ 到 } L_1)\] \[C_{\text{OPT}} = n\]

4. 性能比分析 (Approximation Ratio)

计算启发式算法结果与最优解的比率：

\[R_n = \frac{C_{\text{MST}}}{C_{\text{OPT}}} = \frac{2n - 2}{n} = 2 - \frac{2}{n}\]

当顶点数 $n$ 趋于无穷大时：

\[\lim_{n \to \infty} R_n = 2\]

严格度量空间的修正：

如果需要避免 $d(L_i, L_k) = d(L_i, L_j) + d(L_j, L_k)$ 的等式情况，可以将相邻叶顶点的距离设为 $1 + \epsilon$。此时比率将变为 $\frac{2n-2}{n + (n-2)\epsilon}$，在 $\epsilon \to 0$ 且 $n \to \infty$ 时依然收敛于 2。

附录


You May Also Enjoy

Shell 自动补全 + 终端美化汇总：zsh、cmd 和 powershell

2 minutes read

Published:

zsh 是一个兼容 bash 的 shell, 还提供了强大的自动补全功能，并拥有丰富的主题和插件支持。Oh-my-zsh 项目提供了很多漂亮的主题，其中我个人比较喜欢的是 powerlevel10k。由于它实在美观，了解到美化 windows 终端的 oh-my-posh 后，我也把 cmd 和 powershell 一并美化成了 powerlevel10k 的风格，并通过 Clink 实现了自动补全功能。具体的操作步骤在此记录。

WSL 代理配置

less than 1 minute read

Published:

介绍使用 Clash for Windows 配置 WSL 代理的两种方法。