分布式系统中的故障检测器：原理、实现与应用

# 分布式系统中的故障检测器：原理、实现与应用 ## 1. 解决基本共识问题的最弱故障检测器 在不限制故障进程数量的环境中，排除不现实的故障检测器后，完美故障检测器类 P 是解决诸如统一共识、原子广播和终止可靠广播等基本共识问题的最弱故障检测器。 ### 1.1 原子广播算法 每个进程 p 执行以下操作： - **初始化**： ```plaintext R_delivered ← ∅ A_delivered ← ∅ k ← 0 ``` - **执行 A_broadcast(m)**： ```plaintext Task 1 R_broadcast(m) ``` - **A_deliver(–) 操作**： ```plaintext when R_deliver(m) Task 2 R_delivered ← R_delivered ∪ {m} when R_delivered − A_delivered ≠ ∅ Task 3 k ← k + 1 A_undelivered ← R_delivered − A_delivered propose(k, A_undelivered) wait until decide(k, msgSetk) A_deliverk ← msgSetk − A_delivered atomically deliver all messages in A_deliverk in some determinisic order A_delivered ← A_delivered ∪ A_deliverk ``` ### 1.2 不同共识问题 - **统一共识**：在普通共识中，协议属性允许坏进程与好进程做出不同的决策，而统一共识的统一协议属性则要求任何两个进程（无论好坏）都不能做出不同的决策。 - **终止可靠广播**：解决共识问题等同于解决原子广播问题。终止可靠广播是原子广播的一种更强形式，除了像原子广播一样按顺序传递消息外，对于故障进程广播但没有正确进程传递的消息，进程应传递特定的 nil 值。 ### 1.3 故障检测器层次结构 在不限制故障进程数量的环境中，统一共识比普通共识更难，统一共识和原子广播比终止可靠广播弱。而完美故障检测器类 P 是解决这些共识问题的唯一有用类。 ## 2. 现实故障检测器 故障检测器通常被定义为故障模式的函数，但有些故障检测器能提供关于未来故障的信息，这种故障检测器不现实且无法实现。因此，定义了现实故障检测器类 R，它不能预测未来。 ### 2.1 现实故障检测器的定义 一个故障检测器是现实的，如果它不能预测未来，即对于任何时间 t 和任何故障模式 F，它都不能提供关于 F 中 t 之后崩溃的确切信息。形式上，现实故障检测器类 R 是满足以下属性的故障检测器 D 的集合： ```plaintext ∀〈F, F ′〉 ∈ E, ∀t ∈ ℝ such that ∀t1 ≤ t: F(t1) = F ′(t1) We have: ∀H ∈ D(F), ∃H′ ∈ D(F ′) such that ∀t1 ≤ t; ∀pi ∈ Π: H(pi, t1) = H′(pi, t1). ``` ### 2.2 示例 - **Scribe (C)**：是一个现实的故障检测器，它实时查看所有进程的情况，并根据所见输出进程列表。 - **The Marabout (M)**：是一个不现实的故障检测器，它输出故障进程列表，包括已经崩溃或将要崩溃的进程。 ## 3. 共识的最弱故障检测器 在不限制故障进程数量的情况下，完美故障检测器类 P 是解决共识问题的最弱“现实”故障检测器类。 ### 3.1 证明思路 - **任何共识算法都是“全的”**：任何决策事件的因果链都包含来自在决策时未崩溃的每个进程的消息。 - **如果现实故障检测器 D 实现了全共识算法，则 D 可以转换为完美故障检测器 P**：由于 D 是现实的且算法是全的，为了准确跟踪进程故障，在没有咨询每个正确进程的情况下不会做出决策。 ## 4. 终止可靠广播的最弱故障检测器 在不限制崩溃进程数量的情况下，现实故障检测器中解决终止可靠广播的最弱类是 P。 ### 4.1 充分条件 终止可靠广播问题可以由任何完美故障检测器解决。当执行终止可靠广播的实例 (k, k′) 时，每个进程等待直到从 pk 接收值或怀疑 pk。前者情况下，它将接收到的值提交给共识；后者情况下，它提交值 nil。传递的值是共识值。 ### 4.2 必要条件 假设 A 是使用故障检测器 D 的任何终止可靠广播算法。可以使用终止可靠广播算法 A 在分布式变量 output(P) 中模拟类 P 的故障检测器 D 的输出。当进程 pj 为算法的实例 (i, *) 传递 nil 时，pj 将 pi 添加到 output(P)j。任何崩溃的进程最终将被永久添加到每个正确进程的 output(P) 中。 ## 5. 故障检测器的实现 下面是一个基于超时的最终完美故障检测器 D∈♦P 在部分同步模型中的实现算法： ### 5.1 变量说明 - `Outputp`：进程 p 的怀疑列表，初始为空。 - `q`：用于标识系统中每个进程的循环变量。 - `Π`：系统中所有进程的集合。 - `τp(q)`：进程 p 对进程 q 的超时时间间隔。 ### 5.2 算法实现 ```plaintext Every process p executes the followi ```