1.4.2 进程失败

进程失败是设计分布式算法正确性的第二大挑战。在顺序执行算法中，一般不考虑进程失败的场景，因为进程失败了，那么研究对象就没有了；而在分布式算法中，进程失败是必然要面对的问题，不能因为单节点失败导致整个分布式系统的失败。

在分布式算法中，一个进程只有两种状态，要么是正确的，要么是失败的。正确就表示不是失败的，失败就表示不是正确的。

进程失败有很多种，设计分布式算法很重要的一个方面就是选择合适的失败模型。

第一种失败被称为崩溃式失败，属于比较简单的失败，即进程停止执行任何步骤，不收发任何消息，就像进程完全退出执行了一样，例如进程被停止执行或者节点断电了。

第二种失败被称为遗漏式失败，这时进程并非完全停止执行步骤，而是不能正常收发消息，包括进程收不到它该收的消息，或者发不出它该发的消息。当出现网络拥塞或缓冲区溢出时，就会出现这种失败。

第三种失败被称为恢复后崩溃失败，即进程在一次或多次恢复后最终崩溃，或者无限的处于恢复、崩溃的反复之中。反之，如果进程在经过有限次的崩溃、恢复后，最终恢复到正确状态，那么这个进程仍然是正确的。

第四种失败被称为随意式失败，也叫拜占庭失败（Byzantine Failure）。之所以用“拜占庭”命名，是因为Lamport在1982年发表了一篇论文讨论这个问题，这篇论文的名字就叫《拜占庭将军问题》。与前面所述的失败不一样的是，拜占庭失败的进程可能“不按剧本演戏”，即会在某个不可预测的时间点执行预设算法以外的逻辑。

分布式算法面对很多的失败情形，检测这些失败是很复杂的工作。一方面，这个检测有可能不准确，把一个正确的进程误判为失败的进程；另一方面，有的正确的进程能够检测到这个失败的进程，而有的正确的进程却没有检测到这个失败的进程。也就是说，不是所有的正确的进程都能及时检测到失败的进程，导致这些正确的进程对待这个失败的进程时出现了分歧（执行不同的代码逻辑）。更有甚者，一个系统不止有一个失败的进程，情况就变得更加复杂了。