Lecture 7: Failure Detectors and Membership — 故障检测器与成员管理
Lecture 7: Failure Detectors and Membership — 故障检测器与成员管理
讲义对应：CS 425 FA2026 Lecture 5-6（
L5-6.a.FA26.txt，Failure Detection and Membership，61 页）；Lecture 6b（L6.b.FA26.txt，Grids，16 页）；补充：FA2025 Lecture 6（L6.FA25.txt，内容更全，含 Grid Computing 专题） 教材对应：Coulouris 5th Ed. Ch. 15（Time and Global States，含 failure detector 与 membership 讨论）；Ch. 12（Distributed Systems 中的 group communication） 阅读材料：A. Das, I. Gupta, A. Motivala, SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol, DSN 2002；I. Gupta, T. D. Chandra, G. S. Goldszmidt, On Scalable and Efficient Distributed Failure Detectors, PODC 2001；T. D. Chandra, S. Toueg, Unreliable Failure Detectors for Reliable Distributed Systems, JACM 43(2), 1996；R. van Renesse et al., A Gossip-Style Failure Detection Service, Middleware 1998
7.1 概述
本讲回答一个看起来简单、实际上定义了整个分布式容错领域边界的问题：在一个会丢包、会拥塞、会延迟的网络上，一个进程如何知道另一个进程已经死了？ 讲义开门见山地指出，在数据中心里故障是常态而不是例外：假设单台机器（操作系统/磁盘/主板/网络）的平均故障间隔是 10 年（120 个月），那么 120 台机器的集群每隔 1 个月就会坏一台，12000 台机器的数据中心平均每 7.2 小时就有一台机器出故障，而”软故障”（进程被挂起、GC 停顿、网络抖动）比硬故障还要频繁得多。
故障检测器（Failure Detector, FD）是几乎一切容错机制的前置条件：复制（副本要剔除坏副本）、选主（leader 要确认 follower 还在）、共识（Paxos/Raft 的 quorum 要按存活成员计算）、成员管理（membership）、分布式数据库的读修复、MapReduce 的 straggler 重执行，全都建立在”我知道谁还活着”这个前提上。因此本讲先讲故障检测的根本困难与检测器的理论性质（完备性、准确性），再讲四类具体算法（心跳、Ping-Ack、Gossip-style、SWIM）与超时估计，最后把检测器放回成员管理的整体结构中，并补上课程表上与故障检测放在一起讲的 Grid 计算。
本讲在整门课中的位置极为关键：第 5-6 讲建立的”不可靠通信 + 进程组”模型，在这里第一次遭遇真正的时间不确定性。讲义明确点出，完备性与准确性在丢包网络中不可能同时成立（Chandra-Toueg），而”如果可以同时成立，就能解共识问题，但共识在异步系统中已知不可解”——这句话直接指向第 17 讲的 FLP 不可能性定理与 CAP 的取舍。学完本章你应当能回答：为什么所有真实的容错系统都是在”一个天生不可靠的组件”之上做正确性论证？
7.2 核心概念与分布式机制图解
7.2.1 故障检测与成员管理服务（Group Membership Service）
定义与目的：成员管理协议（Membership Protocol）为进程组中的每个进程维护一份组员列表（Group Membership List），列表随成员的加入（join）、自愿离开（leave）与故障（failure）而更新，并通过 API/回调交给上层应用查询。讲义给出的典型使用者包括 gossip 协议、overlay 网络、DHT（如 Chord）、分布式数据库。
直观解释（”它是什么？”）：把成员管理服务想成公司的员工名册 + 前台。名册要回答”现在公司里有哪些人”；前台要处理入职（join）、离职（leave）、以及”某人联系不上了”（failure）。麻烦在于：名册不是一个人写的，而是每个员工各自抄一份，而且抄写用的”通知渠道”（不可靠网络）随时会丢消息——所以每个人手上的名册随时可能略有不同，甚至有人会把还在上班的同事写成”已离职”。故障检测器就是那个不停打电话确认”你还在吗”的同事。
机制图解：讲义把成员管理服务拆成两个子协议，这是全讲的骨架。
应用进程 pi
│ 查询：现在的成员有哪些？
▼
┌───────────────────────┐
│ Group Membership │
│ List │
└───────┬───────┬───────┘
写入 joins/leaves/failures 读取成员列表
│ │
┌──────────┴──────┐ │
│ │ │
┌─────▼─────┐ ┌─────▼─────┐ │
│ Failure │ │Dissemin- │ │
│ Detector │────►│ ation │ │
│ (II) │ │ (III) │ │
└─────┬─────┘ └─────┬─────┘ │
│ │ │
└────────┬────────┘ │
▼ │
不可靠通信（Unreliable Communication）
│
▼
pj / 网络中的其他成员
- 子协议 II：故障检测器（Failure Detector）——尽快发现”某个进程已经崩溃”，即讲义中”some process finds out quickly”。
- 子协议 III：信息传播（Dissemination）——把成员变更（join/leave/failure）扩散到全组。
关键假设与系统模型：本讲针对进程组系统（云/数据中心、复制服务器、分布式数据库），只考虑 fail-stop（崩溃）故障，不考虑 fail-recover（崩溃后恢复并重新加入，需要持久化状态与恢复协议）。通信用不可靠网络：消息可能丢失、延迟、乱序。规模目标是 1000+ 进程，且每条进程的负载要均等（不能有中心瓶颈）。
为什么”检测”和”传播”必须分开（SWIM 论文的核心洞见）：传统 all-to-all 心跳把两件事揉在一起——为了让所有人都尽快知道某成员死了，心跳必须发给所有人，于是每条进程的负载随 N 线性增长、全网消息量随 N² 增长。SWIM 的作者意识到：故障检测只需要”某个人”尽快发现（检测），”所有人”知道可以慢一点、靠感染式传播达成。把这两件事解耦，是本章所有可扩展方案的共同起点。
7.2.2 异步系统的根本困难：崩溃与”慢”无法区分（Crash vs. Slow）
定义与目的：在异步系统模型（asynchronous system model）中，进程间消息的传输延迟没有上界，进程的执行速度也没有下界（没有时钟同步、没有超时保证）。在这个模型下，”进程 pj 崩溃了”与”pj 只是很慢，或 pj 与 pi 之间的网络只是很慢”这两种情况，对 pi 而言在有限时间内不可区分。
直观解释（”它是什么？”）：你给同事打电话，响了很多声都没人接。有几种可能：（1）他不在座位上（相当于崩溃）；（2）他在开会手机静音（相当于进程被挂起）；（3）信号不好，其实他已经接起来了只是你听不到（相当于网络延迟/丢包）。你能做的只有”再等久一点”或者”打给他旁边的同事问问”——但无论等多久，你都无法百分之百断定他不在，因为”等得还不够久”永远是一个可能的解释。SWIM 论文把这句话写成了规范表述：a process that is losing messages is indistinguishable from one that has failed（一个正在丢消息的进程与一个已经故障的进程不可区分）。
机制图解：把两个不同的物理世界画成同一个观察者视角。异步模型只要求”消息最终会到达（如果发送者与接收者都不故障）”，而不给延迟上界，因此构造下面两个执行（execution）是合法的：
执行 E1：pj 真的崩溃了 执行 E2：pj 只是"慢"，网络也只是"慢"
pi pj pi pj
| | | |
|----- ping ---------►X（崩溃） |----- ping ---------------►| （消息在途，
| | | （延迟 10^9 秒） | 尚未到达）
| 等待 T 秒 | | 等待 T 秒 |
| → 判定 pj 已死 | | → 判定 pj 已死 |
| | | |
| | | （10^9 秒后 pj 回复 ack）|
| | |◄---- ack -----------------|
└── pi 看到的全部现象：T 秒内没有收到任何来自 pj 的消息 ──┘
（两个执行在 pi 的观察下逐位相同）
关键假设与系统模型：只要模型允许任意大的延迟，上面两个执行就都合法，而检测器内部状态与输出完全相同。这就是 impossibility 的来源。走出困境只有三条路，它们对应分布式系统理论的三次”绕过 FLP”（第 17 讲会详细展开）：
- 部分同步假设（partial synchrony）：假设”系统大部分时间同步，只是偶尔不同步”——于是可以用超时，但只能要求”最终正确”（◇ 型检测器）。Paxos / Raft 的 leader 选举正建立在这条路上。
- 随机化（randomization）：用随机币打破确定性，得到以概率 1 终止的共识（但期望轮数无限，且需要密码学/概率论证）。
- 故障检测器增强（failure detector oracle）：给系统加一个不可靠但足够有用的故障检测器，让共识重新变得可解（Chandra-Toueg 路线）。
两个方向的错误：任何实际检测器都有两类错误：
- 误判（false suspicion / false positive）：把活着的进程判成死的。代价：把健康节点踢出组（副本下线、触发无谓的选主、数据搬迁、甚至基于错误成员视图做出不一致的决定）。
- 漏判（false negative）：把死了的进程长期当成活的。代价：请求被永远发给一个不会响应的节点，quorum 永远凑不齐，系统永久阻塞（liveness 彻底丧失）。
讲义明确给出的工程取舍：完备性（不漏判）永远保证，准确性（不误判）只做概率性保证。原因很直白：漏判会让系统”卡死”，误判只会让系统”抖动”；而且漏判其实是可以被工程手段彻底解决的——一个真的崩溃的进程不会再发心跳，只要”等得足够久”（并配合轮询遍历保证一定探测到它），它一定会被某个正确进程发现。但准确性不可能被彻底解决，因为”慢”与”死”不可区分。于是真实系统的做法是：把检测器的误判率压到工程上可接受的水平，并在上层用 quorum、租约（lease）、怀疑机制（suspicion）等机制容忍它。这就是本章最重要的设计原则：故障检测器是分布式系统的眼睛，但它天生不可靠；容错系统的正确性论证必须建立在检测器会出错的前提之上。
7.2.3 故障检测器的四个性质：完备性、准确性、速度、规模
定义与目的：讲义用四个维度刻画一个分布式故障检测器，它们同时也是应用可指定（application-defined）的需求。
| 性质 | 含义 | 讲义的保证口径 |
|---|---|---|
| 完备性 Completeness | 每个故障都被检测到（each failure is detected） | 永远保证（Guaranteed always） |
| 准确性 Accuracy | 没有错误的检测（there is no mistaken detection） | 部分/概率保证：在时间 $T$ 内误判概率为 $P_M(T)$ |
| 速度 Speed | 从故障发生到第一个非故障进程发现它的时间 | 目标 $T$ 个时间单位 |
| 规模 Scale | ① 每个成员的负载均等（no bottleneck / single point of failure）② 网络消息负载 | 比较 $N \cdot L$（总消息率） |
关键补充：讲义特别强调”尽管存在任意的并发进程故障（in spite of arbitrary simultaneous process failures）“——这是与很多教科书例子不同的地方：真实数据中心里不是一次只坏一台机器，而是成批坏（机房掉电、机架交换机故障）。因此”环状心跳在多个同时故障下检测时间不可预测”是一个致命的缺陷。
机制图解（必需的时序图）：下面把心跳与Ping-Ack两种最基本的探测方式画在两条对齐的时间轴上。注意两者最本质的差别不是”消息方向”，而是：心跳是发送者驱动的无状态广播，接收者只能靠”多久没收到”来推断；Ping-Ack 是探测者驱动的请求-应答，探测者能直接测出往返时间（RTT），从而为自适应超时提供样本。
Heartbeating（单向、周期、发送者驱动） Ping-Ack（请求-应答、探测者驱动、可测 RTT）
pi pj pi pj
| | | |
t0 |---- HB(seq=1) ----->| t0 |--------- PING ---------->|
t1 |---- HB(seq=2) ----->| t1 |<-------- ACK ------------| RTT = t1 - t0
t2 |---- HB(seq=3) ----->| t2 |--------- PING ---------->|
| (丢包) | | （链路拥塞） |
t3 | ✗ 无 HB | t3 | 等待 T_ack 超时 ──┐ |
| | | │ |
t4 | 距离上次收到已超过 | t4 |<── 触发间接探测 ─────┘ |
| T_hb ⇒ pj 判 pi 死 | | 或直接判死（无怀疑机制时） |
| | | |
判死依据：一个"缺席"事件 判死依据：一个"超时未应答"事件
（无法获得 RTT 样本） （可获得 RTT 样本 ⇒ 可自适应）
7.2.4 完备性与准确性的分类：Chandra-Toueg 故障检测器
定义与目的：Chandra 与 Toueg 把”完备性”和”准确性”各自细化为强弱两档，得到一张可以精确讨论”某个检测器能解什么共识问题”的分类表。
- 强完备性（Strong Completeness）：每个最终崩溃的进程，最终被所有正确进程怀疑。
- 弱完备性（Weak Completeness）：每个最终崩溃的进程，最终至少被某个正确进程怀疑。
- 强准确性（Strong Accuracy）：没有任何正确进程被怀疑。
- 弱准确性（Weak Accuracy）：存在某个正确进程从未被怀疑。
四个经典组合（$\Diamond$ 读作 “eventually”）：
| 检测器 | 完备性 | 准确性 | 含义 | 现实性 |
|---|---|---|---|---|
| Perfect P | 强 | 强 | 从不冤枉任何人，且每个故障都被所有人发现 | 异步系统中不可能实现（需同步假设） |
| Eventually Perfect $\Diamond P$ | 强 | 强（最终） | 初期可能冤枉人，但存在某个时刻之后不再冤枉 | 部分同步系统中可实现，最强实用类型 |
| Strong S | 强 | 弱（始终） | 从不冤枉某个”被指定的”正确进程，但可能冤枉别的 | 比 P 弱，理论意义为主 |
| Eventually Strong $\Diamond S$ | 强 | 弱（最终） | 最终存在一个不被冤枉的正确进程（天然的 leader 候选） | Paxos/Raft 实际依赖的类型 |
| Weak W | 弱 | 弱 | 最弱的组合 | 理论下界 |
为什么”最终准确”就够用了：Raft 的 leader 选举只要求”最终能选出一个稳定的 leader”——它允许某段时间里有节点被错误地怀疑（于是反复重选），但只要存在某个时刻之后不再有误判，选举就会稳定下来，系统收敛。这正是 $\Diamond S$ 的语义。而 Perfect P 要求”从第一秒起就永不误判”，这需要网络延迟有已知上界（同步系统），在真实网络里做不到。
ASCII 图：不同检测器的”强弱”沿两条轴展开：
准确性（不冤枉好人）
弱 ◄──────────────────────────► 强
┌──────────────┬──────────────┬──────────────┐
强 │ │ │ │
▲ │ W │ S │ P │
│ │ │ │ （不可实现） │
完 ├──────────────┼──────────────┼──────────────┤
备 │ │ │ │
性 │ │ ◇S │ ◇P │
│ 弱 │ │ （Paxos/Raft │ （部分同步可 │
▼ │ │ 依赖） │ 实现的最强） │
└──────────────┴──────────────┴──────────────┘
关键假设与系统模型：在异步 + 可能丢包的网络中，”完备性 + 准确性同时成立”是不可能的（讲义原话：Impossible together in lossy networks [Chandra and Toueg]）。讲义还给出了两条判断捷径：
- 什么检测器是”100% 完备”的？提示：平凡的（trivial）——把所有进程永远标记为已死，完备性当然成立（每个故障都被”检测”了），但准确性为零。
- 什么检测器是”100% 准确”的？——永远不怀疑任何进程，准确性当然成立，但完备性为零。
- “如果存在既完备又准确的检测器会怎样？”——那就能解共识问题；但共识在异步系统中已知不可解（FLP），所以这样的检测器不可能存在。这是一条漂亮的归约链，把故障检测的不可能性与共识的不可能性绑在了一起。
7.2.5 从检测器到成员管理：三种成员视图一致性路线
定义与目的：把故障检测（子协议 II）与传播（子协议 III）组合起来，就得到成员管理协议。讲义按”成员视图的一致性强度”把方案分成三类：
| 路线 | 成员列表形态 | 代表系统 | 特点 |
|---|---|---|---|
| 强一致（Strongly consistent） | 任何时刻所有节点的完整列表一致 | Virtual Synchrony（虚拟同步）、Isis/Ensemble | 语义最强，但扩展性受限，成员变更成为同步点 |
| 弱一致（Weakly consistent） | 几乎完整（almost-complete）：视图可能短暂不一致，最终收敛 | Gossip-style FD、SWIM | 可扩展（本讲重点） |
| 部分随机（Partial-random） | 每个节点只保留部分随机邻居列表 | SCAMP、T-MAN、Cyclon | 用于大规模 overlay 的邻居管理 |
关键洞察：成员变更本身就是一个分布式一致性问题。让 N 个节点对”当前成员集合”达成一致，与让它们对”某个值”达成一致，在异步 + 故障模型下是等价难度的问题——因为任何成员视图的变更都必须”知道谁还活着”，而这就回到了 7.2.2 的困难。SWIM 论文因此明确选择了弱一致路线，并指出”强一致规格可能有根本性的可扩展性限制”。这条取舍在后面的 7.2.10 会展开：弱一致成员视图 + quorum 防护是工业界的主流组合，而强一致成员视图（etcd/ZooKeeper 的 Raft 成员变更）则用共识代价买来”成员配置不会脑裂”的保证。
7.2.6 心跳检测的三种拓扑：集中式、环状、全互探
定义与目的：心跳（Heartbeating）是最古老也最直观的检测方式：进程 $p_i$ 周期性地递增一个序号（heartbeat sequence number） $l$ 并广播出去；接收者若在超时时间内没有收到 $p_i$ 的新心跳，就把 $p_i$ 标记为故障。
机制图解：三种拓扑各有致命弱点，讲义用它们引出”为什么需要更好的检测器”。
(a) 集中式心跳 Centralized (b) 环状心跳 Ring (c) 全互探 All-to-All
所有心跳发给 pj 沿逻辑环单向传递 每个节点给所有其他节点发
p1 ──┐ p1 ──► p2 p1 ◄──► p2
p2 ──┤ ▲ │ ▲ ╲ ╱ ▲
p3 ──┼──► pj（中心） │ ▼ │ ╳ │
... │ p4 ◄── p3 p3 ◄──► p4
pn ──┘ （全连接）
缺点：热点、单点故障 缺点：多个同时故障时 缺点：单条心跳丢失
（pj 自己也可能是故障点） 检测时间不可预测 即造成误判；消息 O(N²)
| 拓扑 | 每条进程的负载 | 消息总量 | 完备性 | 准确性 | 致命弱点 |
|---|---|---|---|---|---|
| 集中式 | 1 条心跳 | $O(N)$ | 依赖中心 | 中心误判影响全体 | 热点（hotspot），中心自身是单点故障 |
| 环状 | 1 条心跳 | $O(N)$ | 环断则不完备 | 多故障下不可预测 | 多个同时故障导致检测时间不可预测 |
| 全互探 | $N-1$ 条心跳 | $O(N^2)$ | 强（每人独立探测） | 单条心跳丢失即误判 | 负载与带宽随 N 平方增长 |
关键解说（讲义原文的要点）：
- 集中式：$p_j$ 无法区分”$p_i$ 崩了”与”$p_i$ 的消息被丢了/延迟了”；为了完备性，$p_j$ 只能把 $p_i$ 判为故障——这就是 7.2.2 的直接体现。此外 $p_j$ 本身不能故障。
- 环状心跳：每个节点只监测环上的后继。单个故障能定位，但多个同时故障时，”谁该报告谁”变得不可预测（可能形成一段无人报告的断链）。讲义特别提醒：随着组规模变大，同时多故障的概率也在变大，所以这不是罕见情况。真实系统中 IBM SP2 等集群机就使用了环状故障检测。
- 全互探：负载均等（每条进程发 $N-1$ 条），完备性强，但只要丢失一条心跳就可能产生一次误判——在没有重传/多路径的情况下准确性极差。这正是”用 gossip 提高鲁棒性”的动机：让关于同一节点的存活信息有多条独立路径到达每个观察者。
7.2.7 Ping-Ack 直接探测（Direct Probing）
定义与目的：探测者 $p_i$ 主动向目标 $p_j$ 发送 PING，$p_j$ 回 ACK；若在 $T_{ack}$ 内未收到 ACK，$p_i$ 就怀疑 $p_j$ 已故障。与心跳的关键差别在于探测是请求-应答式（request-response）的，因此：
- 探测者能直接测量 RTT，从而自适应地设置超时（7.2.12 节）；
- 探测者能控制探测频率与目标选择（随机化、轮转、按拓扑加权）；
- 探测是双向确认：收到
ACK同时证明”$p_j$ 活着”且”$p_i \to p_j$ 与 $p_j \to p_i$ 两条路径当前可用”。
机制图解：见 7.2.3 的时序图（右半部分）。需要强调的是：
"谁能检测谁"的差别
┌──────────────┬────────────────────────────┬─────────────────────────────┐
│ │ 心跳（Heartbeating） │ Ping-Ack（直接探测） │
├──────────────┼────────────────────────────┼─────────────────────────────┤
│ 消息模式 │ 单向广播，周期性 │ 请求-应答，可随机触发 │
│ 谁驱动 │ 被检测者自己（"我活着"） │ 检测者（"你还在吗"） │
│ 能否测 RTT │ 否（只能测"到达间隔"） │ 是（直接测往返时间） │
│ 一条消息的价值 │ 一次心跳可服务所有接收者 │ 一次探测只服务一个探测者 │
│ 故障时的行为 │ 静默（靠"缺席"推断） │ 无应答（靠"超时"推断） │
│ 误判来源 │ 连续丢包 / 拥塞 │ 丢包 + 单向路径拥塞 │
└──────────────┴────────────────────────────┴─────────────────────────────┘
关键假设：探测者需要维护被探测者的最近确认时间戳与（自适应方案中）RTT 估计。所有探测都假定”消息可能丢失、延迟无上界”，因此判定只能基于超时，而超时必然引入误判。
7.2.8 Gossip 风格的故障检测（Gossip-style Failure Detection）
定义与目的：让每个节点周期性地把自己的成员表副本（含每个成员的心跳计数）gossip（闲聊式地随机发送）给若干个随机节点；收到的人把对方的表与自己的表合并（merge）；当某个表项的心跳计数长时间不增长时，就把该成员标记为故障。这套机制来自 van Renesse 等人的工作，是讲义阅读材料之一。
直观解释：”向所有人确认存活”太贵，于是改成”闲聊“：每个人把听来的消息讲给几个随机的人听，消息像谣言一样在人群里扩散。一个人是否还活着这件事，会被很多条互相独立的”传闻路径”证实，因此单条消息丢失不再导致误判——这就是它比全互探心跳准确性好的原因。
机制图解（讲义的具体数值例子）：每个表项有三个字段：地址（Address）、心跳计数（Heartbeat Counter）、本地时间戳（Time (local)）——注意时间戳是接收者本地时钟上”最后一次听到关于它的新消息”的时刻，而不是发送者的时间。
节点 2 在本地时间 70 时收到的 gossip（来自节点 1、3、4 的合并结果）
┌─────────┬──────────────────┬─────────────────┐
│ Address │ Heartbeat Counter│ Time (local) │
├─────────┼──────────────────┼─────────────────┤
│ 1 │ 10120 │ 70 │ ← 刚刚直接从 1 听到
│ 2 │ 10110 │ 64 │ ← 自己（16 单位前刷新过）
│ 3 │ 10098 │ 70 │ ← 刚从 3 的 gossip 里听到
│ 4 │ 10111 │ 65 │ ← 已经 5 个单位没更新
└─────────┴──────────────────┴─────────────────┘
讲义提问：若当前本地时间是 80，且 Tfail = 12，节点 2 会判谁 failed？
计算：age(j) = 80 - Time(local)
age(1) = 10 ≤ 12 → 正常
age(2) = 16 → 忽略（自己，不能判自己死）
age(3) = 10 ≤ 12 → 正常
age(4) = 15 > 12 → 【判定节点 4 故障】
答案：只有节点 4 被标记为 failed。
协议步骤（讲义原文口径）：
- 节点周期性 gossip 自己的成员表：随机选若干节点，把表发给它们；
- 收到后与本地成员表合并（同一条目取更大的心跳计数，并把本地时间戳置为”现在”）；
- 当某条目的心跳计数在 $T_{fail}$ 秒内没有增长时，该成员被判定为故障；
- 再经过额外的 $T_{cleanup}$ 秒，才把它从成员表中删除。
为什么需要额外的 $T_{cleanup}$？（讲义专门提问）如果一判定失败就立刻删除表项，会出问题：来自其他节点的、在途的旧 gossip 会把该表项重新插回来。讲义的第二张图正是这个现象——节点 3 被删掉后，又因为收到一条携带旧计数的 gossip 而”复活”，成员表出现抖动（flapping）。$T_{cleanup}$ 的作用是让”删除”推迟到所有可能携带该节点的在途消息都已过期之后，这样”死而复生”不再可能；同时它也让”$p_i$ 已死”这条信息有时间传播到全组，避免不同节点对同一条目做出相反的处置。
时间复杂度分析（讲义的核心结论）：
- 一条 gossip 传播到全组需要 $O(\log N)$ 轮（这是流行病/谣言传播的经典结论）。直觉：每一轮，知道消息的人数翻倍（每个知情者传染给若干个随机节点），因此 $1 \to 2 \to 4 \to \dots \to N$ 需要 $\log_2 N$ 轮。
- 因此，单条心跳在带宽充足时，$O(\log N)$ 时间即可传遍全组。
- 但要让 N 条心跳都传遍，需要区分带宽预算：
- 每条进程允许 $O(N)$ 带宽（每条 gossip 携带全表）：$N$ 条心跳整体仍是 $O(\log N)$ 时间；
- 每条进程只有 $O(1)$ 带宽（每条消息只带常数个条目）：需要 $O(N \log N)$ 时间；
- 每条进程 $O(k)$ 带宽：介于两者之间（$O(\frac{N}{k}\log N)$ 量级）。
- 讲义给出的定量结果：若 gossip 周期为 $t_g$、检测时间为 $T$，则 $T = \log N \cdot t_g$，每条进程的负载 $L = N / t_g = N \log N / T$——比全互探心跳的 $L = N/T$ 多了一个 $\log N$ 因子，这是”用带宽换准确性”的代价。
三个两难（讲义明确列出的权衡三角）：
- gossip 周期 $T_{gossip}$ 调小会怎样？——检测更快、传播更快，但消息量线性上升（带宽代价）。
- $T_{fail}$ 与 $T_{cleanup}$ 调大会怎样？——误判率 $P_{mistake}$ 指数下降，但检测时间线性变长（故障节点在列表里”赖”得更久）。
- 结论：误判率 vs 检测时间 vs 带宽构成一个不可能三角，任何基于超时的方案都只能在这个三角里选一个点。SWIM 的价值正在于把这个三角的边往外推：用随机探测 + 间接探测 + 怀疑机制，在同样的负载下同时改善检测时间与误判率。
7.2.9 SWIM：随机探测 + 间接探测 + 怀疑机制
定义与目的：SWIM（Scalable Weakly-consistent Infection-style process group Membership）是 Cornell 的 Das、Gupta、Motivala 在 DSN 2002 提出的成员协议，也是本讲的核心。它由三个子协议构成：
- 故障检测（Failure Detection）：随机点对点探测（
ping）+ 间接探测（ping-req）； - 信息传播（Dissemination）：感染式（infection-style）把成员变更捎带在探测消息上，不产生额外消息；
- 怀疑机制（Suspicion）：不立即判死，而是先怀疑（Suspect），给被怀疑者一个反驳（refute）的机会。
为什么它能同时赢三局：SWIM 论文的出发点是”把故障检测与成员传播解耦“。传统心跳之所以要发给所有人，是因为它想让所有人同时知道故障；但检测其实只需要某一个人先知道，传播可以慢慢来（$O(\log N)$ 轮）。解耦之后，故障检测就可以用随机点对点探测：每个协议周期只 ping 一个随机成员，于是每进程负载恒为常数、与组规模无关；而”某进程崩溃”这件事被发现的期望时间也是常数（与 $N$ 无关）。
机制图解 1：完整时序图（ping → 超时 → ping-req → 间接 ack）
Mi（探测者） Mk（K 个随机代理之一） Mj（被探测者）
| | |
t0 |------- PING(seq) --------->| | ① 直接 ping
| |----- PING(seq,Mj) ---------->| （走 Mi→Mj 直连）
| | |
| ✗ 直接路径拥塞： | |
| PING 或 ACK 丢失 | |
| | |
t1 |◄── 超时 T_ack 触发 ────────┤ | ② 超时点 1
|------- PING-REQ(seq,Mj) -->| | ③ 请代理代为探测
|------- PING-REQ(seq,Mj) -->|（另 K-1 个代理，图中省略） |
| |----- PING(seq,Mj) ---------->| ④ 代理走 Mk→Mj 路径
| |<---- ACK --------------------| ⑤ Mj 活着
|<------ ACK(seq,Mj) --------| | ⑥ 代理把 ack 转回
| | |
t2 | 协议周期 T' 结束：收到了间接 ack ⇒ 不判死， | ⑦ 周期结束点
| 也不广播任何 Suspect 消息 |
时序要点：超时点 $t_1$（T_ack）触发间接探测，周期结束点 $t_2$（$T^{\prime}$）才做最终判定。因此 $T_{ack}$ 必须远小于协议周期 $T^{\prime}$（SWIM 论文要求 $T^{\prime}$ 至少是 RTT 估计的 3 倍），否则间接探测的消息来不及在一个周期内回来。
间接探测解决什么问题：它解决的是单条网络路径拥塞导致的假阳性。如果 $M_i \to M_j$ 这条路径刚好在丢包（交换机队列溢出、跨机架链路抖动），直接 ping 必然超时；但只要 $M_i$ 与 $M_j$ 各自与其他节点的路径正常，请 $K$ 个随机代理绕道探测就能拿到 ack。SWIM 论文明确指出这样做的目的就是避开 $M_i$ 与 $M_j$ 之间那条可能拥塞的路径（to avoid the effect of any congestion on the network path between Mi and Mj）。
机制图解 2：怀疑机制的状态机（Alive → Suspect → Confirm/Failed，以及 refute 回边）
① 本协议周期内既无直接 ack 也无间接 ack
⇒ 本地标记 Suspect，并广播 Suspect(inc)
┌──────────┐ ───────────────────────────────────────► ┌────────────┐
│ Alive │ │ Suspected │
└──────────┘ ◄─────────────────────────────────────── └────────────┘
▲ ② 收到该成员的 acK（直接或间接） │
│ 或收到 Alive(inc' > inc) 消息 │
│ │
│ ④ refute 回边：被怀疑者 Mj 收到关于自己的 │ ③ 怀疑超时
│ Suspect(inc) ⇒ 自增 incarnation ⇒ 广播 │ T_suspect 到期
│ Alive(inc+1) ⇒ 全组撤销怀疑（"复活"） ▼
│ ┌────────────┐
└───────────────────────────────────────────────── │ Failed │
（只有在收到更高 inc 的 Alive 时才可能回到 Alive； └────────────┘
一旦 Confirm 为 Failed，在 SWIM 中不可回退） 广播 Confirm(inc)
incarnation number（化身号）的关键设计：一个进程可能在一生中被多次怀疑，这些 Suspect/Alive 消息必须能被区分先后。SWIM 的解法是给每个成员表项加一个全局的 incarnation number（inc）：
- 成员 $M_j$ 加入时 $inc_j = 0$；
- 只有 $M_j$ 自己可以增加 $inc_j$——当它通过传播组件得知”有人在这个 inc 上怀疑我”时，就自增 inc 并广播
Alive(inc+1)； - 优先级规则（讲义原文口径）：
- 更高的 inc 覆盖更低的 inc（不管消息类型）；
- 同一个 inc 内：
Suspect(inc)覆盖Alive(inc)； Confirm/Failed(inc)覆盖一切（任何 inc 的Alive与Suspect）。
| 收到的新消息 | 本地状态 Alive(k) | 本地状态 Suspect(k) | 本地状态 Failed(k) |
|---|---|---|---|
Alive(k), $k >$ 本地 inc | 更新 | → Alive(k) | 更新（除非已 Confirm） |
Suspect(k), $k >$ 本地 inc | → Suspect(k) | 更新 | 更新 |
Alive(k), $k =$ 本地 inc | 无变化 | 无变化（同 inc 下 Suspect > Alive） | 无变化 |
Suspect(k), $k =$ 本地 inc | → Suspect(k) | 无变化 | 无变化 |
Confirm/Failed(k), 任意 $k$ | → Failed | → Failed | 无变化 |
为什么这套设计能把”永久误判”降级为”暂时误判”：没有怀疑机制时，一次误判（一条 ping 丢了、一次 GC 停顿）就会让一个健康节点被立刻踢出组——它”受到极重的惩罚”（SWIM 论文原话）。有了怀疑机制，误判只会让它短暂进入 Suspect 状态；只要它还在正常工作，它就会在下一个协议周期被别的节点成功 ping 到（状态回到 Alive），或者更直接地自己发现被怀疑并自增 inc 反驳，从而从未离开过组、也无需重新加入。代价是：检测时间被拉长了 $T_{suspect}$（怀疑超时），这正是”用检测时间换误判率”的显式旋钮。
时间有界的完备性（Time-Bounded Completeness）：基本 SWIM 的 ping 目标是随机选的，虽然每个故障最终都会被检测到（eventual Strong Completeness），但理论上可能很久都检测不到（极端情况下某个故障节点永远没被任何人抽中）。SWIM 论文给出修正：把 ping 目标选择从”纯随机”改为轮转（round-robin）遍历成员表，每遍历完一轮就随机重排一次列表。于是：
- 每个成员在每一轮遍历中恰好被选中一次；
- 若成员表大小不超过 $N$，同一目标被连续两次选中的间隔至多为 $2N-1$ 个协议周期；
- 因此在 $M_i$ 本地，任何故障最迟在 $2N-1$ 个协议周期内被检测到——这就是确定性时间上界（$O(N)$ 个周期，而非期望常数）。
弱一致（weakly consistent）成员视图：SWIM 传播是尽力而为的感染式，因此不同节点的成员视图在任一时刻可能不同（有人已经知道 $M_j$ 死了，有人还不知道；有人收到 Suspect，有人还没收到）。协议保证的是最终收敛：所有 Suspect/Alive/Confirm 更新都会在 $O(\log N)$ 个协议周期内传遍全组，此后各视图一致。这条弱保证是 SWIM 可扩展性的代价，也是它必须配合上层机制（quorum、lease）一起使用的原因。
工业应用：SWIM 最早用于 Oasis/CoralCDN；随后被 HashiCorp 开源实现，先叫 Serf，后来演化为 Consul（服务发现与健康检查的成员协议）；Uber 也实现了自己的版本 ringpop，用于其基础设施的故障检测。讲义还提到：环状故障检测支撑了 IBM SP2 等集群机，gossip-style 故障检测据称（rumored）支撑了 Amazon EC2/S3 的部分机制。补充说明：Cassandra 的节点成员管理同样基于 gossip（但其故障检测用的是基于到达间隔分布的 Phi accrual failure detector，输出”可疑度”而非布尔值），Redis Cluster 也有自己的 gossip 总线协议——它们都可以看作”随机化探测 + 感染式传播”这一思路的不同工程实现。
7.2.10 成员视图的一致性、脑裂与 quorum 防护
定义与目的：视图（View）指”某一时刻系统认定的成员集合”。视图变更（view change）必须被一致地执行，否则会出现脑裂（split-brain）：两个分区各自认为对方已死，各自选出一个 leader，各自接受写入。
机制图解：脑裂与 quorum 防护
时刻 t0：7 个副本组成一个组，quorum = floor(7/2)+1 = 4
┌──────────────────────────────────────────────────────────────┐
│ {A B C D E F G} 所有节点视图一致，A 是 leader │
└──────────────────────────────────────────────────────────────┘
│
网络分区（交换机故障 / 心跳链路中断）
│
┌───────────────────────┴───────────────────────┐
▼ ▼
┌───────────────────────────┐ ┌───────────────────┐
│ 分区 A：{A B C D} 4/7 │ │ 分区 B：{E F G} │
│ 4 ≥ quorum(4) │ │ 3 < quorum(4) │
│ ⇒ 保留 leader A，继续服务 │ │ ⇒ 拒绝服务/降级/ │
│ （但更新会丢吗？取决于 │ │ 让 E 下台 │
│ 共识协议——Raft 需多数） │ │ （不能选出新 leader）│
└───────────────────────────┘ └───────────────────┘
✗ 若两侧都继续接受写入 ⇒ 脑裂：两个"当前成员集合"互相冲突，
恢复连通后无法合并 ⇒ 数据不一致、更新丢失
✓ quorum 的作用：任何两个 quorum 必有交集（|Q1|+|Q2| > N），
因此至多一个分区能凑齐多数 ⇒ 至多一个 leader ⇒ 无脑裂
一致性要求与代价：
- 弱一致成员视图（SWIM 风格）：分区期间两侧都会把对方标记为
Suspect/Failed，视图会分裂；但协议本身不阻止两侧各自工作。因此 SWIM 类系统必须由上层提供防护：quorum 写、lease、以及”多数派才能提供服务”的策略。Cassandra 正是这种风格（AP 倾向）：成员用 gossip 维护，一致性靠可调 quorum（$R + W > N$）而不是靠成员视图。 - 强一致成员视图（共识风格）：把”成员变更”本身当作一条共识日志来做（Raft 的 joint consensus、ZooKeeper 的 ZAB 配置变更）。代价是 每次成员变更都需要一轮多数派共识，成员规模受限于共识的吞吐；收益是成员配置永不脑裂，且任何时刻的配置都是”全局唯一”的。ZooKeeper 甚至用单独的一套机制防止”僵尸 leader”：epoch/ZXID 单调递增 + quorum 校验。
| 取舍 | 代表系统 | 成员机制 | 一致性倾向 | 能容忍什么 |
|---|---|---|---|---|
| 弱一致成员 + quorum 数据面 | Cassandra、Redis Cluster | Gossip（含 Phi accrual / gossip bus） | AP 倾向 | 分区期间两侧都能读写，靠 quorum 与读修复最终一致 |
| 强一致成员 + 共识数据面 | ZooKeeper、etcd、Consul（Raft 后端） | Raft/ZAB 配置变更 | CP 倾向 | 少数派分区直接不可用，但绝不脑裂 |
为什么这仍然”很难”：把成员视图做强一致，等于在系统里放了一个共识实例；而共识本身需要 $\Diamond S$ 型故障检测器（7.2.4），于是我们又绕回了”检测器不可靠”这一根本困难。这就是为什么”成员管理”看起来只是”维护一个名单”，实际上却是分布式系统里最难的问题之一。 工程上的现实答案通常是一个分层组合：用 SWIM 类协议做快速、可扩展、弱一致的成员与健康视图，用 Raft/Paxos 做慢速、强一致的元数据与配置视图（例如 Consul 用 gossip 维护成员与健康，用 Raft 维护 KV 与配置）——眼睛可以模糊，大脑必须精确。
7.2.11 Grid 计算（Grid Computing，Lecture 6b）
定义与目的：Grid 计算的目标是在动态的、多机构的虚拟组织（Virtual Organization, VO）内做协同的资源共享与问题求解（coordinated resource sharing and problem solving in dynamic, multi-institutional virtual organizations）。它关注的是计算密集型（computation-intensive / HPC = high performance computing）任务：把跨机构、跨地域的超级计算资源、集群与存储聚合成一个”电网”（Grid，取”像电力网一样按需取用”之意）。
“A Cloudy History of Time”（讲义的历史时间线）
1940 ──┬── 1950 ──┬── 1960 ──┬── 1970 ──┬── 1980 ──┬── 1990 ──┬── 2000 ──┬── 2012
│ │ │ │ │ │ │
分时计算公司 & 数据处理行业 第一批大型数据中心 P2P 系统
(Timesharing Companies (ENIAC/ORDVAC/ILLIAC， (90s-00s，数百万用户、
& Data Processing Industry) 大量使用真空管与机械继电器) 每天数 GB)
1975 市场份额：Honeywell 34%、 ├─ 集群 Clusters
IBM 15%、Xerox 10%、CDC 10%、 │ (Berkeley NOW、
DEC 10%、UNIVAC 10% │ 服务器农场 Oceano)
数据处理行业：1968 年 $70M → └─ 超级计算机
1978 年 $3.15B
└──────────── Grids（1980s-2000s）────────────┐
GriPhyN(1970s-80s) │ Open Science Grid 与
Lambda Rail(2000s) │ Globus 及各种标准(1990s-2000s)
│
Clouds and Datacenters（2012）
一个真实的 HPC 应用（讲义例子）：科罗拉多州立大学的 RAMS（Rapid Atmospheric Modeling System）模拟了 1998 年 9 月肆虐 17 天的飓风 Georges：它把网格间距从通常的 10 km 细化到 5 km，跑在 256+ 个处理器上，成功再现了那次带来极端降水的”中尺度对流复合体”。这个例子说明 HPC 的特征：计算密集、可大规模并行、单次运行耗时数小时到数天、输入输出文件达到数 GB。
一个物理学家写的作业流程（讲义例子）：应用被写成作业 DAG（Job 0 → Job 1/Job 2 可并发 → Job 3），每个作业经历四个阶段：
┌────────┐ ┌───────────┐ ┌─────────┐ ┌────────────┐ ┌─────────┐
│ Init │──►│ Stage in │──►│ Execute │──►│ Stage out │──►│ Publish │
└────────┘ └───────────┘ └─────────┘ └────────────┘ └─────────┘
初始化 把数 GB 输入 计算密集， 把数 GB 输出 发布结果文件
文件搬到算力点 大规模并行 文件搬回/转发
两级调度基础设施（2-level Scheduling Infrastructure）：这是 Grid 区别于”一个大集群”的核心架构。
站点 1（Wisconsin） 站点 2（MIT） 站点 3（NCSA）
┌──────────────────┐ ┌──────────────────┐ ┌──────────────────┐
│ 内部调度器 │ │ 内部调度器 │ │ 内部调度器 │
│ HTCondor 协议 │ │ 其他 intra-site │ │ PBS 等 │
│ ·内部资源分配调度 │ │ 协议 │ │ ·监控 │
│ ·监控/文件分发发布│ │ │ │ │
└────────┬─────────┘ └────────┬─────────┘ └────────┬─────────┘
│ │ │
└─────────────┬───────────┴─────────────┬───────────┘
▼ ▼
┌──────────────────────────────────────────┐
│ Globus Protocol（inter-site，跨站点） │
│ ·外部资源分配与调度 │
│ ·Stage in / Stage out（文件进出） │
│ 站点内部结构对 Globus 不可见 │
└──────────────────────────────────────────┘
关键点：Globus 不是调度器。它做的是”外部分配与调度”以及”文件的 stage in/stage out”，并与站点内部的调度器（HTCondor、PBS）通信。这种”层叠”设计正是 Grid 联邦性质的技术体现：每个站点保留自治，跨站点的协同靠标准协议。
Cycle-scavenging（周期窃取）与志愿计算：Condor（现 HTCondor，威斯康星大学麦迪逊分校）属于”cycle-scavenging“系统——跑在大量工作站上，工作站空闲时向本站中央服务器（或 Globus）索取任务，用户一敲键盘/动鼠标就暂停或杀掉任务、请求重新调度；也能跑在专用机器上。SETI@home 与 Folding@Home 属于同一类别。
Globus Toolkit（开源中间件）的组件：
| 组件 | 作用 |
|---|---|
| GridFTP | 广域网大批量数据传输（高性能、可并行、可断点续传） |
| GRAM5（Grid Resource Allocation Manager） | 提交、定位、取消、管理作业——它不是调度器，与站点调度器协作 |
| RLS（Replica Location Service） | 命名服务：把文件/目录名翻译成目标位置（或另一个名字） |
| XIO 等库 | 为所有 Grid IO 功能提供统一 API |
| GSI（Grid Security Infrastructure） | 安全基础设施（见下） |
安全为什么在 Grid 里特别重要：因为 Grid 是联邦（federated）的——没有任何单一实体控制整个基础设施。讲义列出五个要点：
- 单点登录（single sign-on）：一整套作业集只需用户认证一次；
- 映射到本地安全机制：有的站点用 Kerberos，有的直接用 Unix 权限；
- 委托（delegation）：访问资源的凭据可以被子计算继承（例如 Job 0 的凭据传给 Job 1）；
- 社区授权（community authorization）：例如第三方认证；
- 这些在云里也重要，但云的中央控制使其压力小得多；云更关注的是故障、规模与按需性。
Grid vs Cluster vs Cloud：全面对比
| 维度 | Cluster（集群） | Grid（网格） | Cloud（云） |
|---|---|---|---|
| 资源所有权 | 单一组织 | 多组织各自拥有（联邦） | 单一提供商（或多提供商的多云） |
| 控制权 | 集中 | 分散、松耦合、无全局控制者 | 集中（对用户透明） |
| 信任边界 | 组织内 | 跨信任域（需 VO、GSI、委托） | 提供商内部信任 + 用户与提供商的合同 |
| 典型规模 | 几十~几千节点，同构 | 跨站点、异构（超算+集群+存储） | 数万~数十万节点，同构虚拟化资源 |
| 资源分配 | 静态/排队（PBS、Slurm） | 两级调度（站点内 + Globus 跨站点） | 按需、弹性、按用量计费 |
| 使用模式 | 提交批处理作业 | 提交跨站点的作业流（DAG） | API/自助式；虚拟机/容器/函数 |
| 安全模型 | Kerberos / Unix | GSI：单点登录、委托、社区授权 | IAM、租户隔离、密钥管理 |
| 计费 | 不计费（自建） | 通常不计费（科研共享、配额） | 按需付费（on-demand） |
| 故障关注度 | 中 | 中（作业级重试） | 极高（本课程反复强调：故障是常态） |
| 典型代表 | Berkeley NOW、Oceano | Globus/TeraGrid/OSG/EGEE、SETI@home | AWS EC2/S3、Azure、GCP |
Grid 的失败与教训：Grid 在 2000 年代被寄予厚望，最终却被云取代。原因值得记取：
- 标准复杂度过高：Globus/OGF 的规格庞大（GSI、GRAM、GridFTP、RLS…），中间件部署与运维成本极高，”为了跨组织共享而引入了远超收益的复杂度”；
- 缺少统一的资源所有权：联邦意味着没有人对端到端体验负责，跨站点的调度与故障处理难以保证 SLA；
- 管理开销大：证书、委托、站点间信任关系的维护成本随站点数增长；
- 虚拟化与规模经济的降维打击：云用集中所有权 + 虚拟化 + 按需付费，把”跨组织共享”的需求替换成”租用一家公司的资源”，绕开了联邦的全部难点。
但 Grid 的核心思想被继承了下来：虚拟组织（VO）的联邦、跨域认证与委托、作业的阶段化流水线（init/stage-in/execute/stage-out/publish）、两级调度（站点内 + 跨站点），在今天的多云/联邦云（multi-cloud、federated cloud）、Kubernetes 多集群调度（如 Karmada、Volcano）、以及科研数据网格（如 OSG 仍在运行）中都能看到影子。讲义最后的问题依然值得思考：Grids/HPC 是否正在向云收敛？——比较 OpenStack 与 Globus，你会看到两种架构在”资源抽象、调度、认证、数据搬运”上的高度同构。
7.3 算法伪代码与正确性分析
本节四份伪代码对应四种机制：心跳检测器（最基础、误判率最高）、Gossip 检测器（用冗余换取准确性）、SWIM 完整协议（本讲核心，检测 + 怀疑 + 传播三位一体）、自适应超时估计（Jacobsons/Karels 移植，把定长超时变成动态超时）。每份都给出假设、逐步解说、安全性/活性论证与复杂度。
算法 7.3.1：心跳故障检测器（Heartbeating Failure Detector）
假设与系统模型
- 系统模型：异步（无时钟同步、无延迟上界），但检测器依赖本地超时，因此实际上是在一个”部分同步”的假设下工作（超时只在”网络正常时”有意义）。
- 故障模型：crash-stop（进程一旦崩溃即永久停止，不恢复；讲义明确”不考虑 fail-recover”）。
- 通道假设：点对点可靠通道（TCP），消息不丢失但可能任意延迟；或 UDP 且可能丢失（本算法假设 TCP，把”丢失”归约为”延迟过大”）。
- 参数：进程数 $N$，心跳周期 $T_{hb}$，超时阈值 $T_{to}$（通常取 $T_{to} = k \cdot T_{hb}$，$k \ge 2$）。
伪代码
# 每个进程 pi 维护：
# hb[i] : 自己的心跳序号（单调递增）
# last[i][j] : pi 最近一次收到 pj 消息的本地时间
# suspect[i][j]: pi 认为 pj 已故障（布尔）
# T_hb, T_to : 心跳周期与超时阈值
upon init:
hb[i] <- 0
for all j != i: last[i][j] <- now() ; suspect[i][j] <- false
start_timer("heartbeat", T_hb)
start_timer("check", T_hb / 4) # 独立的高频检查定时器
upon timer("heartbeat") fires: # 周期广播自己的存活
hb[i] <- hb[i] + 1
send(HEARTBEAT(i, hb[i])) to all j in group except i
reset_timer("heartbeat", T_hb)
upon timer("check") fires: # 周期扫描超时
for all j != i with suspect[i][j] == false:
if now() - last[i][j] > T_to:
suspect[i][j] <- true # 【判定 pj 已故障】
notify_application(j, FAILED) # 交给上层 / 交给传播组件
hand_to_dissemination(SUSPECT_OR_FAILED(j))
reset_timer("check", T_hb / 4)
upon receiving HEARTBEAT(j, seq) from j:
if seq > hb_known[i][j]: # 只接受更新的序号（防乱序）
hb_known[i][j] <- seq
last[i][j] <- now() # 【刷新存活证据】
suspect[i][j] <- false # 收到消息即撤销怀疑
算法逻辑解说（数值例子走一遍）
设 $N=5$，$T_{hb}=1.0$ s，$T_{to}=3.0$ s（容忍连续 2 次心跳丢失）。在 $t=10.00$ 时 $p_4$ 崩溃，其余进程的本地状态如下：
| 进程 | $last[\cdot][4]$ | $t=10.0$ 起的行为 | 判定时刻 |
|---|---|---|---|
| $p_0$ | 9.98 | $t=12.98$ 检查时 $12.98-9.98=3.00$（未严格大于）→ 下一次检查 $t=13.23$ 时 $3.25>3.0$ | $t \approx 13.23$ |
| $p_1$ | 10.00 | 同上，但 $last$ 稍晚 | $t \approx 13.25$ |
| $p_2$ | 9.75 | $t=12.75$ 与 $t=13.00$ 之间触发 | $t \approx 12.80$ |
| $p_3$ | 9.60 | 最早触发 | $t \approx 12.65$ |
可见：检测时间 = 故障时刻 + 剩余超时窗口，其期望约为 $T_{to}$，但每条进程的判定时刻不同（因为各人最近一次收到心跳的时间不同），这正是”心跳方案难以做到全组同时检测”的原因——而为了”同时检测”，就必须让所有人都直接收到心跳，于是掉进 $O(N^2)$ 的陷阱（见 7.3.3 与 7.5）。
正确性论证
- 安全性（Safety）——”不会把已死进程长期当成活的”：若 $p_j$ 在 $t_f$ 崩溃，则 $t_f$ 之后 $p_j$ 不再发送任何心跳，因此对任意 $p_i$（$i \ne j$），$last[i][j]$ 在 $t_f$ 之后不再更新。又因为通道可靠（TCP），不会有虚假的心跳到来。于是在 $t_f + T_{to} + \delta$（$\delta$ 为检查定时器的粒度）之后，$p_i$ 的检查必然看到 $now() - last[i][j] > T_{to}$，从而置 $suspect[i][j] = true$。结论：强完备性成立（每个故障最终被所有正确进程检测到），且是有限时间的。
- 安全性（Safety）的失败面——准确性无法保证：若 $p_j$ 是正确的（正确的进程），但 $p_j$ 的心跳在窗口 $(t, t+T_{to})$ 内因为拥塞被延迟（TCP 下不是丢失而是延迟），则 $p_i$ 会看到 $now() - last[i][j] > T_{to}$ 而错误判定 $p_j$ 故障。这就是误判（false positive）。异步模型下不存在任何 $T_{to}$ 能排除这种情况（见 7.3.5 的构造性反证）。因此本算法不满足强准确性，也不满足弱准确性，只能给出概率保证 $P_M(T)$。
- 活性（Liveness）——”每个正确进程最终都会被判定为活的”：只要 $p_j$ 正确且网络在其心跳周期内能送达至少一条心跳，$last[i][j]$ 就会被刷新，$suspect[i][j]$ 保持/回到 false。因此在”系统最终同步（Σ 型部分同步）”的假设下，检测器最终不再误判，等价于 $\Diamond P$（最终完美）型检测器。
复杂度
- 消息复杂度：每条进程每周期发送 $N-1$ 条心跳，全网 $N(N-1) \approx O(N^2)$ 条/周期，每条进程负载 $O(N)$。若要求可测 RTT 而加 ack，则再翻一倍。单位时间内每条进程负载 $L = N / T_{hb}$。
- 空间复杂度：每条进程 $O(N)$（$last$ 与 $suspect$ 矩阵各 $N$ 项）。
- 时间（检测）复杂度：期望 $\Theta(T_{to})$，与 $N$ 无关；但最坏情况下单条进程的判定时刻抖动可达 $T_{hb} + T_{to}$。
- 可扩展性瓶颈：$O(N^2)$ 的消息总量使 $N$ 上千时带宽与中断处理开销爆炸（还要乘上 ack）。
算法 7.3.2：Gossip-style 故障检测器（Van Renesse 风格）
假设与系统模型
- 与 7.3.1 相同的异步模型与 crash-stop 故障模型；通道允许丢失（UDP）。
- 参数：gossip 周期 $T_g$；每次 gossip 的随机目标数 $f$（fanout）；失败阈值 $T_{fail}$；清理阈值 $T_{cleanup}$。
- 每个节点维护整张成员表：
(addr, counter, local_ts, state)。
伪代码
# 每个进程 pi 维护：
# counter[i] : 自己的心跳计数（每 Tg 自增）
# known[i][j] : i 已知的 j 的最新计数
# ts[i][j] : i 上次"看到 j 的计数增长"的本地时间
# state[i][j] : ALIVE / FAILED / CLEANED
# Tg, f, T_fail, T_cleanup
upon init:
counter[i] <- 0; for all j: known[i][j] <- 0; ts[i][j] <- now()
start_timer("gossip", Tg); start_timer("expire", Tg)
upon timer("gossip") fires: # ① 周期 gossip 自己的成员表
counter[i] <- counter[i] + 1
known[i][i] <- counter[i]; ts[i][i] <- now()
targets <- random_sample(all_members \ {i}, f)
entries <- [(j, known[i][j]) for j where state[i][j] != CLEANED]
for each t in targets: send(GOSSIP(entries)) to t
reset_timer("gossip", Tg)
upon receiving GOSSIP(entries) from j: # ② 合并：取更新的计数
handle_liveness(j) # 收到消息即证明 j 活着
for each (x, cnt) in entries:
if cnt > known[i][x]:
known[i][x] <- cnt
ts[i][x] <- now() # 【本地时间戳刷新】
state[i][x] <- ALIVE # 可能把 FAILED 复活
cancelled_cleanup <- true
upon timer("expire") fires: # ③ 过期判定与清理
for all x != i with state[i][x] != CLEANED:
age <- now() - ts[i][x]
if age > T_fail and state[i][x] == ALIVE:
state[i][x] <- FAILED # 【判定故障，先不删除】
notify_application(x, FAILED)
if age > T_fail + T_cleanup:
state[i][x] <- CLEANED # 【再等 T_cleanup 才真正删除】
reset_timer("expire", Tg)
算法逻辑解说（数值例子走一遍）
沿用 7.2.8 的讲义例子：节点 2 在本地时间 70 的表如上，$T_{fail}=12$。在 $t=80$ 的 expire 定时器触发时，节点 2 算出 age(4)=15>12，于是把节点 4 置为 FAILED 并通知上层。注意此时并不删除表项：节点 2 会把 (4, 10111) 这条 FAILED 信息继续 gossip 出去（对，失败信息也要传播）。直到 $t = 80 + T_{cleanup}$ 之后，表项才被置为 CLEANED，不再参与 gossip。
若没有 $T_{cleanup}$：假设节点 4 其实没死，只是它的心跳被延迟；节点 2 在 $t=80$ 删除表项后，$t=81$ 又收到一条来自节点 3 的、携带 (4, 10112) 的 gossip，于是表项被重新插入——节点 4 在节点 2 的视图里”死而复生”，而且这类抖动会随着延迟变长而反复发生。$T_{cleanup}$ 保证”删除”发生在所有携带旧计数的在途消息都已过期之后。
正确性论证
- 安全性（Safety）：设 $p_j$ 崩溃于 $t_f$。$t_f$ 之后 $counter[j]$ 不再增长，任何节点 $i$ 都不会再收到 $cnt > known[i][j]$ 的条目，因此 $ts[i][j]$ 在 $t_f$ 之后不再刷新（最坏情况下，一条在 $t_f$ 前不久生成的 gossip 可能在 $t_f$ 之后到达并刷新一次）。于是在 $t_f + T_{fail} + \delta$（$\delta$ 为一条 gossip 的最大在途时间）之后，$p_i$ 必然把 $j$ 置为
FAILED。强完备性成立（因为每个节点都独立判断，且每个节点都与其他节点有 gossip 联系）。 - 准确性的改善：$known[i][j]$ 的更新来自多条独立路径（$p_j$ 自己 gossip，以及任何知道 $j$ 的节点转发）。要让一个正确节点 $j$ 在 $i$ 眼中”过期”，必须连续 $T_{fail}$ 时间内所有能到达 $i$ 的、携带 $j$ 新计数的 gossip 全部失败——这是一个”多路径同时失败”的事件，其概率随 fanout $f$ 与每轮参与转发的节点数指数下降。这就是”gossip 提高准确性”的定量解释。
- 活性（Liveness）：只要 $p_j$ 正确，$counter[j]$ 每 $T_g$ 增长一次，且该更新以极高概率在一段时间内到达所有节点（感染式传播），因此 $ts[i][j]$ 会被周期性刷新，$state[i][j]$ 最终回到
ALIVE。最终准确性成立。 - 收敛性（弱一致视图）：所有
ALIVE/FAILED更新都遵循”更高计数覆盖更低计数”的单调规则，因此状态不会自相矛盾地来回翻转（除非有新信息），且感染式传播保证每个更新在 $O(\log N)$ 轮内传遍全组 → 各节点视图最终收敛。
复杂度
- 消息复杂度：每周期每节点发 $f$ 条 gossip，全网 $N f = O(N)$ 条/周期（比全互探心跳的 $O(N^2)$ 好一个量级）；但每条消息携带 $O(N)$ 个条目，因此字节复杂度仍是 $O(N^2)$/周期——这正是 gossip 心跳被带宽卡住的地方。讲义给出的每条进程负载是 $L = N \log N / T$（为实现检测时间 $T$ 所必需）。
- 时间（检测）复杂度：检测时间 $\approx T_{fail}$；传播时间 $O(\log N)$ 轮。
- 空间复杂度：$O(N)$ 每条进程（整张表 + 时间戳）。
- 参数敏感性：$T_{fail}$ 需大于”连续 $k$ 轮 gossip 都未能带来该成员更新”的时间，通常取 $T_{fail} \ge 3 T_g$；$T_g$ 与小 fanout 会增加误判（见 7.4.2 的实测：$T_{fail}=0.25$ s 时出现 2~4 次误判，$T_{fail}=0.60$ s 时误判降到 0 但检测变慢）。
算法 7.3.3：SWIM 完整协议（Failure Detection + Suspicion + Dissemination）
假设与系统模型
- 系统模型：异步 + 部分同步假设（协议周期与超时用于判定，因此隐含”网络正常时延迟有界”）。
- 故障模型：crash-stop（SWIM 论文明确只考虑进程崩溃；slow 进程通过怀疑机制处理）。
- 通道假设：点对点 UDP，可能丢失、延迟、乱序；不需要 FIFO，也不需要可靠传输。
- 规模参数：$N$ 个进程；协议周期 $T^{\prime}$；直接 ping 超时 $T_{ack}$（$T^{\prime} \ge 3 \times \text{RTT}$ 估计）；间接探测代理数 $K$；怀疑超时 $T_{susp}$；每条消息最多捎带 $P$ 条成员变更。
伪代码（完整状态机）
# ============ 每个进程 Mi 的持久状态 ============
# inc[i] : Mi 自己的 incarnation number（只能由 Mi 自增）
# member[j] = (state, inc_j) : state ∈ {ALIVE, SUSPECT, DEAD}；inc_j 是 j 的化身号
# susp_timer[j] : j 的怀疑超时截止时刻
# buf : 待传播的成员变更缓冲区 [(member, state, inc, count)]
# order / pos : 轮转探测的成员顺序（遍历一轮后随机重排）
# pending_seq, acked : 本周期的探测序号与"已收到 ack"标志
# proxy[seq] : 我作为代理时记录 (请求者, 被探测者)
upon init(Mi, membership_list):
inc[i] <- 0
for all j: member[j] <- (ALIVE, 0); susp_timer[j] <- null
order <- random_permutation(members); pos <- 0
start_timer("protocol_period", T')
# ============ 主循环：每 T' 执行一次协议周期 ============
upon timer("protocol_period") fires:
check_suspicion_timeouts() # (A) 先处理到期的怀疑
Mj <- next_target() # (B) 轮转 + 遍历后随机重排
if Mj == null: return
pending_seq <- (i, next_seq()); acked <- false
send PING(seq=pending_seq, target=Mj, piggyback=pick_buffer()) to Mj # (C) 直接探测
wait_until(now() + T_ack) processing_inbox() # (D) 等 T_ack
if not acked: # (E) 超时 ⇒ 间接探测
for each Mk in random_sample(members \ {Mi, Mj}, K):
send PING_REQ(seq=pending_seq, target=Mj, piggyback=pick_buffer()) to Mk
wait_until(period_end) processing_inbox() # (F) 等到周期结束
check_suspicion_timeouts()
if not acked: # (G) 周期结束仍无 ack
local_mark_suspect(Mj) # 只标记 SUSPECT，不判死
# ============ 收到消息 ============
upon receiving MSG from Mj (any type):
for each (x, st, inc_x) in MSG.piggyback: # (H) 先合并捎带的成员变更
merge(x, st, inc_x)
case MSG.type of
PING: # (I) 我被人探测，回 ack
send ACK(seq=MSG.seq, target=MSG.target,
piggyback=pick_buffer()) to Mj
PING_REQ: # (J) 我当代理：代为探测并回传
proxy[MSG.seq] <- (Mj, MSG.target)
send PING(seq=MSG.seq, target=MSG.target,
piggyback=pick_buffer()) to MSG.target
ACK:
if MSG.seq == pending_seq: # (K) 我本周期被确认了
acked <- true
local_mark_alive(MSG.target) # 撤销对 target 的怀疑
if proxy[MSG.seq] == (·, Mj): # (L) 我是代理，转发给请求者
requester <- proxy.pop(MSG.seq).requester
send ACK(seq=MSG.seq, target=Mj,
piggyback=pick_buffer()) to requester
# ============ 成员表操作 ============
procedure local_mark_suspect(Mj): # 本地判定：
if member[Mj].state == ALIVE: # 从 ALIVE 升级为 SUSPECT
member[Mj] <- (SUSPECT, member[Mj].inc)
susp_timer[Mj] <- now() + T_susp
buffer_add(Mj, SUSPECT, member[Mj].inc) # 交给传播组件（感染式）
procedure local_mark_alive(Mj): # 收到 ack ⇒ 证明 Mj 活着
if member[Mj].state != ALIVE:
member[Mj] <- (ALIVE, member[Mj].inc)
susp_timer[Mj] <- null
buffer_add(Mj, ALIVE, member[Mj].inc)
procedure check_suspicion_timeouts():
for each Mj with member[Mj].state == SUSPECT:
if now() > susp_timer[Mj]: # 怀疑超时 ⇒ Confirm
member[Mj] <- (DEAD, member[Mj].inc)
buffer_add(Mj, DEAD, member[Mj].inc)
notify_application(Mj, FAILED)
remove Mj from order # 不再作为 ping 目标
procedure merge(x, st, inc_x): # 优先级规则
if x == Mi: # 关于我自己的消息
if st == SUSPECT and inc_x >= inc[i]:
inc[i] <- inc_x + 1 # ★ refute：自增化身号
buffer_add(Mi, ALIVE, inc[i]) # 广播 Alive(inc+1) 自证清白
return
local <- member[x]
if st == DEAD:
if inc_x >= local.inc: # Confirm 覆盖一切
member[x] <- (DEAD, inc_x); remove x from order
buffer_add(x, DEAD, inc_x)
else if inc_x > local.inc: # 更高的 inc 覆盖更低的 inc
member[x] <- (st, inc_x)
susp_timer[x] <- (now() + T_susp) if st == SUSPECT else null
buffer_add(x, st, inc_x)
else if inc_x == local.inc and st == SUSPECT and local.state == ALIVE:
member[x] <- (SUSPECT, inc_x) # 同 inc：Suspect > Alive
susp_timer[x] <- now() + T_susp
buffer_add(x, SUSPECT, inc_x)
// 其余情况忽略（同 inc 的 Alive 不能覆盖 Suspect；低 inc 一律忽略）
# ============ 感染式传播（零额外消息）============
procedure pick_buffer(): # 每条消息捎带最多 P 条
items <- 缓冲区中 count（已捎带次数）最小的 P 条 # 优先传播"年轻"的更新
for each it in items: it.count <- it.count + 1
return items
procedure buffer_add(member, st, inc): # 本地发生变更 ⇒ 入缓冲区
buf[member] <- (st, inc, count=0)
# 缓冲区元素在被捎带 O(log N) 次后（或经过 O(log N) 个周期后）被垃圾回收：
# 此时它已以极高概率传遍全组 —— 这正是"弱一致"的边界。
算法逻辑解说（数值例子走一遍）
设 $N=6$，$T^{\prime}=0.10$ s，$T_{ack}=0.045$ s，$K=2$，$T_{susp}=0.8$ s。三个典型场景（与 7.4.3 的代码实验完全对应）：
- $M_5$ 在 $t=1.2$ s 崩溃。其他节点按轮转顺序，最多经过 5 个周期（$0.5$ s）就会轮到 ping $M_5$；直接 ping 超时 → 发 2 个
PING_REQ→ 代理也拿不到 ack（目标已死）→ 周期结束 → 本地标记Suspect(5, inc=0)并广播。所有节点在 $t \approx 1.5$ s 前后都标记了 SUSPECT。$0.8$ s 后（$t \approx 2.3$ s）怀疑超时 →Confirm(5, 0)→ 各节点视图把它删除。实测检测延迟约 1.1 s（≈ 11 个协议周期），与”期望 $\frac{e}{e-1} \approx 1.58$ 个周期 + 怀疑超时”的量级一致。 - $M_0$ 到 $M_2$ 的有向路径拥塞（0.15 s > 周期）。$M_0$ ping $M_2$ 超时（$T_{ack}$ 到期）→ 但 $K=2$ 个代理走的是别的路径，
ping-req的往返只需 $4 \times 0.004$ s $= 0.016$ s，在同一个周期内就拿到了间接 ack → $M_0$ 什么都不标记，$M_2$ 从未被怀疑。对照实验：把 $K$ 设为 0（关闭间接探测），$M_0$ 会立刻把 $M_2$ 标为SUSPECT并广播出去（实测其 incarnation 被推到 3）——只是靠怀疑机制与 refute 才没有被 Confirm 成DEAD。 - $M_3$ 应答变慢（它的 ack 延迟 0.12 s > 周期）。每个节点 ping $M_3$ 都超时，于是 $M_3$ 被所有节点标记
Suspect并广播；$M_3$ 通过捎带收到Suspect(3, inc)→inc[3]自增 → 广播Alive(3, inc+1)→ 全组撤销怀疑；下一个周期又被怀疑，于是 inc 再次自增……实测 $M_3$ 的 incarnation 从 0 一路涨到 7，但它从未被确认为DEAD，也从未离开过组。
正确性论证
- 安全性 S1（完备性 / 不永久漏判）：由轮转探测（
order+ 遍历后重排），每个成员在每一轮遍历中恰好被选为 ping 目标一次；若成员表大小不超过 $N$，则同一目标两次被选中的间隔 $\le 2N-1$ 个协议周期。因此对任意崩溃的 $M_j$ 与任意正确进程 $M_i$，$M_i$ 会在 $O(N)$ 个周期内 ping 到 $M_j$，且由于 $M_j$ 已崩溃不会回 ack，也不会通过任何代理回 ack，$M_i$ 必然把 $M_j$ 标记为SUSPECT，再经 $T_{susp}$ 后Confirm为DEAD。强完备性 + 时间有界（Time-Bounded Completeness）成立。 - 安全性 S2（不产生”不可撤销的错误”）：误判只可能把状态推到
SUSPECT。而SUSPECT是可撤销的：只要 $M_j$ 还有生机，要么某个节点成功 ping 到它（local_mark_alive），要么它自己收到Suspect并自增 inc 反驳（merge的 refute 分支）。唯一不可撤销的只有DEAD，而DEAD需要 $T_{susp}$ 的”冷静期”。这就是”把永久误判降级为暂时误判”的形式化表述。 - 安全性 S3（优先级规则不会自相矛盾）：三条规则（更高 inc 优先；同 inc 下
Suspect > Alive；Confirm覆盖一切）构成一个偏序，并且每条规则都使”已生效的状态”单调地向更强的方向演进（Alive → Suspect → DEAD），不存在”两个节点收到同样两条消息却得出相反结论”的情形（因为规则只依赖 (state, inc) 对，不依赖消息来源）。因此合并操作是可交换、可结合、幂等的（类似 CRDT 的单调 join），这保证了收敛性。 - 活性 L1（refute 一定有效）：被怀疑者 $M_j$ 只要仍然正确，就会继续执行协议周期并收到别人捎带（piggyback）在 ping/ack 上的
Suspect(j, inc)消息。由于 $inc_j$ 只能由 $M_j$ 自增，且新消息的 inc 严格更大，它广播的Alive(j, inc_j+1)会覆盖所有旧的Suspect(j, inc_j)。因此”被误判者最终会被全组重新接受”。 - 活性 L2（视图最终收敛）：每个成员变更都被写入缓冲区，并以”优先传播捎带次数最少的条目”的策略在 ping/req/ack 上捎带，感染式传播保证任一条更新在 $O(\log N)$ 个协议周期内以高概率到达全组；到达后按 S3 的单调规则合并，因此所有正确节点的视图最终一致（弱一致成员视图的”最终”部分）。
- 活性 L3（负载不因故障而发散）：缓冲区条目在被捎带 $O(\log N)$ 次后被回收，因此同一变更不会被无限重复传播；
DEAD成员被移出探测目标，因此探测负载不会因为死节点而累积。
复杂度
- 消息复杂度：每个协议周期，每条进程发送 1 条
PING+ 至多 $K$ 条PING_REQ+ 若干ACK（每收到一个 ping 回一个）。每条进程 $O(K+1) = O(1)$ 条/周期，与组规模 $N$ 无关。全网 $O(N)$ 条/周期。“零额外消息”是感染式传播的核心贡献：成员变更完全靠捎带，不产生任何额外的 multicast/point-to-point 消息。 - 消息大小：每条
ping/ping-req/ack至多捎带 $P$ 条成员变更，大小有界且与 $N$ 无关（SWIM 论文实测：基础版 15 B，带感染传播版 135 B）。 - 时间（检测）复杂度：期望首次检测时间 $= \frac{e}{e-1} \approx 1.58$ 个协议周期，是常数（与 $N$ 无关），因为”某个随机成员在本周期被某个进程抽中”的概率为 $1 - (1-\frac{1}{N})^N \approx 1 - 1/e$；最坏（时间有界）检测时间 $= 2N-1$ 个协议周期。
- 传播复杂度：成员变更的传播延迟 $O(\log N)$ 个协议周期（流行病传播的标准结论）。缓冲区空间 $O(\log N)$ 条/进程（回收后不再占用）。
- 误判率：$P_M(T)$ 随 $K$ 指数下降（$K$ 越多，需要”直接路径与 $K$ 条间接路径同时失效”才会误判），且随”每条进程负载被放大”而指数下降——这是 SWIM 论文强调的可调旋钮：用一点带宽换取误判率的指数改善。
- 实测（SWIM 论文，PC 集群，协议周期 2 s，$K=3$，每条消息最多捎带 6 条更新）：最多 55 个成员时，每条进程每周期平均消息开销约 2.0 条；$N=28$ 时”发送消息数 > 5 条/周期”的概率小于 1%；首次检测时间与组规模无关，符合 $e/(e-1)$ 的解析估计；传播延迟中位数始终只有几个协议周期；在 10% 人工丢包下做 17 个进程依次加入的实验，
SWIM:Basic与SWIM+Inf.的组规模分别塌缩到 2 与 4，而SWIM+Inf.+Susp.稳定在 12 个成员——怀疑机制把误判率降低了一个数量级以上。
算法 7.3.4：自适应超时估计（Jacobson/Karels）
假设与系统模型
- 检测器采用 ping-ack（能测 RTT）或心跳到达间隔（能测确认间隔）作为样本；
- 网络延迟的分布随时间变化（拥塞、路由切换、跨机架流量），因此固定超时必然在某段时间里过紧或过松；
- 样本必须独立同分布地反映当前网络状况，且估计器必须对离群值稳健。
公式（TCP 重传超时的经典推导）
设第 $k$ 次确认的样本为 $\text{SampleRTT}_k$（一次 ping 到对应 ack 的往返时间，或相邻两次确认的间隔）：
\[\text{EstimatedRTT} \leftarrow (1-\alpha)\cdot \text{EstimatedRTT} + \alpha \cdot \text{SampleRTT}, \qquad \alpha = \frac{1}{8}\] \[\text{Deviation} \leftarrow (1-\beta)\cdot \text{Deviation} + \beta \cdot \left\vert \text{SampleRTT} - \text{EstimatedRTT} \right\vert , \qquad \beta = \frac{1}{4}\] \[\boxed{\ \text{Timeout} = \text{EstimatedRTT} + 4 \cdot \text{Deviation}\ }\]伪代码
# 每条进程对每个 peer j 维护: est[j] (EstimatedRTT), dev[j] (Deviation), prev_ack[j]
const alpha <- 1/8 ; beta <- 1/4 ; K <- 4 ; T_min <- 3 * T_probe # 安全下限
upon init:
for all j: est[j] <- T_probe + RTT_init ; dev[j] <- RTT_init / 4
prev_ack[j] <- null ; last_seen[j] <- now()
upon timer("probe", T_probe) fires: # 周期探测所有 peer（或随机子集）
for all j != i: send PING(seq, t_send=now()) to j
upon receiving ACK(j, t_send) from j:
last_seen[j] <- now() # ① 存活证据刷新
sample <- now() - t_send # ② 取样本（RTT）
est[j] <- (1 - alpha) * est[j] + alpha * sample # ③ 平滑 RTT
dev[j] <- (1 - beta) * dev[j] + beta * abs(sample - est[j]) # ④ 平滑偏差
timeout[j] <- max(T_min, est[j] + K * dev[j]) # ⑤ 重算超时
upon receiving any message from j:
last_seen[j] <- now() # 任何消息都是存活证据
upon timer("check") fires: # ⑥ 用"当前"超时判定
for all j != i:
if now() - last_seen[j] > timeout[j]:
declare j FAILED
算法逻辑解说（数值例子走一遍）
设初始 $est = 0.060$ s，$dev = 0.015$ s，$T_{probe}=0.05$ s，$T_{min}=0.15$ s，$\alpha=1/8$，$\beta=1/4$，$K=4$。网络稳定时 RTT $\approx 0.008$ s：
| 观测 | SampleRTT | est 更新后 | dev 更新后 | Timeout = max(0.15, est+4dev) |
|---|---|---|---|---|
| 初始 | — | 0.060 | 0.015 | 0.150（下限生效） |
| 第 1 次 | 0.008 | 0.0535 | 0.0179 | 0.150 |
| 第 5 次 | 0.008 | 0.028 | 0.014 | 0.150 |
| 第 20 次 | 0.008 | 0.0106 | 0.0048 | 0.150（收敛到下限） |
| 突然拥塞 | 0.400 | 0.0593 | 0.1037 | 0.474（立即自适应该重尾） |
| 拥塞缓解 | 0.008 | 0.0531 | 0.0918 | 0.420（缓慢回落） |
| 持续正常 ×50 | 0.008 | 0.010 | 0.005 | 0.150 |
这张表揭示了自适应机制的全部性格：
- 稳态下由下限 $T_{min}=3T_{probe}$ 主导——因为”确认信号最多每 $T_{probe}$ 刷新一次”，超时必须至少容忍 2 次连续丢失探测，这是一个与 RTT 无关的、由探测节奏决定的下限；
- 一个尾部样本就能把 Timeout 抬起来（0.15 → 0.474），从而避免后续同一量级的尾部延迟造成误判；
- 回落到下限是缓慢的（指数平滑的固有性质）——这带来”误判少但检测慢”的保守性，工程上通常再叠加一个”连续多次无响应就缩短超时”的快速下降机制（TCP 的 RTO 退避与恢复策略也是类似思路）。
为什么是 $4 \times \text{Deviation}$？
- 若样本近似正态，$\text{Deviation} \approx 0.8\sigma$，取 $4\times$ 即覆盖约 99.9% 的正常样本（”正常波动引发误判”的概率约千分之一）；更关键的是平均绝对偏差比重尾分布下的方差稳健得多，这正是”分布未知、非高斯”的真实网络所需要的 safety margin；
- 这是 TCP 重传超时用了三十多年的经验参数：乘子 1 太小（频繁误判），8 太大（检测太慢）。
正确性论证
- 安全性（安全性 ⇒ 误判率上界）：设某时刻真实确认间隔的上界为 $U$，且估计器满足 $est + 4dev \ge U$，则该时刻不产生误判。由于 $est$ 与 $dev$ 都随样本单调更新，只要网络在 $[t-T_{adapt}, t]$ 内的行为与当前样本分布一致，Timeout 就会覆盖该分布的绝大部分尾部。反之，若网络状况在一个探测周期内突变为完全新的分布（例如链路切换导致 RTT 跳变 10 倍），则第一个尾部样本仍可能造成一次误判——这是自适应估计的固有盲区（详见 7.4.2 的实测：在中途切换延迟的场景里，固定与自适应方案的误判数几乎相同）。这条结论非常重要：自适应超时不是万灵药，它只能对付”渐变/持续性的方差变化”，无法预测”瞬时的断崖式变化”。
- 活性（收敛性 / 稳定性）：更新规则是一个带遗忘因子的线性滤波，$\alpha,\beta \in (0,1)$ 保证 $est,dev$ 的更新算子谱半径 $<1$，因此估计是 BIBO 稳定的：有界的样本序列产生有界的估计序列，且当样本分布平稳时 $est \to E[\text{Sample}]$、$dev \to E[\vert \text{Sample}-E[\text{Sample}]\vert ]$（指数遗忘的弱收敛）。此外 $\text{Timeout} \ge T_{min} > 0$ 保证不会因为估计收敛到 0 而产生病态判定。
- 单调安全性：由于所有节点只依赖自己的样本，不需要节点间的时间同步（只用本地时钟测差），因此自适应超时与两进程时钟偏移无关。
复杂度
- 时间：每次确认 $O(1)$ 更新；收敛到新分布需要 $O(1/\alpha) = 8$ 个样本量级（约 $8 T_{probe}$）。
- 空间：每条 peer 两个浮点数 $O(N)$ 每条进程。
- 消息：与所用的探测方式相同（不增加额外消息，只是把 ack 用于测量）。
7.3.5 不可能性：为什么任何检测器都无法同时满足强完备性与强准确性
前面每个算法的”安全性”论证里都出现了同一个漏洞：误判无法被消除。本节把这个漏洞形式化为一条定理，并与 FLP 不可能性（Lecture 17）对接。
定理（Chandra-Toueg 归约的两条腿）
- 在异步系统（延迟无上界）中，不存在同时满足强完备性与强准确性的故障检测器（即不存在 Perfect P）。
- 若存在既强完备又强准确的检测器，则可以解异步共识——而异步共识在有一个进程可能崩溃时不可解（FLP 定理）。因此第 1 条也可由 FLP 反推得到。
构造性反证（”消息恰好延迟到超时之后”的执行）
设 $D$ 是任意一个声称”既强完备又强准确”的检测器，其判定规则在实现上只能是”在某个有限时间 $T$ 内没有收到来自 $p_j$ 的消息就怀疑 $p_j$”（任何实现都必须有限时间内做出判定，否则它连弱完备性都不满足）。构造如下两个执行：
- 执行 $E_1$：$p_j$ 在时刻 $t_0$ 崩溃。$p_i$ 在 $t_0 + T$ 时未收到任何消息，于是怀疑 $p_j$。
- 执行 $E_2$：$p_j$ 一直正确。$p_i$ 在 $t_0$ 发送 ping，而网络把 ping 与 $p_j$ 的 ack 都延迟了 $2T$ 才送达（异步模型允许任意大延迟，所以这是合法执行）。
在 $t_0 + T$ 这一时刻，$p_i$ 的本地状态、收到的消息集合、可观测的一切完全相同（两个执行在 $p_i$ 视角下不可区分）。$D$ 是确定性算法，因此它在两个执行中做出相同的判定：
- 若 $D$ 判定”$p_j$ 已故障”：则 $E_2$ 中出现误判，强准确性被违反；
- 若 $D$ 判定”$p_j$ 活着”：则 $E_1$ 中 $p_i$ 在 $T$ 时刻不怀疑一个已崩溃的进程；而由于 $p_j$ 之后再也不会发消息，$D$ 只能等待——但等待多久都无法保证：异步模型允许”消息仍在途中”，检测器永远无法排除”再等一会儿就到了”这一可能性。因此若 $D$ 声称”不会误判”，它就必须永远等待，强完备性被违反（判定永远不会发生）。
两种情形都不成立 ⇒ 定理成立。 并且这个反证还解释了为什么现实中的检测器必须在两者之间取舍，而不能”更聪明地”两者兼得——信息不足，不是算法不够好。
SWIM 如何在不可能性之下工作：SWIM 的做法不是”打破定理”，而是放弃强准确性，并把违反准确性的后果降到可接受：
- 降级误判：用
SUSPECT中间态取代”立刻判死”，把永久误判降级为暂时误判（自 7.3.3 的安全性 S2）； - 降低误判概率：用 $K$ 条间接探测路径，把”单点拥塞导致误判”的概率降到 $P_M(T)$ 并使其随 $K$ 指数下降；
- 提高检测概率：用轮转探测给出 $2N-1$ 周期的确定性上界，保证强完备性；
- 把正确性责任上移：把”因为误判而暂时少了一个成员”的后果交给上层（quorum 无法达成时宁可不可用，见 7.2.10）来吸收。
本讲最重要的一条设计原则：故障检测器是分布式系统的眼睛，但它天生不可靠。任何基于”知道谁死了”的容错机制，其正确性论证都必须显式地写出”当检测器出错时，系统仍然安全”的论证。 Raft 的做法是”任何疑似的 leader 失效都只会触发一次新的选举，而选举的结果必须得到多数派认可”；Paxos 的做法是”任何 proposer 的提议都必须赢得多数派，而多数派天然排除了被误判的少数”；Cassandra 的做法是”成员视图的短暂不一致由读写 quorum 与读修复兜底”。没有哪个严肃系统把正确性直接建立在检测器的判定之上。
7.4 代码示例与分布式实现
本节三个程序层层递进：先建一个延迟/丢包/崩溃都可配置的模拟网络（7.4.1），再用它做三种故障检测器的对照实验（7.4.2），最后用真实线程 + 消息队列实现完整的 SWIM（7.4.3）。全部只用 Python 标准库、固定随机种子、可直接 python3 运行。
7.4.1 可配置延迟、丢包与崩溃的模拟网络（Network Simulator）
"""7.4.1 可配置延迟 / 丢包 / 崩溃的离散事件网络模拟器（只用标准库）"""
import heapq
import random
from collections import defaultdict
class Network:
"""离散事件网络：固定 / 高斯 / 重尾 Pareto 延迟，可设丢包率，可让节点崩溃。"""
def __init__(self, dist="fixed", param=0.02, sigma=0.0, loss=0.0, seed=0):
self.dist, self.param, self.sigma = dist, param, sigma
self.loss = loss
self.rng = random.Random(seed)
self.events = [] # 最小堆: (投递时刻, 序号, 目的, 源, 消息)
self.seq = 0
self.now = 0.0
self.crashed = set() # 已崩溃节点
self.inbox = defaultdict(list) # 每个节点收到的消息
self.n_sent = self.n_dropped = self.n_delivered = 0
self.delays = [] # 成功投递的端到端延迟样本
def sample_delay(self):
if self.dist == "fixed":
return self.param
if self.dist == "gauss": # 正态：抖动有限但连续
return max(0.0, self.rng.gauss(self.param, self.sigma))
if self.dist == "pareto": # 重尾：偶发超长延迟（排队/拥塞）
return self.param * self.rng.paretovariate(1.5)
raise ValueError("unknown dist")
def crash(self, node):
self.crashed.add(node)
def send(self, t, src, dst, msg):
self.n_sent += 1
if src in self.crashed or dst in self.crashed:
self.n_dropped += 1
return
if self.rng.random() < self.loss:
self.n_dropped += 1
return
self.seq += 1
heapq.heappush(self.events, (t + self.sample_delay(), self.seq, dst, src, msg))
def step(self):
"""投递堆顶事件；返回 False 表示事件队列已空。"""
if not self.events:
return False
t, _, dst, src, msg = heapq.heappop(self.events)
self.now = max(self.now, t)
self.n_delivered += 1
self.delays.append(t - msg.get("t_send", t)) # 端到端延迟
self.inbox[dst].append((src, msg))
return True
def take(self, node):
return self.inbox.pop(node, [])
def pct(self, p):
s = sorted(self.delays)
return s[min(len(s) - 1, int(p * len(s)))] if s else float("nan")
if __name__ == "__main__":
random.seed(0)
print("=== 三种延迟分布下的端到端行为（200 条消息，丢包率 5%）===")
print(f"{'dist':8s} {'sent':>5s} {'drop':>5s} {'deliv':>6s} "
f"{'p50':>8s} {'p99':>8s} {'max':>8s}")
for dist, kw in [("fixed", dict(param=0.02)),
("gauss", dict(param=0.02, sigma=0.01)),
("pareto", dict(param=0.01))]:
net = Network(dist=dist, loss=0.05, seed=42, **kw)
for i in range(200):
net.send(0.0, 0, 1, {"type": "ping", "seq": i, "t_send": 0.0})
while net.step():
pass
assert len(net.take(1)) == net.n_delivered
print(f"{dist:8s} {net.n_sent:5d} {net.n_dropped:5d} {net.n_delivered:6d} "
f"{net.pct(0.50):8.4f} {net.pct(0.99):8.4f} {max(net.delays):8.4f}")
print("\n=== 崩溃注入：所有发往崩溃节点的消息被丢弃 ===")
net = Network(dist="fixed", param=0.02, seed=1)
net.crash(2)
for _ in range(5):
net.send(0.0, 0, 2, {"type": "ping", "t_send": 0.0}) # 5 条发往崩溃节点
net.send(0.0, 0, 1, {"type": "ping", "t_send": 0.0}) # 5 条正常
while net.step():
pass
print(f"node1 收到 {len(net.take(1))} 条，node2 收到 {len(net.take(2))} 条，"
f"丢弃 {net.n_dropped} 条")
assert len(net.take(2)) == 0 and net.n_dropped == 5
print("断言通过：崩溃节点不再接收任何消息。")
运行结果（节选）
=== 三种延迟分布下的端到端行为（200 条消息，丢包率 5%）===
dist sent drop deliv p50 p99 max
fixed 200 10 190 0.0200 0.0200 0.0200
gauss 200 6 194 0.0200 0.0502 0.0561
pareto 200 7 193 0.0154 0.7481 1.2477
=== 崩溃注入：所有发往崩溃节点的消息被丢弃 ===
node1 收到 5 条，node2 收到 0 条，丢弃 5 条
断言通过：崩溃节点不再接收任何消息。
【代码做什么？】
Network用离散事件模拟（discrete-event simulation）建模网络：所有消息进入一个最小堆events，堆顶是”最早到达的那条消息”，step()弹出它并投递到目标节点的inbox；sample_delay()支持三种延迟分布：fixed（固定，理想局域网）、gauss（正态，抖动有限）、pareto（重尾，模拟排队/拥塞下的长尾延迟——注意其 p99 是 p50 的 48 倍，而高斯只有 2.5 倍）；loss参数模拟随机丢包；crash(node)把节点加入crashed集合，此后所有以它为源或目的的消息都被丢弃（模拟进程崩溃后既不发也不收）；- 主程序先对三种分布各发 200 条消息，统计投递率与延迟分位数；再注入一次崩溃，用
assert验证”崩溃节点不再接收任何消息、发给它的消息全部被丢弃”。
【分布式机制透视】
- 离散事件模拟 vs 真实 socket：真实分布式系统里”消息在网络中飞行”是物理事实；在这里它被显式地表示为”堆里一个带投递时刻的记录”。这个抽象是等价的，而且可复现（固定种子后每次运行结果完全相同），这正是研究型论文里做故障检测器对照实验的标准做法。
- 重尾分布为什么重要：真实数据中心网络的延迟分布不是高斯的——交换机队列溢出、TCP 重传、虚拟机调度抖动都会产生”绝大多数很快、偶尔极慢”的重尾。本模拟器专门提供 Pareto 分布，就是为了在 7.4.2 里逼出”固定超时方案的误判”。
crashed集合的语义：注意它同时拦截入边和出边。真实系统中进程崩溃后确实既不发也不收；如果不拦截”发给崩溃节点的消息”，模拟器会错误地让已死进程还能收到 ping，从而让检测器”意外地”正确。
【与理论的对应】
- 代码里的
send对应 7.3 伪代码中的send(m) to Pj；step()对应”消息在不可靠通道上传输”这一系统模型假设； sample_delay()实现的正是”延迟无上界“这一异步模型假设的工程化近似：Pareto 分布的尾部可以任意长，因此任何有限超时 $T$ 都存在被超过的概率——这就是 7.3.5 里那个”消息恰好延迟到超时之后”的执行在代码层面的化身；loss参数对应 Chandra-Toueg 语境里的”lossy networks”。
7.4.2 三种故障检测器在同一环境下的对照实验
"""7.4.2 三种故障检测器在同一模拟网络下的对比实验（只用标准库）"""
import heapq
import random
from collections import defaultdict
# ---------------------------------------------------------------- 模拟网络
class Network:
def __init__(self, dist="fixed", param=0.01, sigma=0.0, loss=0.0, seed=0):
self.dist, self.param, self.sigma, self.loss = dist, param, sigma, loss
self.rng = random.Random(seed)
self.events, self.seq, self.now = [], 0, 0.0
self.crashed, self.inbox = set(), defaultdict(list)
self.n_sent = self.n_dropped = 0
def sample_delay(self):
if self.dist == "fixed":
return self.param
if self.dist == "gauss":
return max(0.0, self.rng.gauss(self.param, self.sigma))
if self.dist == "pareto": # 重尾：偶发超长延迟
return self.param * self.rng.paretovariate(1.5)
raise ValueError(self.dist)
def crash(self, node):
self.crashed.add(node)
def send(self, t, src, dst, msg):
self.n_sent += 1
if src in self.crashed or dst in self.crashed or self.rng.random() < self.loss:
self.n_dropped += 1
return
self.seq += 1
heapq.heappush(self.events, (t + self.sample_delay(), self.seq, dst, src, msg))
def step(self):
if not self.events:
return False
t, _, dst, src, msg = heapq.heappop(self.events)
self.now = max(self.now, t)
self.inbox[dst].append((src, msg))
return True
# ---------------------------------------------------------------- 检测器基类
class BaseFD:
"""每个节点维护自己的视图 declared[i][j]；harness 以"上帝视角"统计误判。"""
def __init__(self, n, net):
self.n, self.net = n, net
self.declared = [[False] * n for _ in range(n)]
self.declare_at = [[None] * n for _ in range(n)]
self.fp = 0
self.kill_node = self.kill_time = None
def declare(self, i, j, t):
if i == j or self.declared[i][j]:
return
self.declared[i][j], self.declare_at[i][j] = True, t
if j != self.kill_node or t < self.kill_time: # 判死一个当时还活着的节点
self.fp += 1
def detection_delay(self):
"""某个存活节点第一次认定 kill_node 已死的时刻（崩溃前就误判的记为 0）。"""
times = [max(self.declare_at[i][self.kill_node], self.kill_time)
for i in range(self.n)
if i != self.kill_node and self.declare_at[i][self.kill_node] is not None]
return None if not times else min(times) - self.kill_time
def on_tick(self, t):
raise NotImplementedError
def on_msg(self, t, dst, src, msg):
raise NotImplementedError
# ---------------------------------------------------------------- 1) 固定超时心跳
class FixedHeartbeat(BaseFD):
def __init__(self, n, net, period=0.05, timeout=0.15):
super().__init__(n, net)
self.period, self.timeout = period, timeout
self.next_send, self.seq = [0.0] * n, 0
self.last_seen = [[0.0] * n for _ in range(n)]
def on_tick(self, t):
for i in range(self.n):
if i in self.net.crashed:
continue
if t >= self.next_send[i]: # 周期性发送心跳
self.next_send[i] = t + self.period
self.seq += 1
for j in range(self.n):
if j != i:
self.net.send(t, i, j, {"type": "hb"})
for j in range(self.n): # 超时即判死
if j != i and not self.declared[i][j] and t - self.last_seen[i][j] > self.timeout:
self.declare(i, j, t)
def on_msg(self, t, dst, src, msg):
self.last_seen[dst][src] = t # 收到任何消息都算"活着"
if msg["type"] == "hb":
self.net.send(t, dst, src, {"type": "ack"}) # 回 ack，与自适应方案同消息量
# ---------------------------------------------------------------- 2) 自适应超时
class AdaptiveFD(BaseFD):
"""Jacobson/Karels: Timeout = EstimatedInterval + 4 * Deviation"""
def __init__(self, n, net, period=0.05, alpha=0.125, beta=0.25, k=4.0):
super().__init__(n, net)
self.period, self.alpha, self.beta, self.k = period, alpha, beta, k
self.min_to = 3 * period # 至少容忍连续 2 次丢探测
self.next_send, self.seq = [0.0] * n, 0
self.last_seen = [[0.0] * n for _ in range(n)]
self.prev_ack = [[None] * n for _ in range(n)]
self.est = [[0.06] * n for _ in range(n)] # EstimatedInterval
self.dev = [[0.015] * n for _ in range(n)] # Deviation
self.trace = []
def timeout_of(self, i, j):
return max(self.min_to, self.est[i][j] + self.k * self.dev[i][j])
def on_tick(self, t):
for i in range(self.n):
if i in self.net.crashed:
continue
if t >= self.next_send[i]:
self.next_send[i] = t + self.period
self.seq += 1
for j in range(self.n):
if j != i:
self.net.send(t, i, j, {"type": "ping"})
for j in range(self.n):
if j != i and not self.declared[i][j] and t - self.last_seen[i][j] > self.timeout_of(i, j):
self.declare(i, j, t)
def on_msg(self, t, dst, src, msg):
self.last_seen[dst][src] = t
if msg["type"] == "ping":
self.net.send(t, dst, src, {"type": "ack"})
elif msg["type"] == "ack": # 每收到一次确认就重算超时
i, j = dst, src
if self.prev_ack[i][j] is not None:
sample = t - self.prev_ack[i][j] # 样本 = 相邻两次确认的间隔
self.est[i][j] = (1 - self.alpha) * self.est[i][j] + self.alpha * sample
self.dev[i][j] = (1 - self.beta) * self.dev[i][j] + \
self.beta * abs(sample - self.est[i][j])
self.prev_ack[i][j] = t
if i == 0:
self.trace.append(self.timeout_of(i, j))
# ---------------------------------------------------------------- 3) Gossip 检测
class GossipFD(BaseFD):
def __init__(self, n, net, tg=0.05, tfail=0.60, tcleanup=1.0, fanout=3):
super().__init__(n, net)
self.tg, self.tfail, self.tcleanup, self.fanout = tg, tfail, tcleanup, fanout
self.next_send = [0.0] * n
self.counter = [0] * n # 自己的心跳计数
self.known = [[0] * n for _ in range(n)] # i 已知 j 的计数
self.ts = [[0.0] * n for _ in range(n)] # 本地时间戳
self.clean = [[False] * n for _ in range(n)]
self.rng = random.Random(7)
def on_tick(self, t):
for i in range(self.n):
if i in self.net.crashed:
continue
if t >= self.next_send[i]: # 周期性 gossip 自己的成员表
self.next_send[i] = t + self.tg
self.counter[i] += 1
self.known[i][i], self.ts[i][i] = self.counter[i], t
others = [j for j in range(self.n) if j != i and j not in self.net.crashed]
payload = [(x, self.known[i][x]) for x in range(self.n) if not self.clean[i][x]]
for j in self.rng.sample(others, min(self.fanout, len(others))):
self.net.send(t, i, j, {"type": "gossip", "list": payload})
for j in range(self.n): # 本地过期判定
if j == i or self.clean[i][j]:
continue
age = t - self.ts[i][j]
if age > self.tfail and not self.declared[i][j]:
self.declare(i, j, t)
if age > self.tfail + self.tcleanup: # Tcleanup 之后才真正删除
self.clean[i][j], self.declared[i][j] = True, False
def on_msg(self, t, dst, src, msg):
if self.ts[dst][src] < t:
self.ts[dst][src] = t # 收到消息即证明 src 活着
if msg["type"] != "gossip":
return
for x, cnt in msg["list"]:
if cnt > self.known[dst][x]: # 合并：只接受更新的计数
self.known[dst][x], self.ts[dst][x] = cnt, t
self.clean[dst][x], self.declared[dst][x] = False, False
# ---------------------------------------------------------------- 实验框架
def run_one(make_fd, net_kw, n=10, duration=20.0, dt=0.01, crash_time=12.0, crash_node=0):
random.seed(2026)
net = Network(seed=99, **net_kw)
fd = make_fd(n, net)
fd.kill_node, fd.kill_time = crash_node, crash_time
t = 0.0
while t < duration:
if t >= crash_time:
net.crash(crash_node)
fd.on_tick(t)
while net.events and net.events[0][0] <= t + dt:
net.step()
for dst in list(net.inbox.keys()):
for src, msg in net.inbox.pop(dst):
fd.on_msg(t, dst, src, msg)
t += dt
return {"detect": fd.detection_delay(), "fp": fd.fp, "msgs": net.n_sent, "fd": fd}
SCENARIOS = [
("S1 固定10ms 丢包 0%", dict(dist="fixed", param=0.01, loss=0.00)),
("S2 固定10ms 丢包10%", dict(dist="fixed", param=0.01, loss=0.10)),
("S3 固定10ms 丢包30%", dict(dist="fixed", param=0.01, loss=0.30)),
("S4 高斯σ=30ms 丢包5%", dict(dist="gauss", param=0.01, sigma=0.03, loss=0.05)),
("S5 重尾Pareto 丢包5%", dict(dist="pareto", param=0.0033, loss=0.05)),
]
DETECTORS = [
("固定心跳 T=0.15", lambda n, net: FixedHeartbeat(n, net, timeout=0.15)),
("固定心跳 T=0.30", lambda n, net: FixedHeartbeat(n, net, timeout=0.30)),
("自适应 J/K", lambda n, net: AdaptiveFD(n, net)),
("Gossip Tfail=0.6", lambda n, net: GossipFD(n, net, tfail=0.60)),
]
if __name__ == "__main__":
N, DUR, CT = 10, 20.0, 12.0
print(f"n={N} 个节点，模拟 {DUR}s，t={CT}s 时节点 0 崩溃；探测周期 50ms\n")
for sname, kw in SCENARIOS:
print(f"### {sname}")
print(f"{'检测器':<18s}{'检出时间(s)':>12s}{'误判次数':>10s}{'消息总数':>10s}")
print("-" * 52)
for dname, mk in DETECTORS:
r = run_one(mk, kw, n=N, duration=DUR, crash_time=CT)
d = "未检出" if r["detect"] is None else f"{r['detect']:.3f}"
print(f"{dname:<18s}{d:>12s}{r['fp']:>10d}{r['msgs']:>10d}")
print()
print("=== 自适应检测器在 S3(丢包30%) 下超时估计的演化（节点0 对某个 peer）===")
r = run_one(DETECTORS[2][1], SCENARIOS[2][1], n=N, duration=DUR, crash_time=CT)
tr = r["fd"].trace
for idx in range(0, len(tr), max(1, len(tr) // 8)):
print(f" 第 {idx:4d} 次确认后: Timeout = {tr[idx]:.4f}s")
print(f" 最终 : Timeout = {tr[-1]:.4f}s (固定方案恒为 0.1500s)")
运行结果（节选；随机种子固定，每次运行逐位一致）
n=10 个节点，模拟 20.0s，t=12.0s 时节点 0 崩溃；探测周期 50ms
### S1 固定10ms 丢包 0%
检测器 检出时间(s) 误判次数 消息总数
----------------------------------------------------
固定心跳 T=0.15 0.150 0 59598
固定心跳 T=0.30 0.300 0 59598
自适应 J/K 0.150 0 59598
Gossip Tfail=0.6 0.590 0 10152
### S2 固定10ms 丢包10%
固定心跳 T=0.15 0.140 10 56627
固定心跳 T=0.30 0.290 0 56627
自适应 J/K 0.150 5 56627
Gossip Tfail=0.6 0.590 0 10152
### S3 固定10ms 丢包30%
固定心跳 T=0.15 0.000 90 50788
固定心跳 T=0.30 0.000 5 50788
自适应 J/K 0.000 21 50788
Gossip Tfail=0.6 0.590 0 10152
### S4 高斯σ=30ms 丢包5%
固定心跳 T=0.15 0.140 1 58123
固定心跳 T=0.30 0.290 0 58123
自适应 J/K 0.180 0 58123
Gossip Tfail=0.6 0.590 0 10152
### S5 重尾Pareto 丢包5%
固定心跳 T=0.15 0.140 0 58198
固定心跳 T=0.30 0.290 0 58198
自适应 J/K 0.140 0 58198
Gossip Tfail=0.6 0.590 0 10152
=== 自适应检测器在 S3(丢包30%) 下超时估计的演化（节点0 对某个 peer）===
第 0 次确认后: Timeout = 0.1500s
第 110 次确认后: Timeout = 0.3164s
第 220 次确认后: Timeout = 0.3553s
第 330 次确认后: Timeout = 0.3488s
第 440 次确认后: Timeout = 0.2184s
第 550 次确认后: Timeout = 0.3313s
第 660 次确认后: Timeout = 0.5347s
第 770 次确认后: Timeout = 0.2674s
第 880 次确认后: Timeout = 0.3803s
最终 : Timeout = 0.4067s (固定方案恒为 0.1500s)
【代码做什么？】
- 复用 7.4.1 的
Network（同一套离散事件引擎与三种延迟分布）； BaseFD维护每个节点各自的视图declared[i][j]——这一点很关键：检测器不是”上帝视角”，而是十个节点各自判断；declare()在判死一个当时还活着的节点时把fp（误判）计数加一，并记录”崩溃发生之后”的首次判定时刻作为检测时间；FixedHeartbeat：每 50 ms 向所有其他节点发心跳，收方回 ack（消息量与自适应方案对齐），超时用常数 $T$；AdaptiveFD：同样每 50 ms 发一次 ping，收到 ack 后按 Jacobson/Karels 更新est/dev，超时取 $\max(3T_{probe},\ est + 4\,dev)$；GossipFD：每 50 ms 把整张成员表（(member, counter)列表）gossip 给 3 个随机目标，收方合并更大计数并刷新本地时间戳，T_fail到期标记失败、T_fail + T_cleanup到期才真正清理；- 主程序在五个场景（无丢包 / 10% 丢包 / 30% 丢包 / 高斯抖动 / 重尾 Pareto）下依次运行四种检测器，打印 检出时间 / 误判次数 / 消息总数 三列，最后打印自适应超时的演化轨迹。
【分布式机制透视】
- 同一份故障脚本、同一组延迟场景：五个场景都让节点 0 在 $t=12$ s 崩溃，因此”检出时间”列是可比的；
- 误判次数的含义：一次误判 = “某个节点在某时刻把另一个当时还活着的节点判死”。在 $n=10$ 里最多有 $10 \times 9 = 90$ 个”判死关系”，所以 S3 里固定超时 0.15 s 的 90 次误判意味着全连接意义上的彻底崩溃——每个节点都冤枉了其他所有节点；
- 消息总量的对比：心跳与自适应方案在 20 s 内发送约 5~6 万条消息（每条进程每 50 ms 给 9 个 peer 发一条 + 回一条 ack，共 $10 \times 9 \times 2 \times 400 \approx 7.2$ 万），而同样检测能力的 gossip 方案只用 1 万条（约 1/6），代价是检测时间从 0.14 s 拉长到 0.59 s，并且每条消息携带 $O(N)$ 个条目（字节数并不省）。
【与理论的对应】
- 这张表是 7.2.3”误判率 vs 检测时间 vs 带宽”三角的直接测量：固定 0.15 s 检测快但误判多，固定 0.30 s 误判少但检测慢一倍，没有任何一个固定值能在所有场景里同时占优；
- 自适应方案的价值：在 10% 丢包下把误判从 10 降到 5，在 30% 丢包下从 90 降到 21，而检出时间与最激进的固定方案相同（0.15 s）。其超时估计从 0.15 s 自动爬到 0.4 s 左右——对应 7.3.4 中”用一点检测时间换准确率”的自适应行为，这正是 Jacobson/Karels 公式在故障检测场景的移植价值；
- 自适应的边界：注意 S5（重尾）里自适应方案的误判是 0，固定方案也是 0——因为超时的安全下限 $3T_{probe}$ 已经覆盖了这些尾部样本；而真正让自适应”失灵”的场景是延迟分布的瞬时跳变（7.3.4 的”安全性失败面”），此时第一个尾部样本仍然会造成一次误判；
- gossip 方案用冗余换准确：它的误判在所有五个场景下都是 0，这不是因为它更”聪明”，而是因为关于”某节点还活着”的信息有多条独立路径同时传播（对应 7.3.2 的安全性论证）。
7.4.3 SWIM 完整实现（三个子协议 + incarnation 反驳）
"""7.4.3 SWIM 完整实现：故障检测 + 怀疑机制 + 感染式传播（只用标准库）"""
import heapq
import queue
import random
import threading
import time
T0 = time.monotonic() # 相对时间基准（仅用于打印日志）
N = 6 # 进程数
PROTOCOL_PERIOD = 0.10 # 协议周期 T'
ACK_TIMEOUT = 0.045 # 直接 ping 的等待上限
K_PINGREQ = 2 # 间接探测代理个数 K
SUSPICION_TIMEOUT = 0.80 # 怀疑超时：超过则 Confirm 为 Failed
MAX_PIGGYBACK = 4 # 每条消息最多携带的成员变更条数
DELAY = 0.004 # 正常单向延迟
class Network:
"""带延迟投递线程的模拟网络：支持逐条链路拥塞与节点崩溃。"""
def __init__(self, loss=0.0, delay=DELAY, seed=7):
self.loss, self.delay = loss, delay
self.rng = random.Random(seed)
self.lock = threading.Lock()
self.pending, self.seq, self.q = [], 0, {}
self.crashed, self.congested = set(), {} # congested[(src,dst)] = 延迟
self.slow_ack = {} # slow_ack[node] = 该节点迟发 ack 的额外延迟
self.sent, self.dropped = 0, 0
self.stop_flag = False
threading.Thread(target=self._run, daemon=True).start()
def _run(self):
while not self.stop_flag:
now = time.monotonic()
with self.lock:
while self.pending and self.pending[0][0] <= now:
_, _, dst, src, msg = heapq.heappop(self.pending)
self.q[dst].put((src, msg))
time.sleep(0.0005)
def send(self, src, dst, msg):
with self.lock:
self.sent += 1
if src in self.crashed or dst in self.crashed or self.rng.random() < self.loss:
self.dropped += 1
return
d = self.congested.get((src, dst), self.delay)
if msg.get("type") == "ACK":
d += self.slow_ack.get(src, 0.0) # 模拟"应答缓慢"的进程
self.seq += 1
heapq.heappush(self.pending, (time.monotonic() + d, self.seq, dst, src, msg))
def crash(self, nid):
with self.lock:
self.crashed.add(nid)
class SwimNode(threading.Thread):
def __init__(self, nid, net, ids):
super().__init__(daemon=True)
self.nid, self.net, self.ids = nid, net, list(ids)
self.inbox = queue.Queue()
self.lock = threading.RLock() # 保护成员表 / 传播缓冲区的锁
self.members = {j: {"state": "ALIVE", "inc": 0, "deadline": None} for j in self.ids}
self.inc = 0 # 本进程的 incarnation number
self.buffer = {} # mid -> [state, inc, 已捎带次数]
self.running, self.seq = True, 0
self.order, self.pos = random.sample(self.ids, len(self.ids)), 0
self.log = [] # (相对时间, 成员, 新状态) 变迁日志
self.proxy = {} # seq -> (请求者, 被探测者)
self.inc_log = [] # 自身 incarnation 自增历史
self.pending_seq, self.acked = None, False
net.q[nid] = self.inbox
# ---------------------------------------------------------- 成员表操作
def record(self, mid, state, inc):
with self.lock:
self.buffer[mid] = [state, inc, 0]
def merge(self, mid, state, inc, now):
"""SWIM 的优先级规则：Confirm 优先于一切；(inc 大) 优先；(同 inc) Suspect > Alive。"""
if mid == self.nid:
if state == "SUSPECT" and inc >= self.inc: # 被怀疑 -> 自增 incarnation 反驳
self.inc = inc + 1
self.inc_log.append((round(now - T0, 3), self.inc))
with self.lock:
self.members[self.nid]["inc"] = self.inc
self.record(self.nid, "ALIVE", self.inc)
return
with self.lock:
m = self.members[mid]
if state == "DEAD":
if inc >= m["inc"]:
m.update(state="DEAD", inc=inc, deadline=None)
self.log.append((round(now - T0, 3), mid, "DEAD"))
self.record(mid, "DEAD", inc)
elif inc > m["inc"]:
m.update(state=state, inc=inc,
deadline=now + SUSPICION_TIMEOUT if state == "SUSPECT" else None)
self.log.append((round(now - T0, 3), mid, state))
self.record(mid, state, inc)
elif inc == m["inc"] and m["state"] == "ALIVE" and state == "SUSPECT":
m.update(state="SUSPECT", deadline=now + SUSPICION_TIMEOUT)
self.log.append((round(now - T0, 3), mid, "SUSPECT"))
self.record(mid, state, inc)
def mark_alive_by_ack(self, mid, now):
"""收到（直接或间接）ack，证明 mid 活着；若曾被怀疑则撤销并传播 Alive。"""
with self.lock:
m = self.members[mid]
if m["state"] != "ALIVE":
m.update(state="ALIVE", deadline=None)
self.log.append((round(now - T0, 3), mid, "ALIVE(ack)"))
self.record(mid, "ALIVE", m["inc"])
def mark_suspect(self, mid, now):
with self.lock:
m = self.members[mid]
if m["state"] == "ALIVE":
m.update(state="SUSPECT", deadline=now + SUSPICION_TIMEOUT)
self.log.append((round(now - T0, 3), mid, "SUSPECT"))
self.record(mid, "SUSPECT", m["inc"])
def check_timeouts(self, now):
with self.lock:
expired = [(j, m["inc"]) for j, m in self.members.items()
if m["state"] == "SUSPECT" and m["deadline"] and now > m["deadline"]]
for j, inc in expired: # 怀疑超时 -> Confirm/Failed
self.merge(j, "DEAD", inc, now)
# ---------------------------------------------------------- 消息收发
def piggyback(self):
with self.lock:
items = sorted(self.buffer.items(), key=lambda kv: kv[1][2])[:MAX_PIGGYBACK]
for _, v in items:
v[2] += 1
return [(mid, v[0], v[1]) for mid, v in items]
def send(self, dst, mtype, **kw):
msg = {"type": mtype, "src": self.nid, "updates": self.piggyback()}
msg.update(kw)
self.net.send(self.nid, dst, msg)
def handle(self, src, msg):
now = time.monotonic()
for mid, state, inc in msg.get("updates", []):
self.merge(mid, state, inc, now)
t = msg["type"]
if t == "PING":
self.net.send(self.nid, src, {"type": "ACK", "seq": msg["seq"],
"target": msg["target"], "updates": self.piggyback()})
elif t == "PING_REQ": # 代理：代为探测并转发 ack
with self.lock:
self.proxy[msg["seq"]] = (src, msg["target"])
self.net.send(self.nid, msg["target"], {"type": "PING", "seq": msg["seq"],
"target": msg["target"],
"updates": self.piggyback()})
elif t == "ACK":
if msg["seq"] == self.pending_seq: # 本周期目标被确认存活
self.acked = True
self.mark_alive_by_ack(msg["target"], now)
with self.lock:
req = self.proxy.pop(msg["seq"], None)
if req and req[1] == src: # 我是代理，把 ack 转回请求者
self.net.send(self.nid, req[0], {"type": "ACK", "seq": msg["seq"],
"target": src, "updates": self.piggyback()})
def pump_until(self, deadline):
while time.monotonic() < deadline:
try:
src, msg = self.inbox.get(timeout=max(0.0, deadline - time.monotonic()))
except queue.Empty:
return
self.handle(src, msg)
# ---------------------------------------------------------- 协议周期
def pick_target(self):
with self.lock:
alive = {j for j, m in self.members.items() if m["state"] != "DEAD"}
for _ in range(len(self.order) + 1):
if self.pos >= len(self.order): # 遍历一轮后随机重排
self.order, self.pos = random.sample(self.ids, len(self.ids)), 0
j = self.order[self.pos]
self.pos += 1
if j != self.nid and j in alive:
return j
return None
def run(self):
while self.running:
start = time.monotonic()
self.protocol_period(start)
rest = PROTOCOL_PERIOD - (time.monotonic() - start)
if rest > 0:
time.sleep(rest)
def protocol_period(self, start):
now = time.monotonic()
self.check_timeouts(now)
target = self.pick_target()
if target is None:
self.pump_until(start + PROTOCOL_PERIOD)
return
self.seq += 1
self.pending_seq = (self.nid, self.seq)
self.acked = False
self.send(target, "PING", seq=self.pending_seq, target=target)
self.pump_until(start + ACK_TIMEOUT) # 阶段 1：直接 ping
if not self.acked:
others = [j for j in self.ids
if j not in (self.nid, target) and self.members[j]["state"] != "DEAD"]
for p in random.sample(others, min(K_PINGREQ, len(others))):
self.send(p, "PING_REQ", seq=self.pending_seq, target=target)
self.pump_until(start + PROTOCOL_PERIOD) # 阶段 2：等间接 ack
self.check_timeouts(time.monotonic())
if not self.acked:
self.mark_suspect(target, time.monotonic())
def view(self):
with self.lock:
return {j: (m["state"], m["inc"]) for j, m in self.members.items()}
def show(views, tag):
"""views[i][j] = (状态, incarnation)；只打印存活节点的行，但打印全部节点列。"""
cols = sorted(next(iter(views.values())).keys())
print(f"\n--- {tag} ---")
header = "视图/成员".ljust(9)
print(header + "".join(f"{j:>12d}" for j in cols))
for i in sorted(views):
if i not in views: # 已崩溃节点的视图不再有意义
continue
cells = "".join(f"{views[i][j][0][:4]}/{views[i][j][1]:<5d}" if views[i][j][0] != "DEAD"
else f"{'DEAD':>12s}" for j in cols)
print(f"{i:<8d}" + cells)
if __name__ == "__main__":
random.seed(2026)
net = Network(loss=0.0)
t0 = time.monotonic()
nodes = {i: SwimNode(i, net, range(N)) for i in range(N)}
for n in nodes.values():
n.start()
def at(t):
d = t - (time.monotonic() - t0)
if d > 0:
time.sleep(d)
at(1.20)
print("=" * 72)
print("阶段 1 结束：全部健康，成员视图应已收敛")
live = {0, 1, 2, 3, 4, 5}
show({i: nodes[i].view() for i in live}, "t=1.2s 全部健康（视图已收敛）")
print("\n阶段 2：t=1.2s 让节点 5 崩溃")
nodes[5].running = False
net.crash(5)
at(3.20)
live = {0, 1, 2, 3, 4}
show({i: nodes[i].view() for i in live}, "t=3.2s 节点 5 崩溃后应已 Confirm 为 DEAD")
print("\n阶段 3：t=3.2s 拥塞有向链路 0->2（直接 ping 必失败，靠 ping-req 救回）")
with net.lock:
net.congested[(0, 2)] = 0.15
at(4.60)
show({i: nodes[i].view() for i in live}, "t=4.6s 链路 0->2 拥塞：节点 2 仍必须 ALIVE")
print("\n阶段 4：t=4.6s 起节点 3 应答变慢（0.12s > 协议周期）：被怀疑 -> 自增 incarnation 反驳")
with net.lock:
net.congested.pop((0, 2), None)
net.slow_ack[3] = 0.12
at(6.60)
show({i: nodes[i].view() for i in live}, "t=6.6s 节点 3 应答缓慢：必须仍 ALIVE（inc 已自增）")
with net.lock:
net.congested.clear()
net.slow_ack.clear()
at(7.60)
for n in nodes.values():
n.running = False
time.sleep(0.4) # 排空在途消息
views_final = {i: nodes[i].view() for i in live}
show(views_final, "t=8.0s 拥塞解除后的最终视图")
net.stop_flag = True
print("\n=== 崩溃检测延迟：各节点首次把 5 标记为 SUSPECT / DEAD 的时刻 ===")
for i in sorted(live):
first_sus = next((ts for ts, mid, st in nodes[i].log if mid == 5 and st == "SUSPECT"), None)
first_dead = next((ts for ts, mid, st in nodes[i].log if mid == 5 and st == "DEAD"), None)
print(f" 节点 {i}: SUSPECT @ t={first_sus}s DEAD @ t={first_dead}s")
print("\n=== 节点 3 的 incarnation 反驳轨迹（被怀疑 -> 自增自证清白）===")
print(f" 节点 3 自身 incarnation 变化: " +
" -> ".join(f"{inc}@{ts}s" for ts, inc in nodes[3].inc_log))
for i in sorted(live):
n_sus = sum(1 for _, mid, st in nodes[i].log if mid == 3 and st == "SUSPECT")
print(f" 节点 {i} 曾把 3 标为 SUSPECT {n_sus:2d} 次，"
f"最终状态 = {views_final[i][3]}")
for i in live:
assert views_final[i][2][0] == "ALIVE", f"误判：节点 {i} 把 2 判死"
assert views_final[i][3][0] == "ALIVE", f"误判：节点 {i} 把 3 判死"
assert views_final[i][5][0] == "DEAD", f"节点 {i} 未发现 5 已崩溃"
states = {i: frozenset((j, s) for j, (s, _) in v.items()) for i, v in views_final.items()}
assert len(set(states.values())) == 1, "成员视图未收敛"
print(f"\n消息总数 = {net.sent}（其中 {net.dropped} 条被丢弃，含发往崩溃节点 5 的消息），"
f"节点数 = {N}，协议周期 = {PROTOCOL_PERIOD}s")
print("断言通过：所有存活节点视图一致；2、3 未被误判为 DEAD；5 被正确判死。")
运行结果（节选，运行时间约 8 秒）
--- t=3.2s 节点 5 崩溃后应已 Confirm 为 DEAD ---
视图/成员 0 1 2 3 4 5
0 ALIV/0 ALIV/0 ALIV/0 ALIV/0 ALIV/0 DEAD
1 ALIV/0 ALIV/0 ALIV/0 ALIV/0 ALIV/0 DEAD
2 ALIV/0 ALIV/0 ALIV/0 ALIV/0 ALIV/0 DEAD
3 ALIV/0 ALIV/0 ALIV/0 ALIV/0 ALIV/0 DEAD
4 ALIV/0 ALIV/0 ALIV/0 ALIV/0 ALIV/0 DEAD
--- t=4.6s 链路 0->2 拥塞：节点 2 仍必须 ALIVE ---
（5 个存活节点对 2 的状态均为 ALIV/0 —— 间接探测在误判发生前就把它救回了）
--- t=6.6s 节点 3 应答缓慢：必须仍 ALIVE（inc 已自增） ---
视图/成员 0 1 2 3 4 5
0 ALIV/0 ALIV/0 ALIV/0 ALIV/6 ALIV/0 DEAD
1 ALIV/0 ALIV/0 ALIV/0 ALIV/6 ALIV/0 DEAD
2 ALIV/0 ALIV/0 ALIV/0 SUSP/6 ALIV/0 DEAD
3 ALIV/0 ALIV/0 ALIV/0 ALIV/7 ALIV/0 DEAD
4 ALIV/0 ALIV/0 ALIV/0 SUSP/6 ALIV/0 DEAD
=== 崩溃检测延迟：各节点首次把 5 标记为 SUSPECT / DEAD 的时刻 ===
节点 0: SUSPECT @ t=1.603s DEAD @ t=2.312s
节点 1: SUSPECT @ t=1.558s DEAD @ t=2.313s
节点 2: SUSPECT @ t=1.512s DEAD @ t=2.308s
节点 3: SUSPECT @ t=1.503s DEAD @ t=2.304s
节点 4: SUSPECT @ t=1.508s DEAD @ t=2.309s
=== 节点 3 的 incarnation 反驳轨迹（被怀疑 -> 自增自证清白）===
节点 3 自身 incarnation 变化: 1@4.76s -> 2@5.116s -> 3@5.516s -> 4@5.716s
-> 5@6.016s -> 6@6.217s -> 7@6.517s
节点 0 曾把 3 标为 SUSPECT 6 次，最终状态 = ('ALIVE', 7)
...（节点 1/2/4 类似）
消息总数 = 1016（其中 24 条被丢弃，含发往崩溃节点 5 的消息），节点数 = 6，协议周期 = 0.1s
断言通过：所有存活节点视图一致；2、3 未被误判为 DEAD；5 被正确判死。
【代码做什么？】
- 真实的并发结构：
SwimNode继承threading.Thread，$N=6$ 个节点是 6 个独立线程，各自以 0.1 s 的协议周期运行；消息通过queue.Queue的收件箱传递；成员表与传播缓冲区由threading.RLock保护（merge/mark_alive_by_ack会在持锁状态下调用record，因此必须是可重入锁）； - 模拟网络线程：
Network起一个后台线程，把pending堆里到期的消息投递到目标节点的queue；支持逐条有向链路的拥塞（congested[(src,dst)]）与节点级的”应答变慢”（slow_ack[node]，表示进程被挂起或过载），以及crash(node)； - 故障检测子协议：
protocol_period()先check_timeouts()，再用轮转 + 遍历后随机重排（order/pos）选目标，发PING，等ACK_TIMEOUT；超时就向 $K$ 个随机代理发PING_REQ，一直等到周期结束；仍未 ack 则mark_suspect； - 传播子协议：
piggyback()从缓冲区里挑捎带次数最少的 4 条变更，附在每条PING/PING_REQ/ACK上（零额外消息）；merge()实现三级优先级（更高 inc 覆盖 / 同 inc 下Suspect > Alive/Confirm覆盖一切）； - 怀疑子协议：
mark_suspect设deadline = now + 0.8s；check_timeouts到期后merge(j, "DEAD", inc)；收到 ack 时mark_alive_by_ack撤销怀疑并传播Alive；被怀疑者自己在merge里发现mid == self.nid时自增 incarnation 并广播Alive(inc+1)； - 四个场景依次注入：① 全部健康（验证收敛）；② 节点 5 崩溃（验证检测 + 传播）；③ 有向链路 $0 \to 2$ 拥塞到 0.15 s（验证间接探测避免误判）；④ 节点 3 的 ack 延迟 0.12 s（验证怀疑 + incarnation 反驳）；最后恢复网络，打印终态视图并断言。
【分布式机制透视】
- 为什么用线程而不是离散事件：本程序要展示的是”多进程各自独立、通过消息交互、共享状态需要加锁“这一真实分布式结构。线程 +
Queue让每个节点的”局部视图”成为真正的局部变量，任何跨节点状态的读取都必须经过消息传递——这与真实系统的边界一致。（若把Network换成基于socket的 localhost 通信，程序结构可以几乎不变。） - 对称的不可靠性：注意场景 ④ 中”节点 3 变慢”是一个双向的混淆源——别人觉得 3 慢，3 也会因为 ack 回不来而觉得别人慢。本实现里 3 的入向 ack 延迟只影响别人对它，因此只有 3 被怀疑；如果把中心拥塞改成双向，你会看到 3 也开始怀疑所有人（这正是真实部署中”网络劣化节点引发全组怀疑风暴”的来源，也是 HashiCorp Serf 引入 local health multiplier 之类自检机制的动机）。
incarnation的角色：它相当于给”成员状态”加了一个逻辑版本号，使”Suspect/Alive/Confirm”三类消息的合并变成单调、可交换、幂等的操作（类似 CRDT 的 join 语义）。这是弱一致成员视图能够”最终收敛而不需要共识”的根本原因。
【与理论的对应】
- 阶段 ① 验证 7.3.3 的活性 L2（视图最终收敛）；
- 阶段 ② 验证 安全性 S1（强完备性 + 时间有界）：实测 SUSPECT 在崩溃后 $0.3\sim0.4$ s（3~4 个周期）出现，DEAD 在约 $1.1$ s（11 个周期）出现，其中 $0.8$ s 是怀疑超时、其余是轮转遍历延迟与传播延迟；
- 阶段 ③ 验证 间接探测的安全性作用（消除”单路径拥塞 ⇒ 误判”这一最常见的误判源）；
- 阶段 ④ 验证 安全性 S2（误判可撤销）与活性 L1（refute 一定有效）：节点 3 被每个节点怀疑 6~7 次、incarnation 涨到 7，但从未进入 DEAD，也从未离开成员表；
- 最后的
assert把四条理论性质变成可执行的断言：2/3 未被判死（准确性）、5 被判死（完备性）、所有存活节点视图一致（收敛性）。注意：如果调小SUSPICION_TIMEOUT或调大ACK_TIMEOUT，这些断言会失败——这恰好说明”参数选择就是 7.3.5 那条不可能性定理的工程表达”。
7.5 性能与可扩展性分析
7.5.1 理论下界：最优负载 $L^*$ 与 $N$ 无关
讲义（及 SWIM 论文引用的 PODC 2001 结果）给出了一个关键的负载下界：为了在检测时间 $T$ 内发现故障、同时把每成员的误判率控制在 $P_M(T)$ 以内，在独立丢包概率为 $p_{ml}$ 的网络上，每条成员每秒最少需要发送的消息数为
\[L^{*} \;=\; \frac{\log P_M(T)}{T \cdot \log p_{ml}} \;=\; \frac{\log \big(1/P_M(T)\big)}{T \cdot \log \big(1/p_{ml}\big)}\]（两式等价，第二式把两个负数取正，更直观。）
这个公式最重要的一点：$L^*$ 与组规模 $N$ 无关。 直觉解释：为了”相信”一个成员还活着，你需要收到足够多条独立的消息，使得”这些消息全部丢失”的概率低于 $P_M(T)$——需要的消息条数只取决于 $P_M(T)$ 与 $p_{ml}$，而与”组里有多少人”无关。任何负载随 $N$ 增长的方案，本质上都是在做无用功。
算例：$P_M(T) = 10^{-6}$，$p_{ml} = 0.01$，$T = 1$ s：
\[L^{*} = \frac{\ln 10^{6}}{1 \cdot \ln 100} = \frac{13.82}{4.61} \approx 3.0\ \text{条/秒/成员}\]即理论上每条成员每秒发 3 条消息就够。对照下表，全互探心跳在 $N=1000$ 时要发 $1000$ 条/秒——超出发送下界 300 倍以上。
7.5.2 各方案的负载、检测时间与误判率对照
| 方案 | 每条进程负载 $L$ | 全网消息量/单位时间 | 首次检测时间 | 误判率 | 备注 |
|---|---|---|---|---|---|
| 集中式心跳 | $O(1)$ | $O(N)$ | $O(T)$ | 中心误判影响全体 | 热点；中心是单点故障 |
| 环状心跳 | $O(1)$ | $O(N)$ | 单故障 $O(T)$；多故障不可预测 | 中 | IBM SP2 等集群机 |
| 全互探心跳 | $L = N/T$（$O(N)$） | $O(N^2)$ | $O(T)$（常数） | 单条丢失即误判，差 | 负载与规模平方增长 |
| Gossip-style（整表） | $L = N\log N / T$ | $O(N)$ 条，但字节 $O(N^2)$ | $T \approx \log N \cdot t_g$ | 好（多路径冗余） | 用带宽换准确性；带宽被整表大小卡住 |
| SWIM | 常数（每周期 1 ping + ≤K 个 ping-req + 若干 ack） | $O(N)$ 条，与 $N$ 无关的常数大小 | 期望 $\frac{e}{e-1}\approx 1.58$ 个周期（常数）；最坏 $2N-1$ 个周期 | $P_M(T)$ 随 $K$ 指数下降；另有怀疑机制兜底 | 论文实测：$< 2L^$；15% 丢包下 $< 8L^$ |
| 理论下界 $L^*$ | $\frac{\log(1/P_M)}{T\log(1/p_{ml})}$ | $N L^*$ | $T$（依定义） | $P_M(T)$ | 与 $N$ 无关 |
讲义对”为什么心跳与 gossip 都次优”的总结：它们都试图”让所有进程同时检测到故障”，从而把故障检测与信息传播两个组件揉在了一起；一旦分开，就可以用非心跳式（non-heartbeat based）的检测组件达到下界附近。这正是 SWIM 的设计起点。
7.5.3 可扩展性上限与真实系统的实测数据
| 维度 | 观察 | 数据来源 |
|---|---|---|
| SWIM 每进程负载 | 平均约 2.0 条消息/协议周期，直到 $N=55$ 都保持不变；$N=28$ 时”每周期发送超过 5 条”的概率 $< 0.01$ | SWIM 论文（PC 集群，协议周期 2 s，$K=3$） |
| SWIM 报文大小 | 基础版 15 B；带感染式传播版 135 B（最多捎带 6 条成员变更）——与组规模无关 | SWIM 论文 |
| SWIM 检测/传播延迟 | 平均首次检测时间与组规模无关，符合 $\frac{e}{e-1}$ 的解析值；传播延迟中位数始终只有几个协议周期 | SWIM 论文 |
| SWIM 在高丢包下的鲁棒性 | 10% 人工丢包下，17 个进程依次加入：SWIM:Basic 稳定在 2 个成员、SWIM+Inf. 稳定在 4 个，而 SWIM+Inf.+Susp. 稳定在 12 个 | SWIM 论文 |
| 成员管理的工程上限 | SWIM 类协议（Consul/Serf）在数千至上万节点规模可用；gossip 类（Cassandra）通常单集群数百至数千节点；Raft 类成员管理（etcd/ZooKeeper）通常限制在个位数~数十个投票成员（每次成员变更都要一轮共识） | 工程经验（补充说明） |
| 故障率的量级 | 单机 MTTF 按 10 年计：120 台集群 1 个月一次故障；12000 台数据中心 7.2 小时一次；软故障更频繁 | 讲义 |
结论性的工程判断：可扩展性的天花板不由 CPU 或内存决定，而由”每进程负载是否随 $N$ 增长”决定。SWIM 把每进程负载做成常数、把”多路径冗余”交给随机的间接探测、把”传播”变成免费的捎带，因此它的天花板远高于心跳方案；而它的代价是弱一致成员视图与需要上层配合的脑裂防护。
7.6 关键要点
- 故障检测是容错的前置条件，而它在异步系统中天生不可靠。 “崩溃”与”慢”在有限时间内不可区分，因此不存在既强完备又强准确的检测器；工程上的正解是”完备性永远保证、准确性只做概率保证“。
- 完备性优先于准确性，是因为两者的代价不对称：漏判让系统永久阻塞（活性彻底丧失），误判只让系统抖动（可用性下降）。所以真实检测器宁可多冤枉，也不愿漏掉。
- 误判率、检测时间、带宽构成三角，任何基于超时的方案都只能选一个点；SIWM 类的价值在于通过改变探测结构（随机 + 间接 + 怀疑）把这个三角的边界往外推，而不是在同一条曲线上的不同点之间挪动。
- 分离”检测”与”传播”是可扩展性的关键一招：检测只需要”某个人”尽快知道（常数负载、随机探测），传播可以让”所有人”慢一点知道（感染式、$O(\log N)$ 轮、捎带零额外消息）。
- SWIM 的怀疑机制把”永久误判”降级为”暂时误判”：用
Suspect中间态 + 怀疑超时 + 只能由被怀疑者自己自增的 incarnation number 实现 refute，代价是检测时间被拉长 $T_{susp}$。 - 成员管理的一致性与共识同难：弱一致成员视图（gossip/SWIM）必须配合 quorum/lease 才能防脑裂；强一致成员视图（Raft/ZAB）用共识代价换取”配置永不分裂”。“成员管理”是分布式系统里最被低估的难题之一。
- Grid 的教训：跨组织的资源共享如果标准过于复杂、缺乏统一所有权，就会被”集中所有权 + 虚拟化 + 按需付费”的云降维打击；但 VO 联邦、跨域认证委托、两级调度这些思想被多云与联邦云继承了下来。
7.7 常见陷阱与注意事项
陷阱：把超时设得足够大就能消除误判。 为什么错：异步模型中延迟无上界，任何有限超时都存在被超过的概率（7.3.5 的构造性反证）；而且超时越大，检测越慢、崩溃节点在成员表中”赖”得越久，漏判窗口也变长。 正确做法：接受误判不可避免，用自适应超时 + 多条独立探测路径 + 怀疑/反驳机制把误判率压到可接受，并让上层容忍误判。
陷阱：以为”心跳收不到”就等于”进程死了”。 为什么错：收不到心跳有三种可能——进程崩溃、进程慢（GC/调度）、这条路径丢包/拥塞；真实系统里第三种最常见（尤其在跨机架、跨可用区流量下）。 正确做法：先区分”是节点的问题”还是”是路径的问题”——这正是 SWIM 用 $K$ 条间接路径去做的判定；工程上还可以用多种独立探测源（多个监控者交叉验证）来消除路径相关性。
陷阱：把”成员列表”当成一份全局共享的数据结构。 为什么错：成员列表是每个节点各自的局部副本，在任一时刻彼此可能不同（弱一致）。如果代码里假设”我看到 5 个成员，别人也一定看到 5 个”，就会在视图切换的瞬间做出不一致的决定（选主、分片迁移、quorum 计算）。 正确做法：把成员视图当作最终收敛的近似值，任何依赖”精确成员集合”的决定都必须走共识或 quorum，而不是读本地表。
陷阱：在 SWIM 里让”任何人”都能增加某成员的 incarnation number。 为什么错：inc 是”成员状态的版本号”，它权威性的唯一来源是”只有本人知道自己是否活着“。如果别人也能抬高，恶意或故障节点就能通过不断抬高 inc 把某个健康节点永久压制在 Suspect/Failed 上，refute 机制彻底失效（同时也破坏了合并操作的单调性）。 正确做法：严格遵守”inc 只能由自己自增”，并在合并时只接受更高 inc 的状态（见 7.3.3 的
merge）。陷阱：怀疑超时 $T_{suspect}$ 设得过短。 为什么错：$T_{suspect}$ 是”冷静期”，必须足够长，使 refute 的
Alive(inc+1)有时间传播到所有正在怀疑它的节点；否则它们会在收到反驳之前就Confirm为DEAD——而Confirm不可撤销，被误杀的节点只能重新加入组（丢失状态、触发无谓的数据迁移）。 正确做法：$T_{suspect}$ 至少取”传播一圈所需时间”的若干倍（工程上常取 $O(\log N)$ 个协议周期到数十秒），并配合重启抑制（restart backoff）防止刚回来的节点被立刻二次误判。陷阱：把 gossip 的
T_fail与T_cleanup混为一谈，或者判死后立刻删除表项。 为什么错：立刻删除会让在途的旧 gossip 把该表项重新插回来，产生”死而复生”的抖动（讲义专门用一张图演示了这个现象）。 正确做法：T_fail只负责”标记为失败”，T_cleanup负责”真正删除”，且后者要大于”任何消息可能的最大在途时间”。陷阱：在成员协议里忘记”把失败信息也传播出去”。 为什么错：很多实现只传播 join，把 failure 当作本地判定。于是不同节点会在不同时间得出不同结论，视图长期不一致；更糟的是，某些节点可能永远收不到失败信息。 正确做法：把
Suspect/Alive/Confirm（或JOIN/LEAVE/FAILED）一律当作需要传播的成员变更，进入同一个感染式传播缓冲区。陷阱：在云上照搬 Grid 的中间件思路（或反之）。 复杂度的来源不同：Grid 的复杂度来自多机构联邦（信任边界多），云的复杂度来自故障、规模与按需性。正确做法：先明确信任边界与所有权，再选机制——跨组织用联邦身份（OIDC/SPIFFE 等），平台内用 IAM 与租户隔离。
7.8 思考题（带答案）
题 1（计算题）：某数据中心有 $N = 100$ 个节点组成一个进程组，应用要求故障检测时间 $T = 1$ 秒、每成员误判率 $P_M(T) \le 10^{-6}$，网络独立丢包率 $p_{ml} = 1\%$。请计算：(a) 理论最优的每成员消息负载 $L^*$；(b) 全互探心跳方案的实际负载与倍数；(c) 若改用 SWIM（每协议周期 $T^{\prime}=1$ s），估算其每成员负载。（取 $\ln 10^6 = 13.8$，$\ln 100 = 4.6$）
答案：
(a) 直接代入下界公式：
\[L^{*} = \frac{\ln(1/P_M)}{T \cdot \ln(1/p_{ml})} = \frac{13.8}{1 \times 4.6} \approx \mathbf{3.0\ \text{条/秒/成员}}\]物理含义：为了让”该节点还活着”这一结论的错误概率低于 $10^{-6}$，在 1% 丢包下需要约 3 条互相独立的消息在 1 秒内到达——与 $N$ 完全无关。
(b) 全互探心跳每条进程每周期要发给其他 $N-1 = 99$ 个成员，因此
\[L_{\text{all-to-all}} = \frac{N-1}{T} \approx 99\ \text{条/秒/成员},\qquad \frac{L}{L^{*}} = \frac{99}{3.0} \approx \mathbf{33\ \text{倍}}\]全网消息量约 $100 \times 99 = 9900$ 条/秒（若加 ack 则翻倍）。
(c) SWIM 的每协议周期负载是常数：1 条 PING + 超时时的至多 $K$ 条 PING_REQ（通常 $K=3$，且只有超时才发）+ 回应别人 ping 的 ACK。稳态下平均约 2~4 条/周期，即 $L_{\text{SWIM}} \approx 2\sim4$ 条/秒/成员，与 $N=100$ 还是 $N=10000$ 无关，且检测时间为常数（不含怀疑超时约为 $1.58$ 个周期）。论文给的经验值正是”$E[L] < 2L^$、15% 丢包下 $L < 8L^$”。
关键结论：本例中 SWIM 的负载只有全互探心跳的 1/30 左右，而且这个比值随 $N$ 增长而继续变大——这就是”可扩展性”的定量含义。
题 2（概念题）：讲义明确提出”完备性永远保证、准确性只做概率保证”。请解释：为什么把准确性做成概率保证是合理的工程选择？ 如果反过来（保证准确性、放弃完备性）会发生什么？
答案：
- 代价不对称：漏判（不完备）意味着系统永远等不到某个已死节点的响应——Raft 永远选不出 leader、quorum 永远凑不齐、请求永远挂着，活性彻底丧失，且没有自愈路径（因为没有新事件发生）。误判（不准确）意味着错误地把活节点踢出组——系统会抖动、会做无谓的选主与数据迁移，但只要检测器最终停止误判（$\Diamond P$ 型），系统会恢复，且上层可以用 quorum/lease 来限制误判造成的实际损害。
- 可实现性：一个真的崩溃的进程确实不再发消息，所以”等足够久 + 遍历所有成员”必然能发现它（7.3.3 的时间有界完备性）；而”慢”与”死”在异步模型下原理上不可区分，准确性不可能被彻底保证。
- 反过来的后果：如果保证准确性（永不冤枉人），那么检测器必须”永远等待”（7.3.5 的反证中的第二种情形），于是就没有任何故障会被报告——系统在有节点崩溃后会无限期挂起。这等价于”放弃故障检测”本身。
题 3（辨析题）：”既然 SWIM 用 $K$ 个代理做间接探测就能避免误判，那把 $K$ 调得越大越好。”这个直觉错在哪？
答案：它混淆了”降低误判概率”与”消除误判”。
- 误判概率随 $K$ 指数下降，但永不为零：只有当直接路径与全部 $K$ 条间接路径同时在同一个周期内失效时才会误判。$K$ 越大，这种”路径相关性失效”越不可能，但数据中心里的故障往往是相关的——机架交换机故障会让一批路径同时失效，此时增大 $K$ 收益很小。
- $K$ 直接放大负载：每次超时都要额外发 $K$ 条
PING_REQ，并且每个代理还要各自发一条PING并回一条ACK，即一次超时的代价是 $O(K)$ 条额外消息。$K$ 太大时，一旦网络抖动导致大量超时，就会形成”探测风暴“——额外的探测流量进一步加剧拥塞，导致更多超时，形成正反馈（这在真实系统中表现为”检测器把网络打垮”）。 - $K$ 不解决根本问题：如果被探测者本身很慢（GC 停顿、CPU 被抢占），无论多少条路径都拿不到及时 ack——这时起作用的是怀疑机制 + incarnation 反驳，而不是 $K$。
- 正确做法：$K$ 取一个小的常数（SWIM 论文用 3），把”准确性”的其余责任交给怀疑机制、以及上层的 quorum/lease；同时给”超时引发的探测风暴”加上限流与退避。
题 4（应用题）：在 7.4.3 的 SWIM 实现里，我们把”节点 3 的 ack 延迟 0.12 s（大于协议周期 0.1 s）”注入进去，观察到每个节点都把 3 标记为 SUSPECT 6~7 次，3 的 incarnation 涨到 7，但它从未被 Confirm 为 DEAD。请解释这条时间线背后的三个机制，并说明如果 $T_{suspect}$ 被设为 0.2 s 会发生什么。
答案：
三个机制：
- 检测（ping + 间接探测）：节点 3 的 ack 变慢后，任何节点的一个协议周期内都拿不到 ack（直接路径超时，$K$ 个代理的 ping 也因为它回复慢而拿不到 ack），于是判定”这个周期内 3 没有响应”——注意此时只是本地标记 SUSPECT，并不判死（7.3.3 步骤 G）。
- 传播（感染式）：
Suspect(3, inc)被写入缓冲区，捎带在后续的PING/PING_REQ/ACK上传遍全组，于是所有节点的视图里 3 都变成SUSPECT（这解释了”每个节点都标记了 6~7 次”）。 - 反驳（refute，incarnation）：节点 3 自己在收到捎带的
Suspect(3, inc)后（merge中mid == self.nid分支）自增 incarnation 并广播Alive(3, inc+1)。由于”更高 inc 覆盖更低 inc”，这个消息会让所有节点把 3 改回ALIVE。3 在下一个周期又被怀疑，于是 inc 再涨——形成”怀疑 → 反驳 → 再怀疑”的循环，inc 单调上升，而 3 始终留在成员表里。这就是”把永久误判降级为暂时误判”。
如果 $T_{suspect} = 0.2$ s：冷静期变短，”怀疑 → 反驳 → 传到所有怀疑者”这条链来不及在一个 $T_{suspect}$ 内走完（实测反驳传播需要约 $0.3\sim0.5$ s）。于是某些节点会在收到 Alive(inc+1) 之前就执行 Confirm → DEAD。而 Confirm 覆盖一切且不可撤销：这些节点会把 3 从成员表删除，而其他节点仍认为 3 是 ALIVE——成员视图出现永久分歧（正是 7.4.3 最后那条 assert 所有存活节点视图一致 会失败的情形）。要修复只能靠 3 重新加入组（重新走 join 流程，损失状态与时间）。结论：$T_{suspect}$ 的选择不是性能调参，而是正确性参数。