分布式算法：概念、分类与基础算法解析

### 分布式算法：概念、分类与基础算法解析 在分布式系统领域，理解各种算法和概念对于设计高效、可靠的系统至关重要。本文将深入探讨分布式算法中的关键概念、分类以及一些基础算法。 #### 1. 协议分类：抑制与非抑制 协议的执行方式可以根据事件的抑制情况进行分类。正常执行直到协议规定的一系列操作完成的协议被称为抑制或冻结协议。不同的分布式算法执行可能导致事件的不同交织，因此每个算法（或协议）都有多种执行方式。协议可以按照以下方式根据抑制情况进行分类： - **非抑制协议**：如果在协议的任何执行中都没有系统事件被禁用，则该协议是非抑制的；否则，它是抑制的。 - **局部抑制协议**：在执行中被禁用的事件 e 如果存在执行的扩展（超出当前状态），使得该事件在扩展后变为启用，并且在扩展中没有中间接收事件，则称该事件是局部延迟的。如果协议在任何执行中被禁用的任何事件都是局部延迟的，则该协议是局部抑制的。 - **全局抑制协议**：如果存在某种执行，其中某些延迟事件不是局部延迟的，则该抑制协议是全局抑制的。在全局抑制协议的某些（或所有）执行中，至少有一个事件会延迟等待从另一个处理器接收通信。 此外，还有一种正交分类，即发送抑制、接收抑制和内部事件抑制： - **发送抑制协议**：如果某些延迟事件是发送事件，则该协议是发送抑制的。 - **接收抑制协议**：如果某些延迟事件是接收事件，则该协议是接收抑制的。 - **内部事件抑制协议**：如果某些延迟事件是内部事件，则该协议是内部事件抑制的。 这些分类有助于刻画设计协议解决各种问题所需的抑制程度，也可以作为评估协议的标准。抑制类越严格，协议越不理想。 #### 2. 同步与异步系统 - **同步系统**：同步系统满足以下特性： - 消息通信延迟有已知的上限。 - 每个处理器的本地时钟相对于实时有已知的有界漂移率。 - 进程执行逻辑步骤所需的时间有已知的上限。 - **异步系统**：异步系统不满足同步系统的上述三个特性。显然，系统可以设计成满足部分但不是全部定义同步系统的标准。解决任何特定问题的算法可能会根据模型假设而有很大差异，因此事先明确识别系统模型非常重要。分布式系统本质上是异步的。 #### 3. 在线与离线算法 - **在线算法**：在线算法在数据生成时执行。 - **离线算法**：离线算法需要在算法执行开始前所有数据都可用。显然，在线算法更可取。例如，在线调度允许动态更改调度以适应新到达的具有更近截止日期的请求，在线调试可以在错误发生时检测到错误。 #### 4. 故障模型 故障模型指定系统组件可能发生故障的方式。有许多经过深入研究的故障模型。明确指定故障模型很重要，因为解决任何特定问题所使用的算法可能会根据假设的故障模型而有很大差异。 - **进程故障模型**： - **Fail - stop**：在这个模型中，正常运行的进程可能从某个时刻起停止执行，并且其他进程可以得知该进程已失败。 - **Crash**：正常运行的进程可能从任何时刻起停止运行，但其他进程不会得知该崩溃。 - **Receive omission**：正常运行的进程可能间歇性地只接收发送给它的部分消息，或者崩溃。 - **Send omission**：正常运行的进程可能间歇性地只发送它应该发送的部分消息，或者崩溃。 - **General omission**：正常运行的进程可能表现出发送遗漏和接收遗漏故障中的一种或两种。 - **Byzantine or malicious failure, with authentication**：进程可能表现出任何任意行为，但如果一个有故障的进程声称从一个正确的进程接收到特定消息，则可以使用基于不可伪造签名的认证来验证该声明。 - **Byzantine or malicious failure**：进程可能表现出任何任意行为，并且没有认证技术可用于验证任何声明。 这些进程故障模型（除了发送遗漏和接收遗漏不可比较外）按严重程度递增排列，适用于同步和异步系统。 - **通信故障模型**： - **Crash failure**：正常运行的链路可能从某个时刻起停止传输消息。 - **Omission failures**：链路传输一些消息，但不传输发送到它上面的其他消息。 - **Byzantine failures**：链路可以表现出任何任意行为，包括创建虚假消息和修改发送到它上面的消息。 这些链路故障模型适用于同步和异步系统。在同步系统中，还可能发生定时故障，表现为链路传输消息的速度比指定的行为快或慢。 #### 5. 无等待算法 无等待算法可以以（n - 1）进程容错的方式执行（同步操作），即它能抵御 n - 1 个进程故障。如果一个算法是无等待的，那么任何进程的（同步）操作必须在有界的步骤内完成，而不管其他所有进程是否发生故障。无等待算法提供了很高的鲁棒性，但设计无等待算法通常成本很高，并且对于某些同步问题可能甚至不可行。 #### 6. 通信通道 通信通道通常是先进先出（FIFO）队列，但在网络层，这个特性可能不满足，从而产生非 FIFO 通道。