共识算法：从日志记录到随机化的全面解析

### 共识算法：从日志记录到随机化的全面解析 #### 1. 领导者驱动共识算法的终止与性能 领导者驱动共识算法在终止性方面表现出色。由于 epoch - change 原语的单调性和一致性，以及算法仅在先前活动的、时间戳较小的 epoch 共识实例中止后才初始化新实例，它满足调用格式良好的 epoch 共识实例序列的要求。根据底层 epoch - change 原语的最终领导权属性，存在一个时间戳为 ts 且领导者为 ℓ 的 epoch，此后不再有新的 epoch 启动，且 ℓ 是正确的。该算法仅在 epoch - change 原语启动另一个 epoch 时才中止 epoch 共识实例，因此在启动 epoch (ts, ℓ) 之后，epoch 共识实例 ep.ts 的终止条件意味着每个正确的进程最终会在实例 ep.ts 中进行 ep - 决策，并紧接着进行 uc - 决策。 在性能方面，“领导者驱动共识”算法的复杂度完全取决于底层 epoch - change 和 epoch 共识原语的实现复杂度，因为该算法不直接使用点对点链接抽象或广播抽象进行消息通信。 #### 2. 日志记录共识 ##### 2.1 日志记录共识概述 在故障恢复模型中，我们考虑使用崩溃 - 恢复进程抽象来解决共识问题。这类进程可能会任意多次崩溃和恢复，但如果一个进程最终不再崩溃并持续运行，它仍被视为正确的进程。我们引入了日志记录统一共识抽象，其实现将依赖于上一节的“领导者驱动共识”算法。同时，我们还为故障恢复模型引入了 epoch - change 和 epoch 共识抽象的扩展及其相应实现，目的是展示如何组合多个抽象以在崩溃和后续恢复的情况下继续工作。 ##### 2.2 日志记录统一共识规范 日志记录统一共识抽象是在统一共识抽象的基础上进行了小改动，通过放宽终止属性并消除完整性属性得到。具体来说，只有从不崩溃的正确进程才需要进行决策，并且一个进程可以多次决策，这在故障恢复模型中是不可避免的。 日志记录统一共识的规范如下： | 模块 | 名称：LoggedUniformConsensus，实例 luc | | --- | --- | | 事件 | 请求：⟨luc, Propose | v ⟩：提议值 v 进行共识；指示：⟨luc, Decide | decision ⟩：通知上层稳定存储中的变量 decision 包含共识的决策值 | | 属性 | LUC1：终止性：每个从不崩溃的正确进程最终会记录决策某个值；LUC2：有效性：如果一个进程记录决策 v，则 v 是由某个进程提议的；LUC3：统一一致性：没有两个进程记录决策不同的值 | 为了容忍崩溃和后续恢复，高层模块可以在日志记录统一共识中多次提议相同的值，也可以多次记录决策。当高层模块从崩溃中恢复且日志记录统一共识抽象尚未记录决策时，它会再次提议相同的值，以确保共识抽象最终终止并记录决策一个值。 为了使算法适应故障恢复模型，我们需要提供适用于崩溃 - 恢复进程抽象的日志记录 epoch - change 抽象和日志记录 epoch 共识抽象。 ##### 2.3 日志记录 epoch - change 日志记录 epoch - change 抽象与崩溃停止进程的对应抽象几乎相同，唯一的区别在于活性条件，它将一些要求从仅仅是正确的进程加强到从不崩溃的进程。具体来说，日志记录 epoch - change 的最终领导权属性表明，每个正确进程启动的最后一个 epoch 的领导者进程 ℓ 不仅是正确的，而且实际上从不崩溃。 日志记录 epoch - change 抽象会将下一个要启动的 epoch 的时间戳和领导者写入稳定存储中的变量 startts 和 startℓ。其规范如下： | 模块 | 名称：LoggedEpochChange，实例 lec | | --- | --- | | 事件 | 指示：⟨lec, StartEpoch | startts, startℓ⟩：通知上层稳定存储中的变量 startts 和 startℓ 包含下一个要启动的 epoch 的时间戳和领导者 | | 属性 | LEC1 - LEC2：与 epoch - change 中适用于日志启动 epoch 的属性 EC1 - EC2 相同；LEC3：最终领导权：存在一个时间点，此后每个正确进程都已日志启动某个 epoch，且不再日志启动其他 epoch，使得每个正确进程日志启动的最后一个 epoch 是 epoch (ts, ℓ)，并且进程 ℓ 从不崩溃 | 下面是“日志记录领导者基 epoch - change”算法的代码实现： ```python Implements: LoggedEpochChange, instance lec. Uses: StubbornPointToPointLinks, instance sl; StubbornBestEffortBroadcast, instance sbeb; EventualLeaderDetector, instance Ω. upon event ⟨lec, Init ⟩do trusted := ℓ0; (startts, startℓ) := (0, ℓ0); ts := rank(self) − N; upon event ⟨lec, Recovery ⟩do retrieve(startts); upon event ⟨Ω, Trust | p ⟩do trusted := p; if p = self then ts := ts + N; trigger ⟨sbeb, Broadcast | [NEWEPOCH, ts] ⟩; upon event ⟨sbeb, Deliver | ℓ, [NEWEPOCH, newts] ⟩do if ℓ = trusted ∧ newts > startts then (startts, startℓ) := (newts, ℓ); store(startts, startℓ); trigger ⟨lec, StartEpoch | startts, startℓ⟩; else trigger ⟨sl, Send | ℓ, [NACK, newts] ⟩; upon event ⟨sl, Deliver | p, [NACK, nts] ⟩such that nts = ts do if trusted = self then ts := ts + N; trigger ⟨sbeb, Broadcast | [NEWEPOCH, ts] ⟩; ``` 该算法的单调性和一致性属性与原始的“领导者基 epoch - change”算法相同，并且每次 startts 值改变时都会进行记录。最终领导权属性直接得到满足，因为最终领导者进程 ℓ 必须是从不崩溃的进程。每当 Ω 选择一个新的领导者时，该算法会产生一个通信步骤和 O(N) 条消息，并且每次启动一个 epoch 时会写入一次稳定存储。 ##### 2.4 日志记录 epoch 共识 日志记录 epoch 共识抽象在共识算法中扮演着与 epoch 共识原语相同的角色，唯一的变化是记录决策值，该值在达成共识后输出。⟨De