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

Question

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

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

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

Answer 1

关键是 Paxos 的这个假设：

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

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

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

Answer 2

Paxos 实际上并没有解决 2 将军问题。正如维基百科文章所引用的：

一般来说，一个共识算法可以在使用 2F+1 个处理器的情况下取得进展，尽管任何 F 个处理器同时发生故障。

在 2 将军问题中，处理 1 个节点的故障意味着您需要2*1 + 1 = 3节点来处理那么多故障。2个将军的不可能性问题没有推广到N个将军。

人们在现实世界中解决 2 将军问题的一种方法是击剑。