分布式系统模型与相关概念解析

### 分布式系统模型与相关概念解析 #### 1. 分布式系统模型 分布式系统有多种模型，每种模型都有其特点和适用场景。 - **Fail - recovery**：该模型下设计的算法要应对进程失忆的后果，即进程崩溃后可能忘记之前的操作，但可使用稳定存储。链接假设为顽固链接，算法可依赖最终领导者检测器（Ω）。 - **Fail - arbitrary**：这是最通用的分布式系统模型，使用任意故障（或拜占庭）进程抽象和认证完美链接抽象。当拜占庭进程抽象与认证完美链接以及拜占庭最终领导者检测器抽象结合时，称为故障嘈杂任意模型。 - **Randomized**：随机化模型与其他分布式系统模型性质不同，可视为与它们正交。该模型用于更通用的进程抽象，算法不一定是确定性的，进程可使用随机源选择执行步骤，通常以一定概率实现给定抽象。 需要注意的是，很多抽象仅针对具有崩溃停止进程的三种模型（故障停止、故障嘈杂和故障沉默模型）进行指定。在其他分布式系统模型中，尤其是故障恢复和故障任意模型中，这些抽象的表述会不同。而且，很多研究的抽象并非能在所有模型中实现。 #### 2. 系统设置 在所有考虑的系统模型中，所有进程的身份在执行开始前就已定义，且必须全局已知。在实践中，这些身份要么由管理员手动配置，要么由成员服务自动安装，而成员服务本身也需初始化。 密码学抽象还要求根据所有进程的身份分发密钥。例如，消息认证码（MAC）需要每对进程有一个共享对称密钥；数字签名方案要求每个进程有一对公私钥，只有进程自身知道私钥，其他进程知道其公钥。密钥分发在系统模型之外进行，通常由可信代理在系统设置时，与定义进程身份同时进行。 #### 3. 法定人数 法定人数是为一组 N 个进程设计容错算法的常用工具，是具有特殊属性的进程集合。 - **崩溃故障系统法定人数**：在具有 N 个崩溃故障进程抽象的系统（故障停止、故障嘈杂、故障沉默或故障恢复系统模型）中，法定人数是任何多数进程，即超过 N/2 个进程的集合（等价于 ⌈(N + 1)/2⌉ 或更多进程）。多个算法依赖法定人数，利用任意两个法定人数至少有一个进程重叠的特性。即使 f < N/2 个进程因崩溃而失败，此类系统中始终至少有一个非崩溃进程的法定人数。 - **任意故障系统法定人数**：在由任意故障进程抽象组成的系统中，两个多数法定人数可能不会在一个正确进程上相交。容忍 f 个故障的拜占庭法定人数是超过 (N + f)/2 个进程的集合（等价于 ⌈(N + f + 1)/2⌉ 或更多进程）。两个拜占庭法定人数总是至少在一个正确进程上重叠。依赖拜占庭法定人数的算法通常需要在从拜占庭法定人数的进程获得某些消息后取得进展，这要求系统中至少存在一个拜占庭法定人数的正确进程，因此通常要求 f < N/3 个进程可能失败。 以下是法定人数相关的总结表格： | 系统类型 | 法定人数定义 | 特点 | | ---- | ---- | ---- | | 崩溃故障系统 | 超过 N/2 个进程的集合（⌈(N + 1)/2⌉ 或更多） | 任意两个法定人数至少有一个进程重叠，f < N/2 时仍有非崩溃进程法定人数 | | 任意故障系统 | 超过 (N + f)/2 个进程的集合（⌈(N + f + 1)/2⌉ 或更多） | 两个拜占庭法定人数至少在一个正确进程上重叠，要求 f < N/3 | #### 4. 性能测量 在展示实现给定抽象的分布式算法时，主要使用以下指标分析其成本： 1. **消息数量**：完成抽象操作所需的消息数量。 2. **通信步骤数量**：完成此类操作所需的通信步骤数量。 3. **总通信大小**：算法发送的所有消息长度之和，以位为单位。在评估故障恢复模型中算法的性能时，还需考虑对稳定存储的访问次数（或“日志操作”）。 一般在特定执行中（尤其是无故障执行）计算消息、通信步骤和磁盘访问次数，因为无故障执行在实践中更可能发生，且算法通常针对这种情况进行优化。性能测量常使用大 O 表示法，它只提供函数渐近行为的上界。 性能测量指标总结表格： | 指标 | 含义 | | ---- | ---- | | 消息数量 | 完成操作所需消息数 | | 通信步骤数量 | 完成操作所需通信步骤数 | | 总通信大小 | 算法发送消息长度总和（位） | | 稳定存储访问次数 | 故障恢复模型中对稳定存储的访问次数 | #### 5. 练习题与解答 以下是一些练习题及其解答： - **Exercise 2.1**：在假设进程有稳定存储并将状态更新存储在其中，且进程不知道自己已崩溃和恢复的情况下，故障恢复和故障沉默模型相似。 - **Exercise 2.2**：FIFO 顺序完美点对点链接抽象除了完美点对点链接的保证外，还确保消息不被重新排序。其规范如下： ```plaintext Module 2.11: Interface and properties of FIFO - order perfect point - to - point links Module: Name: FIFOPerfectPointToPointLinks, instance fpl. Events: Request: ⟨fpl, Send | q, m ⟩: Requests to send message m to process q. Indication: ⟨fpl, Deliver | p, m ⟩: Delivers message m sent by process p. Properties: FPL1–FPL3: Same as properties PL1–PL3 of perfect point - to - point links (Module 2.3). FPL4: FIFO delivery: If some process se ```