系统模型

系统模型

算法的编写方式并不过分依赖于运行的硬件和软件配置的细节。这又要求我们以某种方式将我们期望在系统中发生的错误形式化。我们通过定义一个系统模型来做到这一点，这个模型是一个抽象，描述一个算法可能承担的事情。关于定时假设，三种系统模型是常用的：

定时假设模型

同步模型

同步模型（synchronous model）假设网络延迟，进程暂停和和时钟误差都是有界限的。这并不意味着完全同步的时钟或零网络延迟；这只意味着你知道网络延迟，暂停和时钟漂移将永远不会超过某个固定的上限。同步模型并不是大多数实际系统的现实模型，因为（如本章所讨论的）无限延迟和暂停确实会发生。

部分同步模型

部分同步（partial synchronous）意味着一个系统在大多数情况下像一个同步系统一样运行，但有时候会超出网络延迟，进程暂停和时钟漂移的界限。这是很多系统的现实模型：大多数情况下，网络和进程表现良好，否则我们永远无法完成任何事情，但是我们必须承认，在任何时刻假设都存在偶然被破坏的事实。发生这种情况时，网络延迟，暂停和时钟错误可能会变得相当大。

异步模型

在这个模型中，一个算法不允许对时机做任何假设——事实上它甚至没有时钟（所以它不能使用超时）。一些算法被设计为可用于异步模型，但非常受限。

节点失效系统模型

除了时间问题，我们还要考虑节点失效。三种最常见的节点系统模型是。

崩溃-停止故障

在崩溃停止（crash-stop）模型中，算法可能会假设一个节点只能以一种方式失效，即通过崩溃。这意味着节点可能在任意时刻突然停止响应，此后该节点永远消失——它永远不会回来。

崩溃-恢复故障

我们假设节点可能会在任何时候崩溃，但也许会在未知的时间之后再次开始响应。在崩溃-恢复（crash-recovery）模型中，假设节点具有稳定的存储（即，非易失性磁盘存储）且会在崩溃中保留，而内存中的状态会丢失。

拜占庭（任意）故障

节点可以做（绝对意义上的）任何事情，包括试图戏弄和欺骗其他节点。

算法的正确性

为了定义算法是正确的，我们可以描述它的属性。例如，排序算法的输出具有如下特性：对于输出列表中的任何两个不同的元素，左边的元素比右边的元素小。这只是定义对列表进行排序含义的一种形式方式。同样，我们可以写下我们想要的分布式算法的属性来定义它的正确含义。例如，如果我们正在为一个锁生成屏蔽令牌，我们可能要求算法具有以下属性：

• 唯一性：没有两个屏蔽令牌请求返回相同的值。

• 单调序列：如果请求 $x$ 返回了令牌 $t_x$，并且请求$y$返回了令牌$t_y$，并且 $x$ 在 $y$ 开始之前已经完成，那么$t_x <t_y$。

• 可用性：请求防护令牌并且不会崩溃的节点，最终会收到响应。

如果一个系统模型中的算法总是满足它在我们假设可能发生的所有情况下的性质，那么这个算法是正确的。但这如何有意义？如果所有的节点崩溃，或者所有的网络延迟突然变得无限长，那么没有任何算法能够完成任何事情。