零基础入门分布式系统 (Martin Kleppmann) 2. Models of distributed systems

system model 系统模型用于描述我们对节点和网络行为方式的假设。它是对其属性的抽象描述，在实践中可以通过各种技术来实现。为了说明常见的系统模型，我们将从分布式系统中的两个经典思维实验开始：两将军问题和拜占庭将军问题。

2.1 两将军的问题

在两将军问题中，我们想象两位将军，各自领导一支军队，他们想占领一座城市。这座城市的防御很强，如果两支军队中只有一支军队进攻，军队就会被击退。除非两支军队同时进攻，才能成功占领该城市。

因此，两位将军需要协调他们的攻击计划。由于两支军队的营地相距甚远，而且他们只能通过信使进行沟通，这使得协调工作变得困难。信使必须通过城市控制的领土，因此他们有时会被敌军抓住。因此，一个将军发出的信息可能被另一个将军收到，也可能不被收到，发信人不知道他们的信息是否得到了传递，除非收到对方的明确回复。如果一个将军没有收到任何信息，他不可能知道这是因为另一个将军没有发送任何信息，还是因为所有信使都被俘虏了

两位将军应该用什么协议来商定一个计划？对每个将军来说，有两种选择：

• 要么将军承诺在任何情况下都会进行攻击（即使没有收到回应）
• 要么将军在承诺攻击之前等待确认。

在第一种情况下，承诺进行攻击的将军有可能在攻击中落单。在第二种情况下，等待确认的将军将问题转移给另一个将军，后者现在必须决定是承诺攻击（并冒着孤独的风险）还是等待确认的确认。

将军们应该如何决定？

1. 将军1总是攻击，即使没有收到回应？
   • 发送大量的信使，以增加信使通过的概率
   • 如果信使全部被俘，将军2不知道攻击的事，那么将军1就会输掉战争
2. 将军1只在收到将军2的正面回应时才会攻击？
   • 现在将军1是安全的
   • 但将军2知道，只有将军1收到他的回应时才会进攻
   • 现在，将军2的情况与选项1中的将军1相同

没有共同知识：获知某事的唯一方法是沟通

问题是，无论交换多少信息，两位将军都无法确定另一支军队也会在同一时间出现。一系列重复的来回确认可以建立起逐渐增加的信心（即将军们的意见是一致的），但可以明确的是他们无法通过交换任何有限数量的信息来达到确定性。

这个思维实验表明，在一个分布式系统中，一个节点没有办法确定另一个节点的状态。一个节点如何知道一些事情的唯一方法是通过消息来传达这些知识。从哲学的角度看，这也许类似于人类之间的交流：我们没有心灵感应，所以别人知道你在想什么的唯一方法是通过交流（通过语言、文字、身体语言等）。

我们将网上购物改编为两将军问题的一个实际例子。商店和信用卡支付服务通过RPC进行通信，其中一些消息可能会丢失。然而，商店希望确保只有在货物被支付后才发货，并且只有在货物被发送后才向客户卡收费。

实际上，网上购物的例子并不完全符合两将军的问题模型：先给钱再收货其实是安全的，因为如果商店最终不能发送货物，它可以退钱，也可以取消付款来解决问题。如果商店和支付服务之间的通信中断，商店可以等待，直到连接恢复，然后查询并确定交易的状态。

2.2 The Byzantine generals problem

拜占庭将军问题[Lamport et al., 1982]有一个类似于两将军问题的背景。我们再次假设，有三个或更多的军队想要占领一座城市。将军们再次通过信使进行交流，这次我们假设发出的信息一定可以被送达。

拜占庭问题的难点在于，一些将军可能是 traitors"叛徒"：也就是说，他们可能恶意地误导其他将军。我们称这些叛徒为 malicious 恶意的，而其他人则是 honest 诚实的。

举个例子，将军3从将军1和将军2那里收到了两个相互矛盾的信息。1号将军告诉3号将军要进攻，而2号将军则声称1号将军下令撤退。3号将军不可能确定：

• 2号将军是否在撒谎（第一种情况），
• 或者2号将军是诚实的，但1号将军却发出了矛盾的命令（第二种情况）。

拜占庭将军问题:

• 每位将军要么是诚实的，要么是恶意的
• 最多可以有f名恶意的将军
• 诚实的将军们不知道谁是恶意的人
• 恶意的将军们可能会勾结在一起
• 然而，诚实的将军们必须就计划达成一致

我们能推导出一些结论

• 定理：总共需要 3f+1 位将军才能容忍 f 名恶意的将军们
• 密码学（数字签名）有帮助--但问题仍然很难解决

诚实的将军们不知道谁是恶意的将军，但恶意的将军们可能会勾结起来，秘密地协调他们的行动。我们甚至可以假设，所有的恶意将军都被一个邪恶的对手所控制。那么，拜占庭将军问题就是要确保所有诚实的将军都同意相同的计划（例如，是进攻还是撤退）。根据定义，我们不可能指定恶意将军要做什么，所以我们能做的最好的事情就是让诚实的将军们达成一致。

事实上，这是很困难的：在一个具有恶意将军和不可预测的通信延迟的系统中，可以证明拜占庭将军问题只有在严格少于三分之一的将军是恶意的情况下才能得到解决[Dwork et al., 1988, Theorem 4.4]。也就是说，在一个有3f+1个将军的系统中，不超过f个将军是恶意的。例如，一个有4个将军的系统可以容忍f= 1个恶意的将军，一个有7个将军的系统可以容忍f = 2个。

如果将军们使用密码学（数字签名）来证明谁说了什么，这个问题就会变得容易一些：例如，这将要求将军2向将军3证明将军1的命令是什么。我们不会在本课程中讨论数字签名的细节。即使有了签名，拜占庭将军问题仍然具有难点。

拜占庭将军问题是否具有实际意义？

真正的分布式系统确实经常涉及复杂的信任关系。例如，客户需要信任一家网上商店能够真正交付他们订购的货物，尽管他们可以通过银行对付款提出异议，如果货物没有到达或者扣了不该扣的钱。但是，如果一家网店以某种方式允许顾客在不付款的情况下订购商品，这个弱点无疑会被欺诈者所利用，所以网店必须假设顾客是潜在的恶意的。

另一方面，对于属于商店的服务之间的RPC，运行在同一个数据中心，一个服务可能可以信任由同一公司运行的其他服务。支付服务并不完全信任商店，因为有人可能会建立一个欺诈性的商店或使用被盗的信用卡号码，但商店可能确实信任支付服务。以此类推。最后，我们希望客户、网店和支付服务能够就所下的任何订单达成一致。

拜占庭将军问题是对这种复杂信任关系的简化，但它是研究一些参与者可能有恶意行为的系统的一个很好的起点。

在分布式系统中，有些系统明确地处理了一些节点可能被恶意行为者控制的可能性，这样的系统被称为Byzantine fault tolerant 拜占庭容错。近年来这种理念在区块链和加密货币的加持下变得很流行，其目的是提供某些保证，即使系统中的一些参与者积极地试图欺骗或破坏系统。

PS. 简单说说 "Byzantine拜占庭"这个词的起源。这个词来自于拜占庭帝国，以其首都拜占庭Byzantium或君士坦丁堡Constantinople命名，现在是土耳其的伊斯坦布尔Istanbul。没有任何历史证据表明拜占庭帝国的将军们比其他地方的将军更容易搞阴谋和阳谋。相反，在Leslie Lamport采用这个词来描述拜占庭将军问题之前，拜占庭这个词早就被用于"过于复杂、官僚、狡猾 "的意义上；确切的词源不清楚。

2.3 Describing nodes and network behavior

当设计一个分布式算法时，system model 系统模型是我们对可能发生的故障的假设性具体描述。

我们已经看到了两个思维实验：

• 两将军的问题：网络通信的模型
• 拜占庭将军问题：节点行为的模型

在实际系统中，节点和网络都可能有问题

系统模型中呈现的假设由以下内容组成：

• 网络行为（如信息丢失）
• 节点行为（如崩溃）
• 计时行为（如延迟）

每一部分都对应不同的模型选择

让我们从网络开始。

没有一个网络是完全可靠的：即使在精心设计的具有冗余网络链接的系统中，也可能出错[Bailis and Kingsbury, 2014]。有人可能意外地拔掉了错误的网线。鲨鱼和奶牛可能会对长距离网络造成损害和中断[Google, 2014]。或者一个网络可能暂时过载，也许是意外，也许是由于Dos攻击。任何这些都可能导致信息丢失。

在系统模型中，我们采取更抽象的视角，不必在意鲨鱼和奶牛这些细节。大多数分布式算法假设网络在一对节点之间提供双向的信息传递，也被称为point-to-point 点对点或 unicast 单播通信。真实的网络有时确实允许broadcast 广播或multicast 多播通信（同时向许多收件人发送一个数据包）。但基本上，假设现在的互联网只有单播比较好。在第4章中，我们将展示如何在单播通信的基础上实现广播。

然后，我们要分辨这些假设链接的可靠程度。大多数算法基于以上所列的三种之一

假设两个节点之间是双向的point-to-point 点对点通信：

• Reliable (perfect) links 可靠的（完美的）链接
  • 发送出的信息一定会被接收
  • 信息可能会被重新排序
• Fair-loss links 公平损耗的链接
  • 信息可能会丢失、重复或重新排序
  • 重试+ 扣除
  • 不断重试可以确保信息最终抵达
• Arbitrary links (active adversary) 任意链接（主动攻击者）
  • 存在一个恶意的对手，他可能会干扰信息（窃听、修改、丢弃、欺骗、重放）

网络分区：部分链接上，所有的消息掉线或者延迟一定时间

我们可以通过一些方法将某一类型的链接转换成其他类型。例如，如果我们有一个Fair-loss公平损耗链接，我们可以通过不断地重传丢失的信息，直到最终收到这些信息，并通过过滤掉接收方的重复信息，将其变成一个Reliable可靠链接。Fair-loss公平损耗假设意味着任何network partition 网络分区（网络中断）只会持续有限的时间，而不是永远，所以我们可以保证每条消息最终都会被收到。在网络中断期间发送的任何信息只有在中断修复后才能收到，这可能需要很长的时间。我们将在后面讨论这个话题。

我们在第1.2节中简要讨论过的TCP协议，在网络数据包层面上执行了这种重传和去重。然而，TCP通常会配上一个timeout超时，因此它将在一定时间后放弃并停止重试（通常在一分钟左右）。为了克服更长时间的网络中断，除了TCP提供的机制外，还需要实施额外的重传和去重机制。

练习3.假设你有一个客户端-服务器RPC系统，其中客户端会重复一个RPC请求，直到收到响应。服务器怎样才能对客户端请求去重？

Arbitrary 任意链接才是准确描述互联网上通信的模型：只要你的通信通过一个网络（无论是星巴克的WIFI还是互联网骨干网络），该网络的运营商就有可能以任意的方式干扰和操纵你的网络数据包。操纵网络流量的人被称为active adversary主动攻击者。幸运的是，使用加密技术将Arbitrary 任意链接变成Fair-loss公平损耗链接几乎是可能的。运输层安全Transport Layer Security（TLS）协议（在https://中它提供了 "安全secure"的 "s"），防止主动攻击者窃听、修改、欺骗或重放流量。TLS唯一不能防止的是攻击者阻断通信。因此，只有在我们假设对手不会永远阻断通信的情况下，才能将Arbitrary 任意链接转化为Fair-loss公平损耗链接。

因此，Reliable可靠网络链接的假设并不是完全不现实：一般来说，只要我们愿意在网络中断期间等待一段重试时间，所有发送的消息都有可能被收到。然而，我们还必须考虑这样一种可能性，即消息的发送者在试图重传消息时可能会宕机，这可能导致该消息永久丢失。因此我们来看看节点崩溃的话题。

系统模型：节点行为

每个节点执行一套特定的程序，假设符合以下之一：

• crash-stop 崩溃-停止（fail-stop 故障-停止）
  • （在任何时候）如果一个节点崩溃了，它一定有异常发生。崩溃后，该节点彻底停止运行。
• crash-recovery 崩溃-恢复（fail-recovery 故障-恢复）
  • 一个节点可能在任何时候崩溃，并丢失内存状态。它可能在以后的某个时间恢复执行。 存储在磁盘上的数据在崩溃后仍然存在。
• Byzantine 拜占庭式（fail-arbitrary 故障-任意行为）
  • 如果一个节点偏离了原有程序，它一定有异常发生。异常的节点可能做任何事情，包括崩溃或恶意行为。

没有异常的节点被称为 "correct正确"

在crash-stop 崩溃-停止模型中，我们假设一个节点崩溃后，永远不会恢复。对于无法恢复的硬件故障来说，这是一个合理的模型。或者对于一个把手机掉进厕所的人来说，这也是一个合理的模型。对于软件崩溃，crash-stop 崩溃-停止模型可能显得不现实，因为我们可以直接重启节点来恢复。尽管如此，一些算法还是假设程序符合crash-stop 崩溃-停止模型，因为这使得算法更加简单。在这种情况下，一个崩溃后恢复的节点将被看作一个重新加入系统的新节点。

另外，crash-recovery 崩溃-恢复模型明确地允许节点在崩溃后重新启动并恢复。当一个节点崩溃并重启时，我们假设它所有的内存状态都会丢失，但它在磁盘上存储的数据都会被保留下来。该模型没有假设崩溃的节点可能需要多长时间才能恢复，而且崩溃的节点有可能永远不会恢复。

最后，Byzantine 拜占庭模型是最通用的节点行为模型：如拜占庭将军问题，有故障的节点不仅可能崩溃，而且可能以任意的方式偏离指定的程序，包括表现出恶意行为。一个节点的实现中的错误也可以被归类为拜占庭式故障。然而，如果所有的节点都运行相同的软件，它们都会有相同的错误。因此容错的前提是不超过三分之一的节点有拜占庭故障。原则上，我们可以尝试使用同一算法的几个不同的实现，但这个选择很不现实。因此，我们通常在描述程序意图偏离协议时使用Byzantine 拜占庭这个术语，而不是bug。

在网络的情况下，可以使用通用协议将一个模型转换为另一个模型。而在节点行为的不同模型中，情况就不是这样了。例如，为crash-recovery 崩溃-恢复系统模型设计的算法可能看起来与Byzantine 拜占庭算法完全不相关。

系统模型的第三部分是同步性假设，这是关于时间的。我们在这里可以做出三种选择：synchronous同步, asynchronous异步, 或者 partially synchronous部分同步 [Dwork et al. , 1988]。

假设网络和节点有以下情况之一：

• synchronous 同步
  • 消息延迟不超过已知的上限。
  • 节点以已知速度执行算法。
• partially synchronous 部分同步
  • 系统在某些有限的（但未知的）时间段内是异步的，其余时间内是同步的
• asynchronous 异步
  • 消息可以被任意延迟
  • 节点可以任意地暂停执行
  • 完全没有时间(计时)保证

注：计算机科学的其他领域以不同的方式使用 "同步 "和 "异步 "两个术语在其他语境中也有不同的含义。例如，在RPC和I/O操作的语境中，"同步"通常意味着 "调用者阻塞/等待操作完成"，而 "异步 "意味着 "调用者在发出请求后继续执行，不等待结果"。令人遗憾的是，同样的词被用于不同的含义，但由于这些术语在文献中被广泛使用，我们将坚持使用这些标准术语。

同步系统是大家最喜欢的：通过网络发送的消息永远不会超过某个已知的最大延迟，而且节点总是以可预测的速度执行其算法。如果你假设一个同步系统，分布式计算中的许多问题就容易得多。而且，同步假设很上头，因为网络和节点在大多数时候都不会出错的，所以这个假设在most of the time（大部分时候）为真。

但是，most of the time 大多数时候并不等于 always 总是这样。一旦违反了有限延迟和可预测执行速度的假设（即使这种情况很少发生，并且只是短暂的违反），基于同步模型设计的程序往往会出现灾难性的崩溃。在实际系统中，有太多原因导致网络延迟或执行速度出现变化。

另一个极端是异步模型，在这个模型中，我们根本不做任何时间假设：我们允许消息在网络中任意延迟，我们允许节点处理速度的任意差异（例如，我们允许一个节点暂停执行而其他节点继续正常运行）。为异步模型设计的算法通常非常稳健，因为它们不受任何临时网络中断或延迟峰值的影响。

不幸的是，分布式计算中的一些问题在异步模型中是无法解决的，因此我们有partially synchronous 部分同步模型作为折衷方案。在这个模型中，我们假设我们的系统在大多数时候都是同步且运行良好的，但偶尔也会转到异步模式。异步模式下没有任何时间保证，而且无法预测这种情况什么时候发生。partially synchronous 部分同步模型对许多实际系统很友好，但需要正确且谨慎地使用。

实践中违反同步性的情况

系统违反同步性假设的原因有很多。网络通常有一定程度可预测的延迟，以下场景都会增加延迟：

• 信息丢失，导致需要重试：
  • 我们已经说过，如果信息丢失并重传，延迟会持续增加，特别是如果我们必须等待网络中断修复后，继续传输信息。
• 拥堵/拥挤导致排队：
  • 网络中延迟增加的另一个原因是拥堵，导致数据包在交换机缓冲区排队。
• 网络/路线重新配置：
  • 网络重新配置也会导致大量延迟：即使在一个数据中心内，也有记录显示数据包延迟超过一分钟的情况 [Imbriaco, 2012]。

我们可能期望程序在某个节点上执行的速度是恒定的：毕竟，一条指令一般需要固定数量的CPU时钟周期，而时钟速度本身不会有太大变化。然而，即使在单一节点上，也有许多原因导致正在运行的程序被意外地暂停了很长时间。节点通常以可预测的速度执行代码，但以下场景会带来停顿：

• 操作系统的调度问题，如优先级变动
  • 操作系统中的调度可以抢占一个正在运行的线程，让它在其他程序运行时暂停，特别是在负载很重的机器上。
• 基于Stop-the-world（STW 全局暂停）的垃圾回收（JVM Full GC）
  • 另一个实际的问题是，在Java这样的内存管理语言中，执行垃圾回收时，它需要不时地暂停所有正在运行的线程（这被称为全局暂停垃圾回收）。在一个非常大的堆上，这样的暂停可以长达几分钟[Thompson, 2013]。
• Page faults 页面故障、swap 交换、thrashing颠簸
  • 页面故障是一个线程可能被暂停的另一个原因，特别是当剩余的可用内存不多的时候。

实时操作系统（RTOS）提供调度保证，但大多数分布式系统不使用RTOS

在程序执行的任何阶段，线程可能且一定会在最不方便的时刻被抢占。在分布式系统中，这尤其成问题，因为对一个节点来说，当它被暂停时，时间似乎"stand still静止"了。而在这段时间里，所有其他节点继续正常执行它们的算法。其他节点甚至可能注意到暂停的节点没有响应，并认为它已经宕机了。一段时间后，暂停的节点恢复处理，甚至没有意识到它已经暂停了很长一段时间。

这些执行暂停与之前讨论的崩溃和重启不一样。当一个正在执行的进程或线程被暂停时，它通常不会注意到它已经被暂停了，除非它定期检查系统时钟来测量已过去的时间。另一方面，重启是由程序明确处理的，因为它的内存状态在崩溃时丢失了，在重启时它可能会从磁盘加载其持久状态。

再加上网络延迟变化的诸多原因，这意味着在实际系统中，假设一个同步系统模型是非常不安全的。大多数分布式算法需要为异步或部分同步模型设计。

2.4 Fault tolerance and high availability

建立分布式系统的一个原因是为了实现比单台计算机更高的可靠性。现在我们将根据我们所讨论的系统模型来进一步探讨这个想法

从商业角度来看，通常最重要的是服务的availability可用性，比如网站。一家网上商店希望能够在白天或晚上的任何时候销售产品：网站的任何中断都意味着失去了赚钱的机会。对于其他服务，甚至可能有与客户签订的合同协议，要求该服务必须可用。如果一项服务不可用，也会损害服务提供商的名声。

服务的可用性通常是以其在一定时间内正确响应请求的能力来衡量的。一个服务是 "可用"还是 "不可用"的定义可能有些武断：例如，如果加载一个页面需要5秒，我们是否仍然认为该网站是可用的？如果它需要30秒呢？一个小时呢？

通常，服务的可用性期望的正式定义为service-level objective服务水平目标（SLO），它通常规定了由某个客户在某段时间内，需要（在指定timeout时间内）正确响应请求的百分比。service-level agreement 服务水平协议（SLA）是一个合同，它规定了一些SLO，以及如果没有达到SLO的后果（例如，服务提供商可能需要向其客户提供退款）。

故障（如节点崩溃或网络中断）是导致不可用的一个常见原因。为了提高可用性，我们可以减少故障的频率，或者我们可以设计系统使其在某些部件出现故障的情况下继续工作；后一种方法被称为fault tolerance 容错。通过购买更高质量的硬件和引入冗余来减少故障频率是可行的，但这种方法永远无法将故障的概率降低到零。所以许多分布式系统采取容错的方法。

容错性总是相对于可以容忍的最大数量的故障：例如，一些分布式算法在少于一半的节点崩溃的条件下依然能够运行，但如果超过一半的节点崩溃就会停止工作。想要容忍无限数量的故障是不现实的：如果所有的节点都崩溃并且不能恢复，那么无论多么高明的程序都无法运行。

在某些系统中，一个部件出现故障会导致整个系统的宕机。这样的组件被称为single point of failure单点故障（SPOF），而容错系统一般都试图避免出现任何单点故障。例如，互联网被设计成没有单点故障：没有一个服务器或路由器的崩溃会导致整个互联网的瘫痪（尽管一些组件的损失，如关键的洲际光纤链接，确实会造成明显的瘫痪）。

• 故障检测器：检测另一个节点是否有故障的算法
• 完美的故障检测器：当且仅当一个节点崩溃时，将该节点标记为故障。
• 崩溃-停止/崩溃-恢复的典型实现：发送消息，等待响应，如果在某个超时时间内没有响应，则将节点标记为崩溃
• 问题：无法区分崩溃的节点、暂时无响应的节点、丢失的信息和延迟的信息。

容错的第一步是检测故障，这通常是通过failure detector 故障检测器完成的。("Fault detector"将是一个更合乎逻辑的名称，但"failure detector"是约定好的术语)。故障检测器通常检测的是崩溃故障。拜占庭故障并不总是可以检测到的，尽管在某些情况下拜占庭行为确实留下了线索，可以用来识别和排除恶意节点。

在大多数情况下，故障检测器的工作方式是定期向其他节点发送消息。如果在预期时间内没有收到响应，就将节点标记为崩溃。理想情况下，我们希望只有当节点真的崩溃时才会发生超时（这被称为perfect failure detector 完美故障检测器）。然而，两将军问题告诉我们，这并不是一个完全准确的检测崩溃的方法，因为没有响应也可能是由于消息丢失或延迟。

完美的基于超时的故障检测器只存在于具有可靠链路的、同步的、崩溃-停止系统中（a synchronous crash-stop system with reliable links）。在 partially synchronous 部分同步系统中，一个完美的故障检测器并不存在。此外，在异步系统中，不存在基于timeout 超时的故障，因为在异步模型中超时是没有意义的。然而，在部分同步系统中存在一个有用的故障检测器：eventually perfect failure detector 最终完美故障检测器 [Chandra and Toueg, 1996]。

最终完美的故障检测器：

• 可能暂时将一个节点标记为crashed崩溃，尽管它是correct正确的
• 可能暂时将一个节点标记为correct正确，即使它已经crashed崩溃了
• 最终，当且仅当一个节点已经crashed崩溃时，将其标记为crashed崩溃

以上反映了故障检测不是即时的，可能存在错误的超时

我们将在后面看到，如何使用这样的故障检测器来设计容错机制，并自动从节点崩溃中恢复。使用这样的算法，就有可能建立高度可用的系统。容错设计也使日常操作更容易：例如，如果一个服务可以容忍三个节点中的一个不可用，那么就可以通过安装软件升级、并一次重启一个节点的方式来升级软件，同时其余两个节点继续运行该服务。以这种方式推出软件升级，客户端不会注意到任何中断，这对发布方式对许多无间断升级软件的组织来说是非常重要的。

对于safety-critical 安全关键应用，如空中交通控制系统，良好的容错机制无疑非常重要。然而，并不是可用性越高就越好。要达到极高的可用性，需要集中很多的工程资源，而且往往选择保守设计。例如，老式的固定电话网络是为"五个9"的可用性而设计的，但这种堆砌可用性的缺点是，它的发展非常缓慢。因为收益递减，大多数互联网服务甚至没有达到四个9：在某些时候，实现更高的可用性的额外成本超过了偶尔停机的成本，所以接受一定量的停机时间在经济上是合理的。

练习 4. 可靠的网络链接允许消息被重新排序。假设有一个异步崩溃-**停止的系统模型，请给出一个算法的伪代码，要求该算法加强了可靠的点对点链路的特性，使信息按照发送的顺序被接收（这被称为先进先出FIFO链路）

练习5. 如果我们假设存在一个崩溃-恢复模型而不是崩溃-停止模型，我们需要如何改变练习4中的算法？