Paxos算法

Paxos是一个协议系列，用于解决不可靠或易变的处理器网络中的共识问题。共识是在一群参与者中就一个结果达成一致的过程。当参与者或其通信可能出现故障时，这个问题就变得很困难。

状态机复制是一种将算法转换为容错的分布式实现的技术。临时性的技术可能会使重要的故障情况得不到解决。

Paxos系列协议包括在处理器数量、学习约定值之前的消息延迟数量、单个参与者的活动水平、发送的消息数量和故障类型之间的权衡谱。尽管没有一个确定性的容错共识协议能够保证在异步网络中取得进展（Fischer、Lynch和Paterson的论文中证明了这一结果），但Paxos保证了安全（一致性），而且可能阻止其取得进展的条件很难被激起。

Paxos通常用于需要持久性的地方（例如，复制文件或数据库），其中持久状态的数量可能很大。该协议试图取得进展，即使是在一些有限数量的复制体没有反应的时期也是如此。还有一种机制可以放弃一个xxx失败的副本或添加一个新的副本。

可重构状态机与之前支持动态群组成员的可靠群组组播协议的工作有着密切的联系，然而，gbcast在支持持久性和解决分区故障方面是不寻常的。大多数可靠的组播协议缺乏这些特性，而这些特性是实现状态机复制模型所需要的。

Paxos协议是一个问题的理论类解决方案的成员，这个问题被形式化为有崩溃故障的统一协议。Keidar和Shraer已经证明了这个问题的下限。Derecho是一个用于云规模状态机复制的C++软件库，它提供了一个Paxos协议，该协议已经与自我管理的虚拟同步成员相结合。该协议与Keidar和Shraer的优化界限相匹配，并有效地映射到现代远程DMA（RDMA）数据中心硬件（但如果RDMA不可用，则使用TCP）。

为了简化Paxos的介绍，以下假设和定义被明确提出。

• 处理器以任意速度运行。
• 处理器可能出现故障。
• 具有稳定存储的处理器可能在故障后重新加入协议（遵循崩溃恢复故障模型）。
• 处理器不会串通、撒谎或以其他方式试图颠覆协议。(也就是说，拜占庭式的失败不会发生。请参阅拜占庭Paxos的解决方案，它可以容忍因进程的任意/恶意行为而产生的故障。）

• 处理器可以向任何其他处理器发送消息。
• 消息是异步发送的，可能需要任意的时间来交付。(也就是说，拜占庭式的失败不会发生。请参阅拜占庭Paxos的解决方案，它可以容忍因信息传递通道的任意/恶意行为而产生的损坏的消息。）

一般来说，一个共识算法可以使用n = 2 F + 1 {displaystyle n=2F+1}处理器取得进展，尽管同时有。