文章目录paxos介绍拜占庭将军问题算法原理协商过程示例
Pax操作系统介绍
Paxos 算法是xqdzs 英语)在1990年提出的基于消息传递的具有高度容错特性的共识consensus )算法。
Paxos算法需要解决的问题是分布式共识性问题，即分布式系统中的各个进程如何就某个值决议)达成共识。 但是，Paxos经常被误解为一致性算法consistency )和一致性) consensus Paxos实际上是一种共识算法。
Paxos算法在允许停机故障的异步系统中运行，不需要可靠的消息传递，并且允许消息丢失、延迟、乱序和重复。
Paxos算法解决的问题是，在不考虑是否存在可信中央节点和可信信道的情况下，分散在网络中的各个节点应该如何达成共识。
拜占庭将军问题拜占庭将军问题是一个协议问题，说的是拜占庭帝国军队的将军们必须全体一致决定是否攻击敌军。 问题是，这些将军在地理上是分开的，只能依靠通讯员传达命令，但通讯员和将军中存在奋斗的摩托车。共识催促并不是所有将军都同意的决定，例如在将军们不希望攻击时催促攻击行动，或者迷惑某些将军，使他们无法作出决定。
奋斗的摩托车可以在它们可以篡改消息上实现以下目标。
欺骗部分将军采取攻击行动； 迷惑了一些将军，促使他们作出并不是所有将军都同意的决定，例如在将军们不希望攻击时催促攻击行动，使他们无法作出决定。 奋斗的摩托车如果达到这些目的之一，任何攻击行动的结果都注定失败，只有完全一致的努力才能取得胜利。
假设拜占庭对现实世界进行了建模，则硬件错误、网络拥塞或断开以及恶意攻击可能会导致计算机和网络发生意外行为。
算法原理该算法的基本思想是利用大多数Majority )机制保证2F 1的容错能力。 也就是说，2F 1节点的系统允许最多f个节点同时故障。
一个或一个以上提议过程可开始提议过程提议过程)，其中Paxos算法使所有过程协商一致所有提议中的一个提议。
系统的多数派同时同意批准这个提案。 对最多一个确定的提案达成了一致。
Paxos将系统中的角色分为：三类
篡改消息:提案Proposal )。 提案信息包括提案编号Proposal ID )和提案值Value )。提议者 Proposer):参与决策并响应Proposers的建议。 收到Proposal后，可以接受该提案，如果Proposal被很多Acceptors接受，据说该Proposal得到了批准。决策者 Acceptor):从Proposers/Acceptors学习最新的商定建议Value )，而不参与决策。 在具体实现中，一个流程可能同时扮演多个角色。 例如，流程可能是Proposer、加速器或学习者。 宣传负责提案，
加速器负责提案的裁决是否为accept )，learner负责提案结果的学习。
还有一个重要概念，即3http://www.Sina.com/proposal )。 最终达成一致的value在提案中。 只要Proposer发送的建议被加速器接受，当该建议中的value告诉Learner http://www.Sina.com/acceptor选择了哪个value时，Proposer就会通知learner 只要加速器接受了某个建议，加速器就任务而言，该建议中的value已被学习者 Learner)。
为了避免单点故障，有一个加速器组。 Proposer想把提案发送给Acceptor集团。 加速器组的每个成员都可能同意该建议，每个加速器只能批准一个建议。 如果一半以上的成员同意一项提案，则认为该提案已被选定。
Paxos算法的前提条件是不存在拜占庭将军问题。 即，提案，发出的信号没有被篡改。 因为Paxos算法是基于消息传递的。
理论上，在分布式计算领域，通过异步系统和不信任通道实现一致的状态是不可能的。 因此，在研究一致性的过程中，往往假设渠道是可靠的
事实上，大多数系统都部署在局域网中，因此消息很少被篡改，但由于硬件和网络原因而无法消除
息不完整问题，只需要一套简单的校验算法即可。因此，在实际工程中，可以假设所有的消息都是完整的，也就是没有被篡。
协议过程
主要分为以下两个阶段：
阶段 1：
一个 proposer 选择一个提议编号 n，然后将提议编号 n放入 prepare request 中并发送给 acceptors 中的多数派（出于性能优化的考虑，它只需要大多数的 acceptors 同意）。具体发送给哪些 acceptors 由 proposer 自己决定。如果一个 accptor 接受了一个 prepare request，其中的数字 n 大于这个 acceptor 已经回复过的所有 prepare request，那么他会回复这个 request，同时承诺不接受比 n 小的提议编号，而且会返回它已经接受过的提议中编号最大的那个提议（如果有的话）。
阶段 2：
如果这个 proposer 收到了来自多数 acceptors 对 prepare requests 编号 n) 的回复，那么他会对这些 acceptors 分别发送一个 accept request，其中包含提议编号 n 和一个值 v（v是响应的提议中编号最大的那个提议的值）。否则会重新提议
举个例子
想象一个用来卖票的分布式系统，这个系统一共有五台机器，分布在不同的地点。另外我们假定这个系统只剩最后一张票。五台机器有各自的数据库，用来储存买票者的名字。如果机器 A 认为这张票应该由它去卖，而机器 B 也想卖这张票，那该如何是好。于是我们需要就谁来卖出这张票来在这五台机器间达成共识，具体到这个例子就是保证不同机器中买票者的名字是同一个。
假如此时机器 D 收到了来自 sdxf 的买票请求。于是 D 首先进入 Prepare 阶段：,
D 向其他 4 台机器发送了一条 提议：
其中 P-1D 表示：
这是一个提议（P for Prepare）提议的 ID 是 1D
每个提议都需要一个递增的全局唯一 ID，最简单的方法就是当前时间加上当前机器的名字。这个 ID 会贯穿整个 Paxos 流程。值得注意的是，在提议阶段，D 并没有把购买者的名字 sdxf 告诉其他机器。
其他机器收到这个提议后，他们发现之前并没有收到过提议，于是同意了这份提议。具体来说是做了下面几件事：
将 P-1D 记录下来承诺以后不再接受 ID < “1D” 的提议向 D 回复 OK，表示对提议的回复
D 收到其他机器的回复后，发现加上自己的同意，发现已经有超过半数的机器同意将票卖给 sdxf（事实上，所有五台机器都同意这点）。即然多数派已经同意了这份提议，那么 D 就认为认为这个提议已经被通过了，于是进入了 Commit 阶段。
在 Commit 阶段，D 向所有机器发出了一个决议：
其中 A-1D-sdxf 表示
这是一个决议（A for Accept）决议的 ID 是 1D决议内容：将票卖给 sdxf
其他四台机器到了这个决议后，就会把决议的内容记录下来，并返回给 D。D 最后把买票成功的消息发给 sdxf，表示对决议的回复：
此时，所有五台机器都达成共识由D把票卖给sdxf，同时一致性也得到了保证。