共识算法如何保证一致性？

Question

当两位将军证明“不可能设计出安全一致的算法”时，像Paxos这样的共识算法如何“保证安全（免于不一致）”？

当我考虑让两台服务器（1）可靠地交换号码（即两台服务器最终都知道对方确实收到了号码）或（2）两台服务器最终都知道交换失败并且不改变他们的状态，似乎（就像两个将军一样）消息失败总是以一种留下不一致的方式发生（即，一个服务器认为另一个完成了交换，但它没有）。

那么Paxos（或其他任何东西）如何真正保证“免于不一致”？有没有通俗易懂的解释？演示两个服务器进行有保证的交换或在失败时完全放弃交换的最简单的伪代码是什么？

Answer 1

关键在于 Paxos 的这个假设：

Liveness(C;L)：如果已提出值 C，则最终学习器 L 将学习一些值（如果有足够的处理器保持无故障）。

两将问题的糟糕情况是信使不断被拦截。“如果足够的处理器保持无故障”部分消除了这种可能性。

换句话说，如果消息不断被丢弃，那么 Paxos 不需要（也不会）完成。